Metraipolis › archive › dc_02b7cf0734ba

Parameterized Reachability for Register Machines with Data — arXiv:2610.08009

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.08009
License (as archived)
CC0-1.0
Archived
2026-10-07T15:02:21.532Z
SHA-256 of the archived text
c725da8c62637c5eedadbc918c358e81f60d3945c7e76cb1a1039acd8b0f0be4
Stable URL of this page
https://metraipolis.com/documento/dc_02b7cf0734ba

How to cite

Parameterized Reachability for Register Machines with Data — arXiv:2610.08009 — arXiv (en), https://arxiv.org/abs/2610.08009 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_02b7cf0734ba (Metraipolis archive dc_02b7cf0734ba, sha256 c725da8c62637c5eedadbc918c358e81f60d3945c7e76cb1a1039acd8b0f0be4)
BibTeX
@misc{dc02b7cf0734ba,
  title = {Parameterized Reachability for Register Machines with Data — arXiv:2610.08009},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.08009},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_02b7cf0734ba; sha256 c725da8c62637c5eedadbc918c358e81f60d3945c7e76cb1a1039acd8b0f0be4},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.08009. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We investigate the parameterized reachability problem for concurrent register machines over infinite data domains. In this framework, each machine is a program equipped with a set of local registers, the communication across machines is mediated through a set of shared registers. Both local and shared registers can take values from an infinite data domain. The program's primitive operations include copying values between registers, assigning constants, comparing registers for (dis-)equality, and nondeterministic assignments that store an arbitrary domain value into a local register. The parameterized reachability problem considers a program and a target location, asking whether there exists some n in Naturals such that an execution of n identical machines (referred to as instances) results in at least one instance reaching the specified location. We show that this problem is Pspace-complete in the general case and it becomes undecidable if a freshness assumption (i.e., each assignment must produce a unique value distinct from all constants) is applied to nondeterministic assignments. This undecidability persists even for systems restricted to two shared and two local registers. Finally, we establish optimal decidability results for two restricted settings: when each thread is limited to a single local register, or when the system utilizes only one shared register.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.FL, nuovi lavori del giorno).
Categorie arXiv: Formal Languages and Automata Theory (cs.FL).
Pagina del lavoro: https://arxiv.org/abs/2610.08009 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T14:35:28.663Z dalla pagina https://arxiv.org/list/cs.FL/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).