Journal article icon

Journal article

Semialgebraic invariant synthesis for the Kannan-Lipton orbit problem

Abstract:

The Orbit Problem consists of determining, given a linear transformation A on Qd, together with vectors x and y, whether the orbit of x under repeated applications of A can ever reach y. This problem was famously shown to be decidable by Kannan and Lipton in the 1980s.


In this paper, we are concerned with the problem of synthesising suitable invariants P ⊆ Rd, i.e., sets that are stable under A and contain x and not y, thereby providing compact and versatile certificates of no...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Publisher's version

Actions


Access Document


Files:
Publisher copy:
10.4230/LIPIcs.STACS.2017.29

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
Role:
Author
More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Computer Science
Oxford college:
Green Templeton College; Green Templeton College
Role:
Author
Publisher:
Schloss Dagstuhl Publisher's website
Journal:
34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) Journal website
Publication date:
2017-02-24
Acceptance date:
2016-12-12
DOI:
Pubs id:
pubs:832267
URN:
uri:13335453-b6fc-4ad1-a181-dcc76f0314b4
UUID:
uuid:13335453-b6fc-4ad1-a181-dcc76f0314b4
Local pid:
pubs:832267

Terms of use


Metrics


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