RUS  ENG
Full version
JOURNALS // Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki // Archive

Kazan. Gos. Univ. Uchen. Zap. Ser. Fiz.-Mat. Nauki, 2009 Volume 151, Book 2, Pages 80–89 (Mi uzku748)

The XV International Conference "Problems of Theoretical Cybernetics"

On a Matrix of First Moments for Decomposable Stochastic CF-Grammar

L. P. Zhiltsova

N. I. Lobachevski State University of Nizhni Novgorod

Abstract: Stochastic context-free grammar is considered which contains arbitrary number of classes of non-terminal symbols without restrictions on the succession order of classes. Corresponding matrix $A$ of first moments is decomposable. For the case when Perron's root of the matrix $A$ is strictly less than one, properties of the matrix $A^t$ are investigated under $t\to\infty$.

Keywords: algorithm, coding, compression, context-free language, grammar, optimization, automaton, probability.

UDC: 519.713

Received: 30.03.2009



© Steklov Math. Inst. of RAS, 2024