Partial orders on words, minimal elements of regular languages, and state complexity

Research output: Contribution to journalArticle

71 Scopus citations

Abstract

The classical partial orders on strings (prefix, suffix, subsegment, subsequence, lexical, and dictionary order) can be generalized to the case where the alphabet itself has a partial order. This was done by Higman for the subsequence order, and by Kundu for the prefix order. Higman proved that for any language L, the set MIN(L) of minimal elements in L with respect to the generalized subsequence order is finite. Kundu proved that for any regular language L, the set MIN(L) of minimal elements in L with respect to the generalized prefix order is also regular. Here we extend his result to the other orders and give upper bounds for the number of states of the finite automata recognizing MIN(L). The main contribution of this paper, however, is the proof of lower bounds. The upper bounds are shown to be tight; in particular, if L is recognized by a deterministic finite automaton with n states then any deterministic (or even nondeterministic) finite automaton recognizing MIN(L) needs exponentially many states in n; here, MIN is taken with respect to a generalized prefix, suffix, or subsegment order (with a partially ordered alphabet of 4 letters, whose Hasse diagram contains just one edge) or with respect to the ordinary subsequence order. We also give a new proof of a theorem of Sakoda and Sipser about the complementation of nondeterministic finite automata.

Original languageEnglish (US)
Pages (from-to)267-291
Number of pages25
JournalTheoretical Computer Science
Volume119
Issue number2
DOIs
StatePublished - Oct 25 1993
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Partial orders on words, minimal elements of regular languages, and state complexity'. Together they form a unique fingerprint.

  • Cite this