Intercalation theorems for stack languages

DOI10.1145/800169.805419MaRDI QIDQ5402503zbMATH OpenOpenAlexFDO

Authors William F. Ogden

Publication date 14 March 2014

Published in Proceedings of the first annual ACM symposium on Theory of computing - STOC '69 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/800169.805419

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cited in

(28)

• One-way weak-stack-counter automata
• Iteration theorems for families of strict deterministic languages
• Two iteration theorems for the LL(k) languages
• 1-way stack automaton with jumps
• On derivation trees of indexed grammars - an extension of the uvwxy- theorem
• Two-way nested stack automata are equivalent to two-way stack automata
• Intercalation lemmas for tree transducer languages
• Economy of description by parsers, DPDA's, and PDA's
• Pumping lemmas for term languages
• Measures of nondeterminism for pushdown automata
• Context free normal systems and ETOL systems
• Queues, stacks, and transcendentality at the transition to chaos
• The totality problem for program schemas
• Deterministic stack transducers
• Tree-stack automata
• A Refinement of the μ-measure for Stack Programs
• Queue Automata: Foundations and Developments
• Diving into the queue
• On languages satisfying “interchange Lemma”
• Multi-stack-counter languages
• Locally finite languages
• Tree-walking-storage automata
• A shrinking lemma for indexed languages
• Deterministic tree-walking-storage automata
• Deterministic real-time tree-walking-storage automata
• Measuring the expressive power of practical regular expressions by classical stacking automata models
• Deterministic real-time tree-walking-storage automata
• Syntactic operators on full semiAFLs

This page was built for publication: Intercalation theorems for stack languages

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