Conference item
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
Authors
Bibliographic Details
- Publisher:
- Association for Computing Machinery
- Host title:
- LICS '16 Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science
- Journal:
- Symposium on Logic in Computer Science More from this journal
- Pages:
- 207-216
- Publication date:
- 2016-07-05
- Acceptance date:
- 2016-04-04
- DOI:
- ISSN:
-
1043-6871
- ISBN:
- 9781450343916
Item Description
- Keywords:
- Pubs id:
-
pubs:635014
- UUID:
-
uuid:c6573883-2497-416c-b594-af2fa4040615
- Local pid:
-
pubs:635014
- Source identifiers:
-
635014
- Deposit date:
-
2016-07-22
Terms of use
- Copyright date:
- 2016
Metrics
If you are the owner of this record, you can report an update to it here: Report update to this record