1 Search Results for "Yeshurun, Asaf"


Document
Determinization of One-Counter Nets

Authors: Shaull Almagor and Asaf Yeshurun

Published in: LIPIcs, Volume 243, 33rd International Conference on Concurrency Theory (CONCUR 2022)


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.

Cite as

Shaull Almagor and Asaf Yeshurun. Determinization of One-Counter Nets. In 33rd International Conference on Concurrency Theory (CONCUR 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 243, pp. 18:1-18:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2022.18},
  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}
}
  • Refine by Author
  • 1 Almagor, Shaull
  • 1 Yeshurun, Asaf

  • Refine by Classification
  • 1 Theory of computation → Formal languages and automata theory

  • Refine by Keyword
  • 1 Automata
  • 1 Determinization
  • 1 One-Counter Net
  • 1 Semilinear
  • 1 Vector Addition System

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail