Complexity of Problems for Commutative Grammars

Details Complexity of Problems for Commutative Grammars Complexity of Problems for Commutative Grammars

2010-03-22

arxiv.org/abs/1003.4105v1

Computer Science

Formal Languages and Automata Theory

Full version of submission to LICS 2010

Scientific paper

We consider Parikh images of languages accepted by non-deterministic finite automata and context-free grammars; in other words, we treat the languages in a commutative way --- we do not care about the order of letters in the accepted word, but rather how many times each one of them appears. In most cases we assume that the alphabet is of fixed size. We show tight complexity bounds for problems like membership, equivalence, and disjointness. In particular, we show polynomial algorithms for membership and disjointness for Parikh images of non-deterministic finite automata over fixed alphabet, and we show that equivalence is Pi2P complete for context-free grammars over fixed terminal alphabet.

Affiliated with

Also associated with

No associations

Rating

Complexity of Problems for Commutative Grammars 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 of Problems for Commutative Grammars, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexity of Problems for Commutative Grammars will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-206220