Some decision problems concerning sequential transducers and checking automata

DOI10.1016/0022-0000(79)90049-7MaRDI QIDQ1256855zbMATH OpenOpenAlexFDO

Authors 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 ProblemsCascade Products of Pushdown AutomataChecking AutomataTwo-Way Sequential Transducers

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Decidability of theories and sets of sentences (03B25)

Cites work

• scientific article; zbMATH DE number 3254905 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Absolutely parallel grammars and two-way finite-state transducers
• Bounded Algol-Like Languages
• Checking automata and one-way stack languages
• Deterministic one-counter automata
• Direct or cascade product of pushdown automata
• On Context-Free Languages
• On two-way sequential transductions of full semi-AFL's
• One way finite visit automata
• One-way stack automata
• 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
• The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
• Two-way sequential transductions and stack automata

Cited in

(1)

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

Describes a project that uses

Uses Software

• ALGOL 60

This page was built for publication: Some decision problems concerning sequential transducers and checking automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1256855)