Complexity in Prefix-Free Regular Languages

Details Complexity in Prefix-Free Regular Languages Complexity in Prefix-Free Regular Languages

2010-08-10

arxiv.org/abs/1008.1662v1

EPTCS 31, 2010, pp. 197-204

Computer Science

Formal Languages and Automata Theory

In Proceedings DCFS 2010, arXiv:1008.1270

Scientific paper

10.4204/EPTCS.31.22

We examine deterministic and nondeterministic state complexities of regular operations on prefix-free languages. We strengthen several results by providing witness languages over smaller alphabets, usually as small as possible. We next provide the tight bounds on state complexity of symmetric difference, and deterministic and nondeterministic state complexity of difference and cyclic shift of prefix-free languages.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-583297