QRT FIFO automata, breadth-first grammars and their relations

DOI10.1016/0304-3975(91)90053-5zbMath0745.68069OpenAlexW1971153162MaRDI QIDQ1183576

Claudio Citrini, Dino Mandrioli, Stefano Crespi Reghizzi, A. Cherubini Spoletini

Publication date: 28 June 1992

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

Full work available at URL: https://doi.org/10.1016/0304-3975(91)90053-5

zbMATH Keywords

queue automatabreadth-first context-free grammars

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items

On the decidability of the termination problem of active database systems ⋮ Fast nondeterministic recognition of context-free languages using two queues ⋮ Dynamical recognizers: real-time language recognition by analog computers ⋮ Reversible and Irreversible Computations of Deterministic Finite-State Devices ⋮ Deque automata, languages, and planar graph representations ⋮ Queue Automata: Foundations and Developments ⋮ Fair expressions and regular languages over lists ⋮ Queues, stacks, and transcendentality at the transition to chaos ⋮ QRT FIFO automata, breadth-first grammars and their relations ⋮ Compilation of the ELECTRE reactive language into finite transition systems ⋮ Self-Verifying Pushdown and Queue Automata ⋮ The descriptional power of queue automata of constant length ⋮ On computational complexity of set automata ⋮ Stack-like and queue-like dynamics in recurrent neural networks ⋮ Set Automata ⋮ Diving into the queue ⋮ The calculi of emergence: Computation, dynamics and induction ⋮ Quantum automata and quantum grammars ⋮ Boosting Reversible Pushdown and Queue Machines by Preprocessing ⋮ Deterministic input-driven queue automata: finite turns, decidability, and closure properties ⋮ Infinite Lyndon words

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the intersection of stacks and queues
• Reset machines
• Automates a file
• Multiple equality sets and Post machines
• QRT FIFO automata, breadth-first grammars and their relations
• A decidability theorem for a class of vector-addition systems
• Über einen Automaten mit Pufferspeicherung
• On Deterministic Multi-Pass Analysis
• One-way multihead writing finite automata
• k + 1 Heads Are Better than k
• Mappings of languages by two-tape devices
• Real-Time Definable Languages