LINEAR LANGUAGES OF FINITE AND INFINITE WORDS
Research supported by grant no. 77öu9 from the Austrian-Hungarian Action Foundation, the HAS-JSPS cooperative grant no. 101, and by grant no. K 75249 from the National Foundation of Hungary for Scientific Research.
A linear grammar with Büchi acceptance condition is a system
where (N, Σ, P, X0) is an ordinary linear grammar with nonterminal alphabet N, terminal alphabet Σ, productions P and start symbol X0, and R ⊆ N is a set of repeated nonterminals. Consider the set of all finite and infinite derivation trees rooted X0 whose leaves are labeled with letters of the terminal alphabet and possibly the empty word. When the tree is infinite, we require that at least one nonterminal letter in R appears infinitely often as the label of a vertex along the unique infinite branch of the tree. The frontier of such a tree determines a finite or infinite word over Σ. The set of all such words is called the linear language of finite and infinite words generated by G. Using results from 1–3 we provide an algebraic characterization of linear languages by rational operations. More specifically, we associate a Conway semiring-semimodule pair (S, V) with each alphabet Σ, where S is a semiring associated with Σ and V is the set of all subsets of infinite words over Σ of appropriate order type, and show that a set in V is linear if and only if it can be generated from certain simple elements of the semiring S by the rational operations.
