Truncations of infinite matrices and algebraic series associated with some CF grammars (Q1079959)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Truncations of infinite matrices and algebraic series associated with some CF grammars |
scientific article |
Statements
Truncations of infinite matrices and algebraic series associated with some CF grammars (English)
0 references
1984
0 references
The author considers an algebraic system over \({\mathbb{R}}[x]\) of the form \(X=a_ 0(x)X^ k+a_{k-1}(x)X+a_ k(x)\), where \(a_ 0(x)\) and \(a_ k(x)\) are in x\({\mathbb{R}}[x]\) and \(a_{k-1}(x)\) in x\({\mathbb{R}}\). Using this system, an infinite-state automaton and its incidence matrix A are introduced, via Kuich's results. Let \(A_ n\) denote the \(n\times n\) northwest corner truncation of A; the author proves that the eigenvalues of the \(A_ n\) are dense in some algebraic curves. Then a new result on positive algebraic series is obtained, when the coefficients of \(a_ i(x)\) \((i=0,...,k-1,k)\) are positive. Viewing the algebraic series generated by the system as a function in the complex variable x, the author proves, using the above result on truncations, that the radius of convergence equals the least positive zero of the modified discriminant of the system. Finally, applications to context-free languages are described. The author obtains a procedure for calculating the entropy of some one-counter languages, obtaining new results along the lines of those due to Chomsky, Miller and Kuich, and he performs an asymptotic analysis of the number of grammatical strings of a given length. Other applications to Dyck and Ćukasiewicz languages are also considered.
0 references
infinite-state automaton
0 references
incidence matrix
0 references
eigenvalues
0 references
algebraic curves
0 references
positive algebraic series
0 references
context-free languages
0 references
entropy
0 references
0 references
0 references