Syntactic Complexity of Star-Free Languages

Details Syntactic Complexity of Star-Free Languages Syntactic Complexity of Star-Free Languages

2011-09-15

arxiv.org/abs/1109.3381v1

Computer Science

Formal Languages and Automata Theory

17 pages, 6 figures, 3 tables

Scientific paper

The syntactic complexity of a regular language is the cardinality of its syntactic semigroup. The syntactic complexity of a subclass of regular languages is the maximal syntactic complexity of languages in that subclass, taken as a function of the state complexity of these languages. We study the syntactic complexity of star-free regular languages, that is, languages that can be constructed from finite languages using union, complement and concatenation. We find tight upper bounds on the syntactic complexity of languages accepted by monotonic and partially monotonic automata. We introduce "nearly monotonic" automata, which accept star-free languages, and find a tight upper bound on the syntactic complexity of languages accepted by such automata. We conjecture that this bound is also an upper bound on the syntactic complexity of star-free languages.

Affiliated with

Also associated with

No associations

Rating

Syntactic Complexity of Star-Free Languages does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Syntactic Complexity of Star-Free Languages, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Syntactic Complexity of Star-Free Languages will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-673557