On the state complexity of the reverse of R- and J-trivial regular languages
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F13%3A00394009" target="_blank" >RIV/67985840:_____/13:00394009 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1007/978-3-642-39310-5_14" target="_blank" >http://dx.doi.org/10.1007/978-3-642-39310-5_14</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-642-39310-5_14" target="_blank" >10.1007/978-3-642-39310-5_14</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
On the state complexity of the reverse of R- and J-trivial regular languages
Popis výsledku v původním jazyce
The tight upper bound on the state complexity of the reverse of R-trivial and J-trivial regular languages of the state complexity n is 2^{n-1}. The witness is ternary for R-trivial regular languages and (n-1)-ary for J-trivial regular languages. In thispaper, we prove that the bound can be met neither by a binary R-trivial regular language nor by a J-trivial regular language over an (n-2)-element alphabet. We provide a characterization of tight bounds for R-trivial regular languages depending on the state complexity of the language and the size of its alphabet. We show the tight bound for J-trivial regular languages over an (n-2)-element alphabet and a few tight bounds for binary J-trivial regular languages. The case of J-trivial regular languages over an (n-k)-element alphabet, for 2.
Název v anglickém jazyce
On the state complexity of the reverse of R- and J-trivial regular languages
Popis výsledku anglicky
The tight upper bound on the state complexity of the reverse of R-trivial and J-trivial regular languages of the state complexity n is 2^{n-1}. The witness is ternary for R-trivial regular languages and (n-1)-ary for J-trivial regular languages. In thispaper, we prove that the bound can be met neither by a binary R-trivial regular language nor by a J-trivial regular language over an (n-2)-element alphabet. We provide a characterization of tight bounds for R-trivial regular languages depending on the state complexity of the language and the size of its alphabet. We show the tight bound for J-trivial regular languages over an (n-2)-element alphabet and a few tight bounds for binary J-trivial regular languages. The case of J-trivial regular languages over an (n-k)-element alphabet, for 2.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
BA - Obecná matematika
OECD FORD obor
—
Návaznosti výsledku
Projekt
<a href="/cs/project/GPP202%2F11%2FP028" target="_blank" >GPP202/11/P028: Decentralizované a koordinační supervizní řízení</a><br>
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2013
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ů
Údaje specifické pro druh výsledku
Název statě ve sborníku
Descriptional Complexity of Formal Systems 2013
ISBN
978-3-642-39309-9
ISSN
—
e-ISSN
—
Počet stran výsledku
12
Strana od-do
136-147
Název nakladatele
Springer
Místo vydání
Berlin
Místo konání akce
London
Datum konání akce
22. 7. 2013
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—