Journal article icon

Journal article

First-order orbit queries

Abstract:

Orbit Problems are a class of fundamental reachability questions that arise in the analysis of discrete-time linear dynamical systems such as automata, Markov chains, recurrence sequences, and linear while loops. Instances of the problem comprise a dimension π‘‘βˆˆβ„•, a square matrix π΄βˆˆβ„šπ‘‘Γ—π‘‘, and a query regarding the behaviour of some sets under repeated applications of A. For instance, in the Semialgebraic Orbit Problem, we are given semialgebraic source and target sets 𝑆,π‘‡βŠ†β„π‘‘, and the query is w...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1007/s00224-020-09976-7

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Oxford college:
St John's College
Role:
Author
More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
More from this funder
Name:
European Commission
Grant:
648701
Publisher:
Springer
Journal:
Theory of Computing Systems More from this journal
Volume:
65
Issue:
4
Pages:
638-661
Publication date:
2020-04-04
Acceptance date:
2020-02-24
DOI:
EISSN:
1433-0490
ISSN:
1432-4350
Language:
English
Keywords:
Pubs id:
1093165
Local pid:
pubs:1093165
Deposit date:
2020-03-12

Terms of use


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