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
Version:
Publisher's version

Actions


Access Document


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

Authors


More by this author
Department:
Oxford, MPLS, Computer Science
Ohlmann, P More by this author
More by this author
Department:
St Johns College
More by this author
Department:
Oxford, MPLS, Computer Science
More by this author
Department:
Oxford, MPLS, Computer Science
Publisher:
Schloss Dagstuhl Publisher's website
Volume:
66
Pages:
29:1-29:13
Series:
Leibniz International Proceedings in Informatics
Publication date:
2017
Acceptance date:
2017-01-08
DOI:
ISSN:
1868-8969
Pubs id:
pubs:668647
URN:
uri:1f0cfb5a-f0d9-4858-9d63-8878effe024a
UUID:
uuid:1f0cfb5a-f0d9-4858-9d63-8878effe024a
Local pid:
pubs:668647
ISBN:
978-3-95977-028-6

Terms of use


Metrics



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

TO TOP