Abstract: This article presents a combinatorial result on indexed languages which was inspired by an attempt to understand the structure of groups with indexed language word problem. We show that a sufficiently long word in an indexed language can be written as a product of a uniformly bounded number of terms in such a way that some proper subproduct belongs to the language.
Cites work
- scientific article; zbMATH DE number 3811868 (Why is no real title available?)
- scientific article; zbMATH DE number 3311755 (Why is no real title available?)
- Indexed Grammars—An Extension of Context-Free Grammars
- Intercalation theorems for stack languages
- Nested Stack Automata
- On derivation trees of indexed grammars - an extension of the uvwxy- theorem
Cited in
(13)- Word-mappings of level 2
- The size of Higman-Haines sets
- An approach to computing downward closures
- COMBING NILPOTENT AND POLYCYCLIC GROUPS
- Applications of L systems to group theory
- scientific article; zbMATH DE number 1870548 (Why is no real title available?)
- Queue Automata: Foundations and Developments
- On the expressive power of higher-order pushdown systems
- Diving into the queue
- 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
- Regular expressions with backreferences and lookaheads capture NLOG
- A new pumping lemma for indexed languages, with an application to infinite words
This page was built for publication: A shrinking lemma for indexed languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q671370)
