On the height of towers of subsequences and prefixes

Kód výsledku v 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>

Nalezeny alternativní kódy

RIV/00216208:11320/19:10400299 RIV/61989592:15310/19:73595711

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

On the height of towers of subsequences and prefixes

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

On the height of towers of subsequences and prefixes

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2019

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ů

Název periodika

Information and Computation

ISSN

0890-5401

e-ISSN

—

Svazek periodika

265

Číslo periodika v rámci svazku

April

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

17

Strana od-do

77-93

Kód UT WoS článku

000458499800004

EID výsledku v databázi Scopus

2-s2.0-85060521960