A shrinking lemma for indexed languages

DOI10.1016/0304-3975(96)00244-7zbMath0874.68168arXivmath/9509205OpenAlexW2086534829WikidataQ29392907 ScholiaQ29392907MaRDI QIDQ671370

Robert H. Gilman

Publication date: 27 February 1997

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

Full work available at URL: https://arxiv.org/abs/math/9509205

zbMATH Keywords

pumping lemmaindexed languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

An Approach to Computing Downward Closures ⋮ MULTIPLICATION TABLES AND WORD-HYPERBOLICITY IN FREE PRODUCTS OF SEMIGROUPS, MONOIDS AND GROUPS ⋮ Using \textsc{edt0l} systems to solve some equations in the solvable Baumslag-Solitar groups ⋮ Queue Automata: Foundations and Developments ⋮ Word-mappings of level 2 ⋮ Applications of L systems to group theory ⋮ The size of Higman-Haines sets ⋮ A new pumping lemma for indexed languages, with an application to infinite words ⋮ Unnamed Item ⋮ Diving into the queue ⋮ COMBING NILPOTENT AND POLYCYCLIC GROUPS

Cites Work

• Unnamed Item
• Unnamed Item
• On derivation trees of indexed grammars - an extension of the uvwxy- theorem
• Intercalation theorems for stack languages
• Indexed Grammars—An Extension of Context-Free Grammars
• Nested Stack Automata