Thesis
Connections between arithmetic theories and infinite-state systems
- Abstract:
-
Infinite-state systems are crucial for modelling the behaviour of computer programs, concurrent processes, and reasoning about formal languages. One fundamental area of research in theoretical computer science is the study of the computational complexity of the decision problems associated with these models. Similarly, arithmetic theories, such as Presburger arithmetic, are used to model and check properties of programs such as loop invariants, and termination conditions. In 1960, Büchi managed to relate the two concepts via the notion of automaticity, the idea of using a DFA to model the solution set of a formula of Presburger arithmetic. In this thesis, we provide new results in both areas, by leveraging the relationship between them.
First, we study extensions of Semënov arithmetic, the first-order theory of the structure ⟨ N, +, 2 x ⟩. It is well-known that this theory becomes undecidable when extended with regular predicates over tuples of number strings, such as the Büchi V2-predicate. We therefore restrict ourself to the existential fragment, and prove that this theory is decidable in EXPSPACE when extended with arbitrary regular predicates, by establishing a connection to a new model of computation, a type of vector addition system with states (VASS), where we allow for affine updates on the counters.
Next, we look at the reachability problem for VASS. Existing work primarily considers the case in which both the VASS as well as the initial and target configurations are part of the input. Here, we investigate the setting in which the VASS and target configurations are fixed, and only the initial configuration is variable. We show that fixed VASS fully express arithmetic with counting on initial segments of the natural numbers. It follows that there is a very weak reduction from any fixed such number-theoretic predicate to reachability in fixed VASS where configurations are presented in unary.
Actions
Access Document
- Files:
-
-
(Preview, Dissemination version, pdf, 812.1KB, Terms of use)
-
Authors
Contributors
- Institution:
- University of Oxford
- Division:
- MPLS
- Department:
- Computer Science
- Role:
- Supervisor
- Institution:
- University of Oxford
- Division:
- MPLS
- Department:
- Computer Science
- Role:
- Supervisor
- ORCID:
- 0000-0001-9022-7599
- DOI:
- Type of award:
- DPhil
- Level of award:
- Doctoral
- Awarding institution:
- University of Oxford
- Language:
-
English
- Keywords:
- Deposit date:
-
2025-05-21
- ARK identifier:
Terms of use
- Copyright holder:
- Andrei Draghici
- Copyright date:
- 2025
If you are the owner of this record, you can report an update to it here: Report update to this record