The Library
The complexity of regular abstractions of one-counter languages
Tools
Atig, Mohamed Faouzi, Chistikov, Dmitry, Hofman, Piotr, Kumar, K. Narayan, Saivasan, Prakash and Zetzsche, Georg (2016) The complexity of regular abstractions of one-counter languages. In: 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), New York City, USA, 5–8 Jul 2016. Published in: LICS '16 Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science pp. 207-216. ISBN 9781450343916 . doi:10.1145/2933575.2934561
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1145/2933575.2934561
Abstract
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.
Item Type: | Conference Item (Paper) | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Journal or Publication Title: | LICS '16 Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science | ||||
Publisher: | ACM | ||||
ISBN: | 9781450343916 | ||||
Book Title: | Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science - LICS '16 | ||||
Official Date: | 5 July 2016 | ||||
Dates: |
|
||||
Page Range: | pp. 207-216 | ||||
DOI: | 10.1145/2933575.2934561 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) | ||||
Type of Event: | Conference | ||||
Location of Event: | New York City, USA | ||||
Date(s) of Event: | 5–8 Jul 2016 | ||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |