The Library
On history-deterministic one-counter nets
Tools
Prakash, Aditya and Thejaswini, K. S. (2023) On history-deterministic one-counter nets. In: 26th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS'23), ETAPS 2023, Paris, France, 22-27 Apr 2023. Published in: Foundations of Software Science and Computation Structures. FoSSaCS 2023 (13992). ISBN 9783031308284. doi:10.1007/978-3-031-30829-1_11
|
PDF
WRAP-foundations-of-software-science-computation-structures-FoSSaCS-2023.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (27Mb) | Preview |
|
|
PDF
WRAP-on-history-deterministic-one-counter-nets-Prakash-2023.pdf - Accepted Version - Requires a PDF viewer. Download (754Kb) | Preview |
Official URL: https://doi.org/10.1007/978-3-031-30829-1_11
Abstract
We consider the model of history-deterministic one-counter nets (OCNs). History-determinism is a property of transition systems that allows for a limited kind of non-determinism which can be resolved ‘on-the-fly’. Token games, which have been used to characterise history-determinism over various models, also characterise history-determinism over OCNs. By reducing 1-token games to simulation games, we are able to show that checking for history-determinism of OCNs is decidable. Moreover, we prove that this problem is PSPACE
-complete for a unary encoding of transitions, and EXPSPACE
-complete for a binary encoding and undecidable for one-counter automata (OCA), which are OCNs that can test for zeroes.
We then study the language properties of history-deterministic OCNs. We show that the resolvers of non-determinism for history-deterministic OCNs are eventually periodic. As a consequence, for a given history-deterministic OCN, we construct a language equivalent deterministic OCA. We also show the decidability of comparing languages of history-deterministic OCNs, such as language inclusion and language universality.
Item Type: | Conference Item (Paper) | ||||||||
---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software T Technology > TJ Mechanical engineering and machinery |
||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
Library of Congress Subject Headings (LCSH): | Robots , Petri nets, Human-computer interaction, Game theory | ||||||||
Series Name: | Lecture Notes in Computer Science ; Advanced Research in Computing and Software Science (ARCoSS) | ||||||||
Journal or Publication Title: | Foundations of Software Science and Computation Structures. FoSSaCS 2023 | ||||||||
Publisher: | Springer | ||||||||
ISBN: | 9783031308284 | ||||||||
Official Date: | 2023 | ||||||||
Dates: |
|
||||||||
Number: | 13992 | ||||||||
DOI: | 10.1007/978-3-031-30829-1_11 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||||
Description: | Edited by O. Kupferman and P. Sobocinski. |
||||||||
Date of first compliant deposit: | 9 March 2023 | ||||||||
Date of first compliant Open Access: | 9 March 2023 | ||||||||
Conference Paper Type: | Paper | ||||||||
Title of Event: | 26th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS'23), ETAPS 2023 | ||||||||
Type of Event: | Conference | ||||||||
Location of Event: | Paris, France | ||||||||
Date(s) of Event: | 22-27 Apr 2023 | ||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year