2026-07-24T22:06:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11603 2024-03-06T10:48:25Z ddc:004 open_access

The Well Structured Problem for Presburger Counter Machines Finkel, Alain Gupta, Ekanshdeep Well structured transition systems infinite state systems Presburger counter machines reachability coverability 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alain Finkel and Ekanshdeep Gupta 2019 Is Part Of LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2019.41 urn:nbn:de:0030-drops-116037 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.41 eng https://creativecommons.org/licenses/by/3.0/legalcode