2004
Regular solutions of language inequalities and well quasi-orders
KUNC, MichalZákladní údaje
Originální název
Regular solutions of language inequalities and well quasi-orders
Název česky
Regulární řešení jazykových nerovnic a dobrá kvaziuspořádání
Autoři
Vydání
Heidelberg, Automata, Languages and Programming: 31st International Colloquium, ICALP 2004, Turku, Finland, July 12-16, 2004. Proceedings, s. 870-881, 2004
Nakladatel
Springer-Verlag
Další údaje
Jazyk
angličtina
Typ výsledku
Stať ve sborníku
Obor
10101 Pure mathematics
Stát vydavatele
Německo
Utajení
není předmětem státního či obchodního tajemství
Odkazy
Označené pro přenos do RIV
Ano
Kód RIV
RIV/00216224:14310/04:00011502
Organizační jednotka
Přírodovědecká fakulta
ISBN
3-540-22849-7
UT WoS
000223656400073
Klíčová slova anglicky
Language equation; Regular language; Well quasi-order; Syntactic semigroup; Finite simple semigroup
Štítky
Změněno: 23. 1. 2006 15:24, doc. Mgr. Michal Kunc, Ph.D.
V originále
By means of constructing suitable well quasi-orders of free monoids we prove that all maximal solutions of certain systems of language inequalities are regular. This way we deal with a wide class of systems of inequalities where all constants are languages recognized by finite simple semigroups. In a similar manner we also demonstrate that the largest solution of the inequality XK subset LX is regular provided the language L is regular.
Česky
Pomocí vhodných dobrých kvaziuspořádání volných monoidů dokazujeme, že všechna maximální řešení jistých systémů jazykových nerovnic jsou regulární. Touto cestou řešíme rozsáhlou třídu systémů nerovnic, v nichž jsou všechny konstanty jazyky rozpoznávané konečnými jednoduchými pologrupami. Podobným způsobem rovněž ukazujeme, že největší řešení nerovnice XK podmnožina LX je regulární za předpokladu, že jazyk L je regulární.
Návaznosti
| GA201/01/0323, projekt VaV |
|