On the Containment and Equivalence Problems for GSMs, Transducers, and Linear CFGs

DOI10.1007/978-3-642-22256-6_18zbMath1297.68139OpenAlexW1566937480MaRDI QIDQ5200064

Oscar H. Ibarra

Publication date: 29 July 2011

Published in: Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22256-6_18

zbMATH Keywords

finite transducerequivalence problemcontainment problempushdown transducergeneralized sequential machinelinear context-free grammar

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Cites Work

• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• The equivalence of finite valued transducers (on HDT0L languages) is decidable
• On the valuedness of finite transducers
• Reversal-bounded multipushdown machines
• A note on finite-valued and finitely ambiguous transducers
• Decomposing Finite-Valued Transducers and Deciding Their Equivalence
• 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

This page was built for publication: On the Containment and Equivalence Problems for GSMs, Transducers, and Linear CFGs