2026-09-08T01:22:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26391 2026-09-05T19:41:56Z ddc:004 open_access

Decidability and Complexity Borders of Reachability Problems (Invited Talk) Zetzsche, Georg infinite-state systems pushdown vector addition systems reachability decidability complexity Reachability problems are arguably one of the most fundamental type of decision problems in the area of infinite-state system: Essentially every non-trivial decision problem involves solving reachability problems of one kind or another. Because of this, reachability has continuously received attention since the very early days of automata theory. It therefore seems worthwhile to characterize the decidability and complexity borders of reachability problems. By this we mean results that consider a family of decision problems and describe precisely where, within this family, a decidability or complexity border lies. The talk will focus on two such settings: One is about decidability, where we aim to describe the state spaces for which reachability is decidable. The other is about complexity, where we aim to describe which kinds of target sets permit polynomial-time algorithms. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Georg Zetzsche 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.2 urn:nbn:de:0030-drops-263919 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.2 eng https://creativecommons.org/licenses/by/4.0/legalcode