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
    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

    Identifiers