A new pumping lemma for indexed languages, with an application to infinite words
type: Item
instance of: scholarly article
title: A new pumping lemma for indexed languages, with an application to infinite words
zbMATH Open document ID: 1358.68176
author: D. Kharzeev
published in: Information and Computation
publication date: 2016-12-22T00:00:00Z
review text: In this paper, the author proves a pumping lemma in order to characterize the infinite words determined by indexed languages. A \textit{word} is a concatenation of symbols, called \textit{letters}, taken over a set called \textit{alphabet}. A (finite or infinite) set of words is called a \textit{language}. A \textit{prefix language} is a language \(L\) such that for all \(x,y \in L\), either \(x\) is a prefix of \(y\) or \(y\) is a prefix of \(x\). Every infinite prefix language determines a single infinite word \(\alpha\), in the sense that every word in \(L\) is a prefix of \(\alpha\). It is known that if a language \(L\) is regular or context-free, then the infinite word determined by \(L\) must be ultimately periodic. This result was first proved by \textit{R. V. Book} [Math. Syst. Theory 10, 229--237 (1977; Zbl 0358.68107)] using a pumping lemma for context-free languages. The class of \textit{indexed languages} consists of the languages generated by indexed grammars. In this kind of grammars, nonterminals are augmented with stacks which can be pushed, popped, and copied to other nonterminals as the derivation proceeds. This class falls between the classes of context-free languages and context-sensitive languages in the Chomsky hierarchy and includes all of the stack automata classes and rewriting systems classes whose infinite words were characterized by the same author in previous papers [Theor. Comput. Sci. 595, 1--10 (2015; Zbl 1328.68120); LIPICS -- Leibniz Int. Proc. Inform. 24, 413--424 (2013; Zbl 1359.68179)]. The author shows that if \(L\) is an indexed language, then the infinite word \(\alpha\) determined by \(L\) is a morphic word, i.e., \(\alpha\) can be generated by iterating a morphism under a coding. Since the other direction, that every morphic word is determined by some indexed language, also holds, this implies that infinite words determined by indexed languages are exactly the morphic words.
reviewed by: Francesco Dolce
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q42
Mathematics Subject Classification ID: 68R15
zbMATH DE Number: 6668162
zbMATH Keywords: infinite words
zbMATH Keywords: indexed languages
zbMATH Keywords: prefix languages
zbMATH Keywords: morphic words
zbMATH Keywords: pumping lemma
MaRDI profile type: Publication
full work available at URL: j.ic.2016.11.002
OpenAlex ID: W2554501700
Wikidata QID: Q125051964
cites work: Indexed Grammars—An Extension of Context-Free Grammars
cites work: Nested Stack Automata
cites work: Automatic Sequences
cites work: Properties of infinite words : Recent results
cites work: On languages with a certain prefix property
cites work: Linear Orders in the Pushdown Hierarchy
cites work: ITERATIVE DEVICES GENERATING INFINITE WORDS
cites work: On proving that certain languages are not ETOL
cites work: A relationship between ETOL and EDTOL languages
cites work: A shrinking lemma for indexed languages
cites work: On derivation trees of indexed grammars - an extension of the uvwxy- theorem
cites work: Q3862379
cites work: Q4714446
cites work: Une note sur la propriété de préfixe
cites work: A pumping lemma for pushdown graphs of any level
cites work: Ogden’s Lemma for ET0L Languages
cites work: Q4140407
cites work: On Infinite Words Determined by L Systems
cites work: On Infinite Words Determined by Stack Automata.
cites work: On Infinite Words Determined by Indexed Languages
DOI: 10.1016/J.IC.2016.11.002
Recommended article: On Infinite Words Determined by Indexed Languages
Recommended article: On Infinite Words Determined by Stack Automata.
Recommended article: A shrinking lemma for indexed languages
Recommended article: Q4662840
Recommended article: Every iterated morphism yields a co-CFL
Recommended article: Decidability of periodicity for infinite words
Recommended article: On Infinite Words Determined by L Systems
Recommended article: Automata on infinite words. Ecole de Printemps d'Informatique Théorique, Le Mont Dore, May 14-18, 1984
Recommended article: Context-free languages over infinite alphabets
Recommended article: Q5317419
description: scientific article; zbMATH DE number 6668162