On the height of towers of subsequences and prefixes

DOI10.1016/J.IC.2019.01.004zbMATH Open1434.68259arXiv1705.02813OpenAlexW2614042440WikidataQ128529142 ScholiaQ128529142MaRDI QIDQ2272979FDOQ2272979

Authors: Štěpán Holub, Tomáš Masopust, Michaël Thomazo 

Publication date: 17 September 2019

Published in: Information and Computation (Search for Journal in Brave)

Abstract: 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. The height of the tower is the number of words in the sequence. If there is no infinite tower (a tower of infinite height), then the height of all towers between the languages is bounded. We study upper and lower bounds on the height of maximal finite towers with respect to the size of the NFA (the DFA) representation of the languages. 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, then, using an alphabet of size approximately 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, there is a gap between the lower and upper bound, and 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.

Full work available at URL: https://arxiv.org/abs/1705.02813

Recommendations

• On upper and lower bounds on the length of alternating towers
• Prefix-free subsets of regular languages and descriptional complexity
• The size of subsequence automaton.
• Partial orders on words, minimal elements of regular languages, and state complexity
• The size of subsequence automaton

zbMATH Keywords

lower boundsautomataupper boundslanguagessubsequencesprefixesalternating towers

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Characterizations of some classes of regular events
• Efficient separability of regular languages by subsequences and suffixes
• Ordering by Divisibility in Abstract Algebras
• On the index of Simon's congruence for piecewise testability
• Implicit operations on finite \({\mathcal J}\)-trivial semigroups and a conjecture of I. Simon
• On upper and lower bounds on the length of alternating towers
• Separating regular languages by piecewise testable and unambiguous languages
• Separability by piecewise testable languages is \textsc{PTime}-complete
• A characterization for decidable separability by piecewise testable languages
• Deciding Universality of ptNFAs is PSpace-Complete

Cited In (2)

• Testing Simon's congruence
• On upper and lower bounds on the length of alternating towers

This page was built for publication: On the height of towers of subsequences and prefixes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2272979)