On the universe, disjointness, and containment problems for simple machines

DOI10.1016/j.ic.2010.07.004zbMath1204.68120OpenAlexW2063925705MaRDI QIDQ710740

Oscar H. Ibarra

Publication date: 22 October 2010

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2010.07.004

zbMATH Keywords

real-timepushdown automatacounter machinescontainment problemdisjointness problempartially blind 2-head NFApartially blind counteruniverse problem

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

On the containment and equivalence problems for two-way transducers

Cites Work

• Unnamed Item
• Unnamed Item
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• On a complexity hierarchy between L and NL
• Reversal-bounded multipushdown machines
• Complete formal systems for equivalence problems
• On partially blind multihead finite automata.
• Restricted one-counter machines with undecidable universe problems
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• An Infinite Hierarchy of Context-Free Languages