uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
The complexity of regular abstractions of one-counter languages
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
Max Planck Inst Software Syst MPI SWS, Kaiserslautern, Germany..
Univ Paris Saclay, CNRS, LSV, St Aubin, France.;Univ Paris Saclay, ENS Cachan, St Aubin, France..
Chennai Math Inst, Madras, Tamil Nadu, India..
Show others and affiliations
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)
Abstract [en]

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.
Keyword [en]
one-counter automata, upward closure, downward closure, Parikh image
National Category
Computer Science
URN: 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
Available from: 2016-12-27 Created: 2016-12-27 Last updated: 2016-12-27Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Atig, Mohamed Faouzi
By organisation
Computer Systems
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 28 hits
ReferencesLink to record
Permanent link

Direct link