Quasi-rocking real-time pushdown automata

DOI10.1016/J.TCS.2011.08.029MaRDI QIDQ650904zbMATH OpenOpenAlexFDO

Authors 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 formsreal-timepushdown automatalanguage hierarchydecision propertiesgrammatical characterizationsquasi-rocking

Mathematics Subject Classification ID

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

Recommendations

• \(\alpha\)-grammar and quasi-deterministic pushdown automata (QDPDA) of order ``\(n\)
• Models of pushdown automata with reset
• Reversible pushdown automata
• Time varying pushdown automata
• scientific article; zbMATH DE number 1439403

Cites work

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

Cited in

(2)

• scientific article; zbMATH DE number 7559404 (Why is no real title available?)
• Synchronizing deterministic push-down automata can be really hard

This page was built for publication: Quasi-rocking real-time pushdown automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q650904)