Finite-Turn Pushdown Automata

DOI10.1137/0304034zbMath0147.25302OpenAlexW2065579926MaRDI QIDQ5525346

Publication date: 1966

Published in: SIAM Journal on Control (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0304034

zbMATH Keywords

mathematical logic

Related Items

The theory of languages ⋮ Sur la structure des langages algébriques ⋮ Unnamed Item ⋮ Context-free graph languages of bounded degree are generated by apex graph grammars ⋮ Conjunctive grammars and alternating pushdown automata ⋮ Finite turns and the regular closure of linear context-free languages ⋮ On reversal bounded alternating Turing machines ⋮ The theory of languages ⋮ Boosting Reversible Pushdown Machines by Preprocessing ⋮ Parallel complexity of logical query programs ⋮ Weightreducing grammars and ultralinear languages ⋮ On a complexity hierarchy between L and NL ⋮ Syntax checking either way ⋮ Families of languages defined by ciliate bio-operations ⋮ Familles de langages fermées par crochet ouvert ⋮ Unnamed Item ⋮ Characterization and closure properties of linear \(\omega\)-languages ⋮ A polynomial algorithm testing partial confluence of basic semi-Thue systems ⋮ Descriptional complexity of bounded context-free languages ⋮ Streaming algorithms for language recognition problems ⋮ Unnamed Item ⋮ On recursion in ETOL systems ⋮ The characterization of parallel ultralinear grammars by rational power series ⋮ Weighted iterated linear control ⋮ Decidable subcases of the equivalence problem for recursive program schemes ⋮ Formal grammars for turn-bounded deterministic context-free languages ⋮ Queue Automata: Foundations and Developments ⋮ Iterated linear control and iterated one-turn pushdowns ⋮ Synchronizing deterministic push-down automata can be really hard ⋮ Unnamed Item ⋮ Look-ahead removal for total deterministic top-down tree transducers ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A pushdown automaton or a context-free grammar - which is more economical? ⋮ Quasi-rocking real-time pushdown automata ⋮ Kernels of Sub-classes of Context-Free Languages ⋮ Nonuniform complexity and the randomness of certain complete languages ⋮ Unnamed Item ⋮ Relationships between bounded languages, counter machines, finite-index grammars, ambiguity, and commutative regularity ⋮ State grammars with stores ⋮ The complexity of ranking simple languages ⋮ On languages with a certain prefix property ⋮ The decidability of a mapping problem for generalized sequential machines with final states ⋮ One counter languages and the IRS condition ⋮ Deep pushdown automata ⋮ Reversal-bounded multipushdown machines ⋮ Familles de langages translatables et fermées par crochet ⋮ Simple context-free languages and free monadic recursion schemes ⋮ Syntax checking either way ⋮ Uniformly erasable AFL ⋮ Context-free grammar forms ⋮ Comparing language operations ⋮ A polynomial algorithm testing partial confluence of basic semi-Thue systems ⋮ Some uniformly erasable families of languages ⋮ Unnamed Item ⋮ Basic tree transducers ⋮ Control sets on context-free grammar forms ⋮ One way finite visit automata ⋮ On equivalence and subclass containment problems for deterministic context-free languages ⋮ Compelled operations and operations of degreeP ⋮ The complexity of the membership problem for some extensions of context-free languagest† ⋮ Derivation-bounded languages ⋮ Abstract families of context-free grammars ⋮ Principal AFL ⋮ Syntactic operators on full semiAFLs ⋮ A characterization of context-free languages ⋮ A PUMPING CONDITION FOR ULTRALINEAR LANGUAGES ⋮ Finite-turn checking automata ⋮ Substitution and bounded languages ⋮ Linear graph grammars: Power and complexity ⋮ On the power of deep pushdown stacks ⋮ Ambiguity and decision problems for local adjunct languages ⋮ Even linear simple matrix languages: formal language properties and grammatical inference. ⋮ Deterministic input-driven queue automata: finite turns, decidability, and closure properties