On the universe, disjointness, and containment problems for simple machines
From MaRDI portal
Publication:710740
DOI10.1016/j.ic.2010.07.004zbMath1204.68120OpenAlexW2063925705MaRDI QIDQ710740
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
real-timepushdown automatacounter machinescontainment problemdisjointness problempartially blind 2-head NFApartially blind counteruniverse problem
Related Items
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