First-order orbit queries

DOI10.1007/S00224-020-09976-7OpenAlexW3014334551MaRDI QIDQ2048201FDOQ2048201

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Algorithms in real algebraic geometry
• Title not available (Why is that?)
• Computing polynomial program invariants
• Title not available (Why is that?)
• Polynomial-time algorithm for the orbit problem
• Logarithmic forms and group varieties.
• Structure and randomness. Pages from year one of a mathematical blog
• Optimal and nearly optimal algorithms for approximating polynomial zeros
• 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
• Symbolic reachability computation for families of linear vector fields
• Occurrence of zero in a linear recursive sequence
• Title not available (Why is that?)
• Ultimate positivity is decidable for simple linear recurrence sequences
• Title not available (Why is that?)
• On the complexity of the orbit problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• The polyhedron-hitting problem

Cited In (4)

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

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)