Decision Problems For Convex Languages

Details Decision Problems For Convex Languages Decision Problems For Convex Languages

2008-08-14

arxiv.org/abs/0808.1928v2

Proc. LATA 2009 Conference, LNICS #5457, pp. 247-258

Computer Science

Computational Complexity

preliminary version. This version corrected one typo in Section 2.1.1, line 4

Scientific paper

10.1007/978-3-642-00982-2_21

In this paper we examine decision problems associated with various classes of convex languages, studied by Ang and Brzozowski (under the name "continuous languages"). We show that we can decide whether a given language L is prefix-, suffix-, factor-, or subword-convex in polynomial time if L is represented by a DFA, but that the problem is PSPACE-hard if L is represented by an NFA. In the case that a regular language is not convex, we prove tight upper bounds on the length of the shortest words demonstrating this fact, in terms of the number of states of an accepting DFA. Similar results are proved for some subclasses of convex languages: the prefix-, suffix-, factor-, and subword-closed languages, and the prefix-, suffix-, factor-, and subword-free languages.

Affiliated with

Also associated with

No associations

Rating

Decision Problems For Convex 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 Decision Problems For Convex Languages, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decision Problems For Convex Languages will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-584376