Conference icon

Conference

The complexity of regular abstractions of one-counter languages

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...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Publisher copy:
10.1145/2933575.2934561

Authors


More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
Role:
Author
Expand authors...
Publisher:
Association for Computing Machinery Publisher's website
Pages:
207-216
Publication date:
2016-07-05
DOI:
ISSN:
1043-6871
URN:
uuid:c6573883-2497-416c-b594-af2fa4040615
Source identifiers:
635014
Local pid:
pubs:635014
ISBN:
978-1-4503-4391-6

Terms of use


Metrics


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP