Syntactic semiring and language equations

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14310%2F02%3A00007312" target="_blank" >RIV/00216224:14310/02:00007312 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Syntactic semiring and language equations

Popis výsledku v původním jazyce

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 maximalsolutions 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.

Název v anglickém jazyce

Syntactic semiring and language equations

Popis výsledku anglicky

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 maximalsolutions 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.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2002

Kód důvěrnosti údajů

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

Název statě ve sborníku

Proc. of the Seventh International Conference on Implementation and Application of Automata

ISBN

—

ISSN

—

e-ISSN

—

Počet stran výsledku

10

Strana od-do

181

Název nakladatele

University of Tours

Místo vydání

Tours

Místo konání akce

July 3 - 5, 2002, Tours

Datum konání akce

1. 1. 2002

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—