On the height of towers of subsequences and prefixes

DOI10.1016/J.IC.2019.01.004MaRDI QIDQ2272979zbMATH OpenOpenAlexWikidataFDO

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)

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

zbMATH Keywords

lower boundsautomataupper boundslanguagessubsequencesprefixesalternating towers

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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.

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

Cites work

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

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)