Diving into the queue

DOI10.1051/ITA/2018009MaRDI QIDQ5223609zbMATH OpenOpenAlexFDO

Authors Simon Beier, Martin Kutrib, Andreas Malcher, Matthias Wendlandt

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

decidability questionsformal languageslogspace Turing machinesqueue automata

Mathematics Subject Classification ID

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

Recommendations

• The Power of the Queue
• scientific article; zbMATH DE number 3988713
• On balking from an empty queue
• On the Traffic-light Queue
• The acquisition queue
• Observing Queues Before Joining
• Cascades of queues
• Queuing with special service
• scientific article; zbMATH DE number 1472360

Cites work

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

Cited in

(2)

• Last in line
• Queue Automata: Foundations and Developments

This page was built for publication: Diving into the queue

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