On upper and lower bounds on the length of alternating towers
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F14%3A00431318" target="_blank" >RIV/67985840:_____/14:00431318 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1007/978-3-662-44522-8_27" target="_blank" >http://dx.doi.org/10.1007/978-3-662-44522-8_27</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-662-44522-8_27" target="_blank" >10.1007/978-3-662-44522-8_27</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
On upper and lower bounds on the length of alternating towers
Popis výsledku v původním jazyce
A tower between two regular languages is a sequence of strings such that all strings on odd positions belong to one of the languages, all strings on even positions belong to the other language, and each string can be embedded into the next string in thesequence. It is known that if there are towers of any length, then there also exists an infinite tower. We investigate upper and lower bounds on the length of finite towers between two regular languages with respect to the size of the automata representing the languages in the case there is no infinite tower. This problem is relevant to the separation problem of regular languages by piecewise testable languages.
Název v anglickém jazyce
On upper and lower bounds on the length of alternating towers
Popis výsledku anglicky
A tower between two regular languages is a sequence of strings such that all strings on odd positions belong to one of the languages, all strings on even positions belong to the other language, and each string can be embedded into the next string in thesequence. It is known that if there are towers of any length, then there also exists an infinite tower. We investigate upper and lower bounds on the length of finite towers between two regular languages with respect to the size of the automata representing the languages in the case there is no infinite tower. This problem is relevant to the separation problem of regular languages by piecewise testable languages.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
BA - Obecná matematika
OECD FORD obor
—
Návaznosti výsledku
Projekt
—
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2014
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
Mathematical Foundations of Computer Science 2014
ISBN
978-3-662-44521-1
ISSN
—
e-ISSN
—
Počet stran výsledku
12
Strana od-do
315-326
Název nakladatele
Springer
Místo vydání
Berlin
Místo konání akce
Budapest
Datum konání akce
25. 8. 2014
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
000349856300027