| Identifikační kód |
RIV/67985840:_____/13:00394009 |
| Název v anglickém jazyce |
On the state complexity of the reverse of R- and J-trivial regular languages |
| Druh |
D - Stať ve sborníku |
| Jazyk |
eng - angličtina |
| Obor - skupina |
B - Fyzika a matematika |
| Obor |
BA - Obecná matematika |
| Rok uplatnění |
2013 |
| Kód důvěrnosti údajů |
S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
| Počet výskytů výsledku |
2 |
| Počet tvůrců celkem |
2 |
| Počet domácích tvůrců |
1 |
| Výčet všech uvedených jednotlivých tvůrců |
Tomáš Masopust (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 7977026)
G. Jirásková (státní příslušnost: SK - Slovenská republika) |
| Popis výsledku v anglické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. |
| Klíčová slova oddělená středníkem |
state complexity; reverse; subregular languages |
| Stránka www, na které se nachází výsledek |
- |
| DOI výsledku |
10.1007/978-3-642-39310-5_14 |
| Odkaz na údaje z výzkumu |
- |