Quotient Complexity of Bifix-, Factor-, and Subword-Free Regular Languages

Details Quotient Complexity of Bifix-, Factor-, and Subword-Free Regular Languages Quotient Complexity of Bifix-, Factor-, and Subword-Free Regular Languages

2010-06-24

arxiv.org/abs/1006.4843v3

Computer Science

Formal Languages and Automata Theory

24 pages, 11 figures in .eepic format, 2 tables, llncs.cls style file. This version contains several new results, and Baiyu Li

Scientific paper

A language L is prefix-free if, whenever words u and v are in L and u is a prefix of v, then u=v. Suffix-, factor-, and subword-free languages are defined similarly, where "subword" means "subsequence". A language is bifix-free if it is both prefix- and suffix-free. We study the quotient complexity, more commonly known as state complexity, of operations in the classes of bifix-, factor-, and subword-free regular languages. We find tight upper bounds on the quotient complexity of intersection, union, difference, symmetric difference, concatenation, star, and reversal in these three classes of languages.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-676458