One way finite visit automata
From MaRDI portal
Publication:1242687
DOI10.1016/0304-3975(78)90035-XzbMath0368.68059MaRDI QIDQ1242687
Publication date: 1978
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items
The Dyck language \(D_ 1^{'*}\) is not generated by any matrix grammar of finite index, Representations of language families by homomorphic equality operations and generalized equality sets, Equivalence problem of mappings relative to languages, Visit-bounded stack automata, Sur les générateurs algébriques et linéaires, Unnamed Item, Unnamed Item, Tree transducers, L systems, and two-way machines, Reset machines, Uniform simulations of nondeterministic real time multitape turing machines, Iterated linear control and iterated one-turn pushdowns, Independance forte de certaines opérations, The equivalence of deterministic gsm replications onQ-rational languages is decidable, 2DST mappings of languages and related problems, The string generating power of context-free hypergraph grammars, Iterated stack automata and complexity classes, Concatenation of graphs, Unnamed Item, The failure of the strong pumping lemma for multiple context-free languages, Visit-bounded stack automata, Basic tree transducers, Control sets on context-free grammar forms, Ogden's lemma, multiple context-free grammars, and the control language hierarchy, Gaining Power by Input Operations: Finite Automata and Beyond, On languages specified by relative acceptance, On two-way sequential transductions of full semi-AFL's, Some decision problems concerning sequential transducers and checking automata, The power of two-way deterministic checking stack automata, Outils et résultats pour les transducteurs boustrophédons, Three hierarchies of transducers, Even linear simple matrix languages: formal language properties and grammatical inference., Hierarchies of hyper-AFLs, A note on Parikh maps, abstract languages, and decision problems
Cites Work
- Unnamed Item
- Unnamed Item
- Syntactic operators on full semiAFLs
- A geometric hierarchy of languages
- Two-way A-transducers and AFL
- Reversal-bounded multipushdown machines
- Uniformly erasable AFL
- Control sets on context-free grammar forms
- Controlled pushdown automata
- Left-derivation bounded languages
- Checking automata and one-way stack languages
- Derivation-bounded languages
- Principal AFL
- The reduction of tape reversals for off-line one-tape Turing machines
- Finite-turn checking automata
- AFL with the semilinear property
- Absolutely parallel grammars and two-way finite-state transducers
- On AFL generators for finitely encoded AFA
- Tape-reversal bounded Turing machine computations
- On certain formal properties of grammars
- Linear Automaton Transformations
- Stack Machines and Classes of Nonnested Macro Languages
- Bounded-crossing transducers
- Control sets on linear grammars
- A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
- Simple Representations of Certain Classes of Languages
- The complexity of the membership problem for some extensions of context-free languagest†
- On Relations Defined by Generalized Finite Automata
- Finite-Turn Pushdown Automata
- On Context-Free Languages
- Control sets on grammars
- On equal matrix languages
- An Infinite Hierarchy of Context-Free Languages
- Quasi-realtime languages
- Studies in abstract families of languages
- Chains of full AFL's
- Two-way sequential transductions and stack automata
- Phrase structure languages, finite machines, and channel capacity