Diving into the queue

DOI10.1051/ita/2018009zbMath1423.68243OpenAlexW2909534413MaRDI QIDQ5223609

Matthias Wendlandt, Martin Kutrib, Simon Beier, Andreas Malcher

Publication date: 18 July 2019

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1051/ita/2018009

zbMATH Keywords

formal languagesdecidability questionsqueue automatalogspace Turing machines

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Queue Automata: Foundations and Developments

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity of multi-head finite automata: origins and directions
• A shrinking lemma for indexed languages
• On the intersection of stacks and queues
• QRT FIFO automata, breadth-first grammars and their relations
• Growing context-sensitive languages and Church-Rosser languages
• Reversible pushdown automata
• On the descriptional power of heads, counters, and pebbles
• Deterministic input-driven queue automata: finite turns, decidability, and closure properties
• Über einen Automaten mit Pufferspeicherung
• On non-determinacy in simple computing devices
• Input-Driven Queue Automata with Internal Transductions
• Church-Rosser Thue systems and formal languages
• Reversible Queue Automata
• Queue Automata: Foundations and Developments
• Intercalation theorems for stack languages
• Stack automata and compiling
• One-way stack automata
• Indexed Grammars—An Extension of Context-Free Grammars
• Nested Stack Automata