The complexity of regular abstractions of one-counter languages
2016 (English)In: Proceedings Of The 31St Annual ACM-IEEE Symposium On Logic In Computer Science (LICS 2016), 2016, 207-216 p.Conference paper (Refereed)
We study the computational and descriptional complexity of the following transformation: Given a one-counter automaton (OCA) A, construct a nondeterministic finite automaton (NFA) B that recognizes an abstraction of the language L (A) : its (1) downward closure, (2) upward closure, or (3) Parikh image. For the Parikh image over a fixed alphabet and for the upward and downward closures, we find polynomial-time algorithms that compute such an NFA. For the Parikh image with the alphabet as part of the input, we find a quasi-polynomial time algorithm and prove a completeness result: we construct a sequence of OCA that admits a polynomial-time algorithm iff there is one for all OCA. For all three abstractions, it was previously unknown whether appropriate NFA of sub-exponential size exist.
Place, publisher, year, edition, pages
2016. 207-216 p.
one-counter automata, upward closure, downward closure, Parikh image
IdentifiersURN: urn:nbn:se:uu:diva-311416DOI: 10.1145/2933575.2934561ISI: 000387609200021ISBN: 9781450343916OAI: oai:DiVA.org:uu-311416DiVA: diva2:1060009
31st Annual ACM-IEEE Symposium on Logic in Computer Science (LICS), JUL 05-08, 2016, New York City, NY