Syntactic semiring and language equations

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14310%2F03%3A00009485" target="_blank" >RIV/00216224:14310/03:00009485 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Syntactic semiring and language equations
Original language description
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 transformationsof a certain modification of the minimal automaton for L. The main issue here are the inequalities r(x1,...,xm) =< L and equations r(x1,...,xm) = L where L is a given regular language over a finite alphabet A and r is a given regular expression over A invariables x1,...,xm. 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, thelast 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.
Czech name
—
Czech description
—

Publication year
2003
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Proc. of the Seventh International Conference on Implementation and Application of Automata
ISBN
3-540-40391-4
ISSN
—
e-ISSN
—
Number of pages
12
Pages from-to
182-193
Publisher name
Springer
Place of publication
Berlin
Event location
Tours (Francie)
Event date
Jan 1, 2002
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)