Deterministic input-driven queue automata: finite turns, decidability, and closure properties

DOI10.1016/j.tcs.2015.01.012zbMath1312.68122OpenAlexW2013651986MaRDI QIDQ2344746

Matthias Wendlandt, Carlo Mereghetti, Andreas Malcher, Martin Kutrib, Beatrice Palano

Publication date: 18 May 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.01.012

zbMATH Keywords

closure propertiesdecidability questionsqueue automatainput-driven automatafinite turns

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (12)

Boolean language operations on nondeterministic automata with a pushdown of constant height ⋮ Input-Driven Double-Head Pushdown Automata ⋮ Queue Automata: Foundations and Developments ⋮ Sweeping input-driven pushdown automata ⋮ When input-driven pushdown automata meet reversiblity ⋮ Unnamed Item ⋮ Input-driven multi-counter automata ⋮ The descriptional power of queue automata of constant length ⋮ Descriptional complexity of iterated uniform finite-state transducers ⋮ Set Automata ⋮ Diving into the queue ⋮ Digging input-driven pushdown automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Descriptional complexity of two-way pushdown automata with restricted head reversals
• More concise representation of regular languages by automata and regular expressions
• On the intersection of stacks and queues
• Reset machines
• Multiple equality sets and Post machines
• QRT FIFO automata, breadth-first grammars and their relations
• Complete formal systems for equivalence problems
• Operator precedence and the visibly pushdown property
• Nondeterministic state complexity of nested word automata
• Operational state complexity of nested word automata
• Über einen Automaten mit Pufferspeicherung
• A Direct Construction of Finite State Automata for Pushdown Store Languages
• Queue Automata of Constant Length
• Input-Driven Stack Automata
• State Complexity of Operations on Input-Driven Pushdown Automata
• Adding nesting structure to words
• Minimizing Variants of Visibly Pushdown Automata
• Visibly pushdown languages
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• The equivalence problem for deterministic finite-turn pushdown automata
• The tree width of auxiliary storage
• Finite-Turn Pushdown Automata
• One-way stack automata
• An Infinite Hierarchy of Context-Free Languages

This page was built for publication: Deterministic input-driven queue automata: finite turns, decidability, and closure properties