Deque automata, languages, and planar graph representations

DOI10.1016/j.tcs.2020.02.029zbMath1440.68153OpenAlexW3007743474MaRDI QIDQ2192371

Pierluigi San Pietro, Stefano Crespi Reghizzi

Publication date: 17 August 2020

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

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

zbMATH Keywords

closure propertiesAFLqueue automatadouble-ended queueDyckantiDyckcylindric planar graphsdeque graphsquasi-realtime

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Toroidal embeddings of abstractly planar graphs are knotted or linked
• Disjunctivity and other properties of sets of pseudo-bordered words
• Deque automata and a subfamily of context-sensitive languages which contains all semilinear bounded languages
• A note on: `Deque automata and a subfamily of context-sensitive languages which contains all semilinear bounded languages' (by K. Ayers)
• Automates a file
• QRT FIFO automata, breadth-first grammars and their relations
• Deque languages, automata and planar graphs
• Über einen Automaten mit Pufferspeicherung
• AFL with the semilinear property
• BREADTH AND DEPTH GRAMMARS AND DEQUE AUTOMATA
• New Real-Time Simulations of Multihead Tape Units
• Data Structures and their Planar Graph Layouts
• Queue Automata: Foundations and Developments

This page was built for publication: Deque automata, languages, and planar graph representations