An Extension of Parikh's Theorem beyond Idempotence

Details An Extension of Parikh's Theorem beyond Idempotence An Extension of Parikh's Theorem beyond Idempotence

2011-12-13

arxiv.org/abs/1112.2864v2

Computer Science

Formal Languages and Automata Theory

Scientific paper

The commutative ambiguity of a context-free grammar G assigns to each Parikh vector v the number of distinct leftmost derivations yielding a word with Parikh vector v. Based on the results on the generalization of Newton's method to omega-continuous semirings, we show how to approximate the commutative ambiguity by means of rational formal power series, and give a lower bound on the convergence speed of these approximations. From the latter result we deduce that the commutative ambiguity itself is rational modulo the generalized idempotence identity k=k+1 (for k some positive integer), and, subsequently, that it can be represented as a weighted sum of linear sets. This extends Parikh's well-known result that the commutative image of context-free languages is semilinear (k=1). Based on the well-known relationship between context-free grammars and algebraic systems over semirings, our results extend the work by Green et al. on the computation of the provenance of Datalog queries over commutative omega-continuous semirings.

Affiliated with

Also associated with

No associations

Rating

An Extension of Parikh's Theorem beyond Idempotence 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 An Extension of Parikh's Theorem beyond Idempotence, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Extension of Parikh's Theorem beyond Idempotence will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-486543