The descriptional power of queue automata of constant length

DOI10.1007/s00236-021-00398-7OpenAlexW3184073115MaRDI QIDQ2041686

Katja Meckel, Sebastian Jakobi, Beatrice Palano, Carlo Mereghetti

Publication date: 23 July 2021

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00236-021-00398-7

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Related Items

Unnamed Item ⋮ Characterization of tree automata based on quantum logic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The size-cost of Boolean operations on constant height deterministic pushdown automata
• Descriptional complexity of two-way pushdown automata with restricted head reversals
• Quantum finite automata: advances on Bertoni's ideas
• More concise representation of regular languages by automata and regular expressions
• Finite automata and unary languages
• QRT FIFO automata, breadth-first grammars and their relations
• Iterated uniform finite-state transducers: descriptional complexity of nondeterminism and two-way motion
• Removing nondeterminism in constant height pushdown automata
• Deterministic input-driven queue automata: finite turns, decidability, and closure properties
• Boolean language operations on nondeterministic automata with a pushdown of constant height
• Quantum automata for some multiperiodic languages
• Optimal Simulations between Unary Automata
• Queue Automata of Constant Length
• Complexity of Promise Problems on Classical and Quantum Automata
• Behaviours of Unary Quantum Automata
• On the Power of One-Way Automata with Quantum and Classical States
• TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE
• Boolean Language Operations on Nondeterministic Automata with a Pushdown of Constant Height
• GOLOMB RULERS AND DIFFERENCE SETS FOR SUCCINCT QUANTUM AUTOMATA
• Descriptional complexity of iterated uniform finite-state transducers
• Trace monoids with idempotent generators and measure-only quantum automata