License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2019.41
URN: urn:nbn:de:0030-drops-116037
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11603/
Go to the corresponding LIPIcs Volume Portal

Finkel, Alain ; Gupta, Ekanshdeep

The Well Structured Problem for Presburger Counter Machines

pdf-format:
LIPIcs-FSTTCS-2019-41.pdf (0.5 MB)

Abstract

We introduce the well structured problem as the question of whether a model (here a counter machine) is well structured (here for the usual ordering on integers). We show that it is undecidable for most of the (Presburger-defined) counter machines except for Affine VASS of dimension one. However, the strong well structured problem is decidable for all Presburger counter machines. While Affine VASS of dimension one are not, in general, well structured, we give an algorithm that computes the set of predecessors of a configuration; as a consequence this allows to decide the well structured problem for 1-Affine VASS.

BibTeX - Entry

@InProceedings{finkel_et_al:LIPIcs:2019:11603,
  author =	{Alain Finkel and Ekanshdeep Gupta},
  title =	{{The Well Structured Problem for Presburger Counter Machines}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{41:1--41:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Arkadev Chattopadhyay and Paul Gastin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2019/11603},
  URN =		{urn:nbn:de:0030-drops-116037},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.41},
  annote =	{Keywords: Well structured transition systems, infinite state systems, Presburger counter machines, reachability, coverability}
}

Keywords: Well structured transition systems, infinite state systems, Presburger counter machines, reachability, coverability
Collection: 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Issue Date: 2019
Date of publication: 04.12.2019

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