Computer Science – Logic in Computer Science
Scientific paper
2010-02-07
Computer Science
Logic in Computer Science
Full version of submission to LICS 2010
Scientific paper
We show that the Parikh image of the language of an NFA with n states over an alphabet of size k can be described as a finite union of linear sets with at most k generators and total size 2^{O(k^2 log n)}, i.e., polynomial for all fixed k >= 1. Previously, it was not known whether the number of generators could be made independent of n, and best upper bounds on the total size were exponential in n. Furthermore, we give an algorithm for performing such a translation in time 2^{O(k^2 log(kn))}. Our proof exploits a previously unknown connection to the theory of convex sets, and establishes a normal form theorem for semilinear sets, which is of independent interests. To complement these results, we show that our upper bounds are tight and that the results cannot be extended to context-free languages. We give four applications: (1) a new polynomial fragment of integer programming, (2) precise complexity of membership for Parikh images of NFAs, (3) an answer to an open question about polynomial PAC-learnability of semilinear sets, and (4) an optimal algorithm for LTL model checking over discrete-timed reversal-bounded counter systems.
No associations
LandOfFree
Parikh Images of Regular Languages: Complexity and Applications 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 Parikh Images of Regular Languages: Complexity and Applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parikh Images of Regular Languages: Complexity and Applications will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-582774