On upper and lower bounds on the length of alternating towers

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
On upper and lower bounds on the length of alternating towers
Original language description
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.
Czech name
—
Czech description
—

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

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

Article name in the collection
Mathematical Foundations of Computer Science 2014
ISBN
978-3-662-44521-1
ISSN
—
e-ISSN
—
Number of pages
12
Pages from-to
315-326
Publisher name
Springer
Place of publication
Berlin
Event location
Budapest
Event date
Aug 25, 2014
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000349856300027

Similar results(10)