Closures in Formal Languages: Concatenation, Separation, and Algorithms

Details Closures in Formal Languages: Concatenation, Separation, and Algorithms Closures in Formal Languages: Concatenation, Separation, and Algorithms

2009-01-23

arxiv.org/abs/0901.3763v1

Computer Science

Computational Complexity

submitted to DLT 2009

Scientific paper

We continue our study of open and closed languages. We investigate how the properties of being open and closed are preserved under concatenation. We investigate analogues, in formal languages, of the separation axioms in topological spaces; one of our main results is that there is a clopen partition separating two words if and only if the words commute. We show that we can decide in quadratic time if the language specified by a DFA is closed, but if the language is specified by an NFA, the problem is PSPACE-complete.

Affiliated with

Also associated with

No associations

Rating

Closures in Formal Languages: Concatenation, Separation, and Algorithms 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 Closures in Formal Languages: Concatenation, Separation, and Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Closures in Formal Languages: Concatenation, Separation, and Algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-66477