Conference item

On affine reachability problems

Abstract:: We analyze affine reachability problems in dimensions 1 and 2. We show that the reachability problem for 1-register machines over the integers with affine updates is PSPACE-hard, hence PSPACE-complete, strengthening a result by Finkel et al. that required polynomial updates. Building on recent results on two-dimensional integer matrices, we prove NP-completeness of the mortality problem for 2-dimensional integer matrices with determinants +1 and 0. Motivated by tight connections with 1-dimensional affine reachability problems without control states, we also study the complexity of a number of reachability problems in finitely generated semigroups of 2-dimensional upper-triangular integer matrices.

Publication status:: Published

Peer review status:: Peer reviewed

Actions

Email

Email this record

Send the bibliographic details of this record to your email address.

Your Email
Please enter the email address that the record information will be sent to.

-
Your message (optional)
Please add any additional information to be included within the email.
Share
Cite

Cite this record

APA Style

Jaax, S., & Kiefer, S. (2020). On affine reachability problems. 45th International Symposium on Mathematical Foundations of Computer Science (MFCS), 170, 48:1–48:14.

MLA Style

Jaax, S, and S Kiefer. “On Affine Reachability Problems.” 45th International Symposium on Mathematical Foundations of Computer Science (MFCS), Leibniz International Proceedings in Informatics (LIPIcs), vol. 170, 2020, pp. 48:1–48:14.

Chicago Style

Jaax, S, and S Kiefer. 2020. “On Affine Reachability Problems.” In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS), 170:48:1–48:14. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl.
Print

Access Document

Files:: LIPIcs-MFCS-2020-48.pdf

(Preview, Version of record, pdf, 479.4KB, Terms of use)

Publisher copy:: 10.4230/LIPIcs.MFCS.2020.48

Publication website:: https://drops.dagstuhl.de/opus/volltexte/2020/12714/

Authors

+ Jaax, S More by this author

Role:: Author

+ Kiefer, S More by this author

Institution:: University of Oxford
Division:: MPLS
Department:: Computer Science
Sub department:: Computer Science
Oxford college:: St John's College
Role:: Author
ORCID:: 0000-0003-4173-6877

+ Royal Society More from this funder

Grant:: URF/R/180025

Publisher:: Schloss Dagstuhl
Host title:: 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Volume:: 170
Pages:: 48:1--48:14
Series:: Leibniz International Proceedings in Informatics (LIPIcs)
Publication date:: 2020-08-18
Acceptance date:: 2020-06-29
Event title:: 45th International Symposium on Mathematical Foundations of Computer Science (MFCS)
Event location:: Prague, Czech Republic
Event website:: http://mfcs.mff.cuni.cz/2020/
Event start date:: 2020-08-24
Event end date:: 2020-08-28
DOI:: 10.4230/LIPIcs.MFCS.2020.48
ISSN:: 1868-8969
ISBN:: 978-3-95977-159-7

Language:: English
Keywords:: FFR

reachability

matrix semigroups

counter machines
Pubs id:: 1119179
Local pid:: pubs:1119179
Deposit date:: 2020-07-16
ARK identifier:: ark:/29072/ora_cca1dc8e5f4f4486b4bd55ea9864ef45

Terms of use

Copyright holder:: Jaax and Kiefer
Copyright date:: 2020
Rights statement:: © Stefan Jaax and Stefan Kiefer; licensed under Creative Commons License CC-BY

Licence:: CC Attribution (CC BY)

Views and Downloads

About views and downloads

If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP