Displaying similar documents to “Parikh test sets for commutative languages”

Linear size test sets for certain commutative languages

Štěpán Holub, Juha Kortelainen (2001)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We prove that for each positive integer n , the finite commutative language E n = c ( a 1 a 2 ⋯ a n ) possesses a test set of size at most 5 n . Moreover, it is shown that each test set for E n has at least n - 1 elements. The result is then generalized to commutative languages L containing a word w such that (i) alph ( w ) = alph ( L ) ; and (ii) each symbol a ∈ alph ( L ) occurs at least twice in w if it occurs at least twice in some word of L : each such L possesses a test set of size 11 n , where n = Card ( alph ( L ) ) . The considerations rest on the analysis of some basic types...

Comparing Complexity Functions of a Language and Its Extendable Part

Arseny M. Shur (2008)

RAIRO - Theoretical Informatics and Applications

Similarity:

Right (left, two-sided) extendable part of a language consists of all words having infinitely many right (resp. left, two-sided) extensions within the language. We prove that for an arbitrary factorial language each of these parts has the same growth rate of complexity as the language itself. On the other hand, we exhibit a factorial language which grows superpolynomially, while its two-sided extendable part grows only linearly.