Language Approximation With One-Counter Automata

2017/07/23 by A. Sakharov, Sakharov, Alexander
Computer Science · #Algorithms and Data Compression #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1707.07670

openalex publication_date 2017/07/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present a method for approximating context-free languages with one-counter automata. This approximation allows the reconstruction of parse trees of the original grammar. We identify a decidable superset of regular languages whose elements, i.e. languages, are recognized by one-counter automata.

Related

• Practical experiments with regular approximation of context-free languages
• An automata characterisation for multiple context-free languages
• Global One-Counter Tree Automata
• A Regularity Measure for Context Free Grammars
• One-Tape Turing Machine Variants and Language Recognition