The descriptional power of queue automata of constant length
From MaRDI portal
Publication:2041686
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
Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)
Related Items
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
