Syntactic Complexity of Prefix-, Suffix-, Bifix-, and Factor-Free Regular Languages

Details Syntactic Complexity of Prefix-, Suffix-, Bifix-, and Factor-Free Regular Languages Syntactic Complexity of Prefix-, Suffix-, Bifix-, and Factor-Free Regular Languages

2011-03-15

arxiv.org/abs/1103.2986v2

Computer Science

Formal Languages and Automata Theory

28 pages, 6 figures, 3 tables. An earlier version of this paper was presented in: M. Holzer, M. Kutrib, G. Pighizzini, eds., 1

Scientific paper

The syntactic complexity of a regular language is the cardinality of its syntactic semigroup. The syntactic complexity of a subclass of the class of regular languages is the maximal syntactic complexity of languages in that class, taken as a function of the state complexity $n$ of these languages. We study the syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages. We prove that $n^{n-2}$ is a tight upper bound for prefix-free regular languages. We present properties of the syntactic semigroups of suffix-, bifix-, and factor-free regular languages, conjecture tight upper bounds on their size to be $(n-1)^{n-2}+(n-2)$, $(n-1)^{n-3} + (n-2)^{n-3} + (n-3)2^{n-3}$, and $(n-1)^{n-3} + (n-3)2^{n-3} + 1$, respectively, and exhibit languages with these syntactic complexities.

Affiliated with

Also associated with

No associations

Rating

Syntactic Complexity of Prefix-, Suffix-, Bifix-, and Factor-Free Regular 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 Prefix-, Suffix-, Bifix-, and Factor-Free Regular Languages, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Syntactic Complexity of Prefix-, Suffix-, Bifix-, and Factor-Free Regular Languages will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-139400