




Publications  An Extension of Parikh's Theorem beyond Idempotence





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 contextfree 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 omegacontinuous 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 wellknown result that the commutative image of contextfree languages is semilinear (k=1). Based on the wellknown relationship between contextfree 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 omegacontinuous 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}
}




