Truncations of infinite matrices and algebraic series associated with some CF grammars
type: Item
instance of: scholarly article
title: Truncations of infinite matrices and algebraic series associated with some CF grammars
zbMATH Open document ID: 0598.68054
DOI: 10.1016/0304-3975(84)90035-5
author: Keisuke Uchimura
published in: Theoretical Computer Science
publication date: 1984-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 15A18
zbMATH DE Number: 3965456
zbMATH Keywords: infinite-state automaton
zbMATH Keywords: incidence matrix
zbMATH Keywords: eigenvalues
zbMATH Keywords: algebraic curves
zbMATH Keywords: positive algebraic series
zbMATH Keywords: context-free languages
zbMATH Keywords: entropy
MaRDI profile type: Publication
full work available at URL: 0304-3975(84)90035-5
OpenAlex ID: W2063523453
cites work: Q4167356
cites work: The characterization of nonexpansive grammars by rational power series
cites work: Q3943082
cites work: Q5678949
cites work: Q3859267
cites work: Q4170993
cites work: Q5541328
cites work: Q3907599
cites work: Q4079524
cites work: Q4072022
cites work: Characterization of the structure-generating functions of regular sets and the DOL growth functions
cites work: On the average depth of a prefix of the Dycklanguage \(D_ 1\).
cites work: On the entropy of context-free languages
cites work: Infinite linear systems and one counter languages
cites work: An algebraic characterization of some principal regulated rational cones
cites work: Q3853827
cites work: Frobenius Theory of Positive Operators: Comparison Theorems and Applications
cites work: Q4753589
cites work: Q5678435
cites work: Q4155837
cites work: Q3948608
cites work: Q5564847
cites work: Q5593877
cites work: Q5654838
cites work: Computing the stationary distribution for infinite Markov chains
cites work: Non-negative matrices and Markov chains. 2nd ed
cites work: A Mathematical Theory of Communication
cites work: Positive rational sequences
cites work: Properties of structure generating functions of automata and their applications for linear systems
cites work: GEOMETRIC ERGODICITY IN DENUMERABLE MARKOV CHAINS
cites work: Ergodic properties of nonnegative matrices. I
cites work: Ergodic properties of nonnegative matrices. II
description: scientific article; zbMATH DE number 3965456