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
Actions
Access Document
- Files:
-
-
(Version of record, pdf, 492.9KB)
-
- Publisher copy:
- 10.4230/LIPIcs.STACS.2017.29
Authors
Funding
Bibliographic Details
- 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:
- Source identifiers:
-
832267
Item Description
- Keywords:
- Pubs id:
-
pubs:832267
- UUID:
-
uuid:13335453-b6fc-4ad1-a181-dcc76f0314b4
- Local pid:
- pubs:832267
- Deposit date:
- 2018-09-05
Terms of use
- Copyright holder:
- Worrell et al
- Copyright date:
- 2017
- Notes:
- © Nathanaël Fijalkow, Pierre Ohlmann, Joël Ouaknine, Amaury Pouly, and James Worrell; licensed under Creative Commons License CC-BY
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record