RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika // Archive

Prikl. Diskr. Mat., 2011 supplement № 4, Pages 20–21 (Mi pdm319)

Theoretical Foundations of Applied Discrete Mathematics

Algebras of languages associated with labelled graphs

E. A. Pryanichnikova

State University of Informatics and Artificial Intelligence, Donetsk, Ukraine

Abstract: In this work, we introduce a family of algebras that may serve as an effective tool for characterization of languages, that can be represented by labelled graphs, and study its properties. It is proved that the language is represented by a regular expression in considered algebras if and only if this language is associated with the labelled graph. This result is an analog of well-known Kleene's theorem for finite automata.

UDC: 519.6



© Steklov Math. Inst. of RAS, 2025