Quasi-rocking real-time pushdown automata

DOI10.1016/j.tcs.2011.08.029zbMath1227.68060OpenAlexW2059417750MaRDI QIDQ650904

Changwook Kim

Publication date: 7 December 2011

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

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

zbMATH Keywords

normal formsdecision propertiesreal-timepushdown automatalanguage hierarchygrammatical characterizationsquasi-rocking

Mathematics Subject Classification ID

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

Related Items

Synchronizing deterministic push-down automata can be really hard ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Boundary graph grammars with dynamic edge relabeling
• Apex graph grammars and attribute grammars
• An elementary proof of double Greibach normal form
• Context-free graph languages of bounded degree are generated by apex graph grammars
• A hierarchy of eNCE families of graph languages
• Double Greibach operator grammars
• \(L(A)=L(B)\)? decidability results from complete formal systems
• Node replacement graph languages squeezed with chains, trees, and forests
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• Turn-bounded grammars and their relation to ultralinear languages
• Deterministic context free languages
• Finite-Turn Pushdown Automata
• Quasi-realtime languages
• Efficient recognition algorithms for boundary and linear eNCE graph languages