Some decision problems concerning sequential transducers and checking automata
From MaRDI portal
Publication:1256855
DOI10.1016/0022-0000(79)90049-7zbMath0404.68057MaRDI QIDQ1256855
Eitan M. Gurari, Oscar H. Ibarra
Publication date: 1979
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(79)90049-7
Decision Problems; Cascade Products of Pushdown Automata; Checking Automata; Two-Way Sequential Transducers
68Q45: Formal languages and automata
68Q70: Algebraic theory of languages and automata
03B25: Decidability of theories and sets of sentences
Related Items
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Deterministic one-counter automata
- Direct or cascade product of pushdown automata
- One way finite visit automata
- On two-way sequential transductions of full semi-AFL's
- Checking automata and one-way stack languages
- Absolutely parallel grammars and two-way finite-state transducers
- Reversal-Bounded Multicounter Machines and Their Decision Problems
- The Unsolvability of the Equivalence Problem for $\varepsilon $-Free NGSM’s with Unary Input (Output) Alphabet and Applications
- Bounded Algol-Like Languages
- On Context-Free Languages
- The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
- One-way stack automata
- Two-way sequential transductions and stack automata