On the height of towers of subsequences and prefixes
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F19%3A00501532" target="_blank" >RIV/67985840:_____/19:00501532 - isvavai.cz</a>
Alternative codes found
RIV/00216208:11320/19:10400299 RIV/61989592:15310/19:73595711
Result on the web
<a href="http://dx.doi.org/10.1016/j.ic.2019.01.004" target="_blank" >http://dx.doi.org/10.1016/j.ic.2019.01.004</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.ic.2019.01.004" target="_blank" >10.1016/j.ic.2019.01.004</a>
Alternative languages
Result language
angličtina
Original language name
On the height of towers of subsequences and prefixes
Original language description
A tower is a sequence of words alternating between two languages in such a way that every word is a subsequence of the following word. We study upper and lower bounds on the number of words in maximal finite towers between two regular languages with respect to the size of the NFA (respectively the DFA) representation. We show that the upper bound is polynomial in the number of states and exponential in the size of the alphabet, and that it is asymptotically tight if the size of the alphabet is fixed. If the alphabet may grow with the number of states of the automata, the lower bound on the height of towers is exponential with respect to that number. In this case the asymptotically optimal bound remains an open problem. Since, in many cases, the constructed towers are sequences of prefixes, we also study towers of prefixes.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2019
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Information and Computation
ISSN
0890-5401
e-ISSN
—
Volume of the periodical
265
Issue of the periodical within the volume
April
Country of publishing house
US - UNITED STATES
Number of pages
17
Pages from-to
77-93
UT code for WoS article
000458499800004
EID of the result in the Scopus database
2-s2.0-85060521960