License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2022.18
URN: urn:nbn:de:0030-drops-170812
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17081/
Go to the corresponding LIPIcs Volume Portal

Almagor, Shaull ; Yeshurun, Asaf

Determinization of One-Counter Nets

pdf-format:
LIPIcs-CONCUR-2022-18.pdf (1 MB)

Abstract

One-Counter Nets (OCNs) are finite-state automata equipped with a counter that is not allowed to become negative, but does not have zero tests. Their simplicity and close connection to various other models (e.g., VASS, Counter Machines and Pushdown Automata) make them an attractive model for studying the border of decidability for the classical decision problems.
The deterministic fragment of OCNs (DOCNs) typically admits more tractable decision problems, and while these problems and the expressive power of DOCNs have been studied, the determinization problem, namely deciding whether an OCN admits an equivalent DOCN, has not received attention.
We introduce four notions of OCN determinizability, which arise naturally due to intricacies in the model, and specifically, the interpretation of the initial counter value. We show that in general, determinizability is undecidable under most notions, but over a singleton alphabet (i.e., 1 dimensional VASS) one definition becomes decidable, and the rest become trivial, in that there is always an equivalent DOCN.

BibTeX - Entry

@InProceedings{almagor_et_al:LIPIcs.CONCUR.2022.18,
  author =	{Almagor, Shaull and Yeshurun, Asaf},
  title =	{{Determinization of One-Counter Nets}},
  booktitle =	{33rd International Conference on Concurrency Theory (CONCUR 2022)},
  pages =	{18:1--18:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-246-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{243},
  editor =	{Klin, Bartek and Lasota, S{\l}awomir and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17081},
  URN =		{urn:nbn:de:0030-drops-170812},
  doi =		{10.4230/LIPIcs.CONCUR.2022.18},
  annote =	{Keywords: Determinization, One-Counter Net, Vector Addition System, Automata, Semilinear}
}

Keywords: Determinization, One-Counter Net, Vector Addition System, Automata, Semilinear
Collection: 33rd International Conference on Concurrency Theory (CONCUR 2022)
Issue Date: 2022
Date of publication: 06.09.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI