Checking automata and one-way stack languages
From MaRDI portal
Publication:2532393
DOI10.1016/S0022-0000(69)80012-7zbMath0174.02702MaRDI QIDQ2532393
Publication date: 1969
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Related Items (59)
Some decision problems concerning semilinearity and commutation. ⋮ Alternating and empty alternating auxiliary stack automata. ⋮ Unnamed Item ⋮ Space Complexity of Stack Automata Models ⋮ On pebble automata ⋮ Transducers and the decidability of independence in free monoids ⋮ Unnamed Item ⋮ Representations of language families by homomorphic equality operations and generalized equality sets ⋮ Chains of full AFL's ⋮ Visit-bounded stack automata ⋮ Familles de langages fermées par crochet ouvert ⋮ Unnamed Item ⋮ Tree transducers, L systems, and two-way machines ⋮ Tree-walking-storage automata ⋮ On counting functions and slenderness of languages ⋮ Generalizations of Checking Stack Automata: Characterizations and Hierarchies ⋮ Uniform simulations of nondeterministic real time multitape turing machines ⋮ 2DST mappings of languages and related problems ⋮ Unnamed Item ⋮ Tree-stack automata ⋮ Iterated stack automata and complexity classes ⋮ Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata ⋮ Unnamed Item ⋮ Relationships between bounded languages, counter machines, finite-index grammars, ambiguity, and commutative regularity ⋮ On languages with a certain prefix property ⋮ Two-way A-transducers and AFL ⋮ Deep pushdown automata ⋮ Visit-bounded stack automata ⋮ Uniformly erasable AFL ⋮ Bounded AFLs ⋮ Comparing language operations ⋮ Characterization theorems on abstract families of transducers ⋮ Proving containment of bounded AFL ⋮ Basic tree transducers ⋮ Variations of checking stack automata: obtaining unexpected decidability properties ⋮ Control sets on context-free grammar forms ⋮ On the complexity of formal grammars ⋮ Weighted automata with storage ⋮ Decision problems and projection languages for restricted variants of two-dimensional automata ⋮ One way finite visit automata ⋮ On two-way sequential transductions of full semi-AFL's ⋮ Stack languages and log n space ⋮ Some decision problems concerning sequential transducers and checking automata ⋮ Compelled operations and operations of degreeP ⋮ The complexity of the membership problem for some extensions of context-free languagest† ⋮ The power of two-way deterministic checking stack automata ⋮ Principal AFL ⋮ Syntactic operators on full semiAFLs ⋮ Finite-turn checking automata ⋮ Substitution and bounded languages ⋮ Outils et résultats pour les transducteurs boustrophédons ⋮ Absolutely parallel grammars and two-way finite-state transducers ⋮ On AFL generators for finitely encoded AFA ⋮ Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata ⋮ On families of full trios containing counter machine languages ⋮ Theory of formal grammars ⋮ Hierarchies of hyper-AFLs ⋮ Extended macro grammars and stack controlled machines ⋮ Space Complexity of Stack Automata Models
Cites Work
This page was built for publication: Checking automata and one-way stack languages
