Syntactic semiring and language equations

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Přírodovědeckou fakultu. Oficiální stránka publikace je na webu muni.cz.
Autoři

POLÁK Libor

Rok publikování 2002
Druh Článek ve sborníku
Konference Proc. of the Seventh International Conference on Implementation and Application of Automata
Fakulta / Pracoviště MU

Přírodovědecká fakulta

Citace
Obor Obecná matematika
Klíčová slova syntactic semiring; language equations
Popis A classical construction assigns to any language its (ordered) syntactic monoid. Recently the author defined the so-called syntactic semiring of a language. We show here that elements of the syntactic semiring of $L$ can be identified with transformations of a certain modification of the minimal automaton for $L$. The main issue here are the inequalities $r(x_1,\dots,x_m) \subseteq L$ and equations $r(x_1,\dots,x_m)=L$ where $L$ is a given regular language over a finite alphabet $A$ and $r$ is a given regular expression over $A$ in variables $x_1,\dots,x_m$. We show that the search for maximal solutions can be translated into the (finite) syntactic semiring of the language $L$. In such a way we are able to decide the solvability and to find all maximal solutions effectively. In fact, the last questions were already solved by Conway using his factors. The first advantage of our method is the complexity and the second one is that we calculate in a transparent algebraic structure.
Související projekty:

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