First-order orbit queries

DOI10.1007/S00224-020-09976-7MaRDI QIDQ2048201zbMATH OpenOpenAlexFDO

Authors Shaull Almagor, James Worrell, Joël Ouaknine

Publication date 5 August 2021

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://ora.ox.ac.uk/objects/uuid:76e1f714-ee9e-4f0c-9e0b-36751280790e

zbMATH Keywords

orbit problemlinear dynamical systemsfirst-order theory of the reals

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Metric theory (11J83) Logic in computer science (03B70) Low-dimensional dynamical systems (37E99) Linear forms in logarithms; Baker's method (11J86)

Recommendations

• scientific article; zbMATH DE number 7559115
• On the complexity of the orbit problem
• The orbit problem in higher dimensions
• Polynomial-time algorithm for the orbit problem
• Complete semialgebraic invariant synthesis for the Kannan-Lipton orbit problem

Cites work

• scientific article; zbMATH DE number 3138903 (Why is no real title available?)
• scientific article; zbMATH DE number 3823893 (Why is no real title available?)
• scientific article; zbMATH DE number 3785018 (Why is no real title available?)
• scientific article; zbMATH DE number 3497890 (Why is no real title available?)
• scientific article; zbMATH DE number 7559115 (Why is no real title available?)
• scientific article; zbMATH DE number 7204476 (Why is no real title available?)
• scientific article; zbMATH DE number 3336831 (Why is no real title available?)
• scientific article; zbMATH DE number 3068536 (Why is no real title available?)
• Algorithms in real algebraic geometry
• Computing polynomial program invariants
• Logarithmic forms and group varieties.
• Occurrence of zero in a linear recursive sequence
• On the complexity of the orbit problem
• On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
• Optimal and nearly optimal algorithms for approximating polynomial zeros
• Polynomial-time algorithm for the orbit problem
• Structure and randomness. Pages from year one of a mathematical blog
• Symbolic reachability computation for families of linear vector fields
• The polyhedron-hitting problem
• Ultimate positivity is decidable for simple linear recurrence sequences

Cited in

(4)

• What's decidable about discrete linear dynamical systems?
• Complete semialgebraic invariant synthesis for the Kannan-Lipton orbit problem
• Algebraic model checking for discrete linear dynamical systems
• The polyhedron-hitting problem

This page was built for publication: First-order orbit queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2048201)