Informace o publikaci

Syntactic structures of regular languages

Autoři

KLÍMA Ondřej POLÁK Libor

Rok publikování 2019
Druh Článek v odborném periodiku
Časopis / Zdroj Theoretical Computer Science
Fakulta / Pracoviště MU

Přírodovědecká fakulta

Citace
www https://doi.org/10.1016/j.tcs.2019.10.020
Doi http://dx.doi.org/10.1016/j.tcs.2019.10.020
Klíčová slova Regular languages; Minimal automaton; Syntactic monoid
Popis Given a regular language, its canonical lattice automaton is defined - this is a modification of the notions of the minimal automaton and the canonical meet automaton of the language. Secondly, the concept of the syntactic lattice algebra is introduced as an analogy of the syntactic monoid and of the syntactic semiring. The above three syntactic structures are constructed as certain transformation algebras of the corresponding automata. This leads to a unified approach to the study of syntactic structures of regular languages. The basic properties of the new notions are stated, showing, among others, the minimality of the canonical lattice automaton and the minimality of the syntactic lattice algebra. Using the syntactic lattice algebra, a new characterization of the membership problem for reversible languages is given.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.

Další info