Conference item icon

Conference item

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 ⊆ R d , i.e., sets that are stable under A and contain x and not y, thereby providing compact and versatile certificates of non-reachabilit...

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

Actions


Access Document


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

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
More by this author
Institution:
University of Oxford
Oxford college:
St John's College
Role:
Author
More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
Publisher:
Schloss Dagstuhl Publisher's website
Volume:
66
Pages:
29:1-29:13
Series:
Leibniz International Proceedings in Informatics
Host title:
34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Publication date:
2017-01-01
Acceptance date:
2017-01-08
DOI:
ISSN:
1868-8969
Source identifiers:
668647
ISBN:
9783959770286
Keywords:
Pubs id:
pubs:668647
UUID:
uuid:1f0cfb5a-f0d9-4858-9d63-8878effe024a
Local pid:
pubs:668647
Deposit date:
2017-01-09

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