Reference:

Michael Luttenberger. An extension of Parikh's theorem beyond idempotence. Technical report, Technische Universität München, Institut für Informatik, December 2011.

Abstract:

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.

Suggested BibTeX entry:

@techreport{ParikhExt,
    author = {Michael Luttenberger},
    institution = {Technische Universit\"{a}t M\"{u}nchen, Institut f\"{u}r Informatik},
    month = {December},
    title = {An Extension of {P}arikh's Theorem beyond Idempotence},
    year = {2011}
}