Thesis icon

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:

Authors

More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Oxford college:
St Catherine's College
Role:
Author

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


Terms of use


Views and Downloads

Views and downloads will return soon






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

TO TOP