Some decision problems concerning sequential transducers and checking automata

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

zbMATH Keywords

Decision Problems; Cascade Products of Pushdown Automata; Checking Automata; Two-Way Sequential Transducers

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q70: Algebraic theory of languages and automata

03B25: Decidability of theories and sets of sentences

Related Items

The Dyck language \(D_ 1^{'*}\) is not generated by any matrix grammar of finite index

Uses Software

• ALGOL 60

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