decision problems

It is a longstanding open problem whether there is an algorithm to decide the Positivity Problem for linear recurrence sequences (LRS) …

Hypergeometric sequences are rational-valued sequences that satisfy first-order linear recurrence relations with polynomial …

The membership and threshold problems for recurrence sequences are fundamental open decision problems in automated verification. The …

James (Ben) Worrell gave a keynote talk on algorithmic analysis of dynamical systems at the 48th ACM SIGPLAN Symposium on Principles of Programming Languages (POPL 2021). During his talk, Ben presented some of our ongoing work on inequality decision problems for low-order holonomic sequences (see here).

Given an integer linear recurrence sequence $\langle X_n \rangle$, the Skolem Problem asks to determine whether there is a natural …

Slides on minimality and positivity for second-order holonomic sequences. Variations given at Mathematical Foundations of Computer Science 2021 (MFCS, Tallinn), the joint Forsyte (TU Wien) and Institute of Science & Technology Seminar, and the Open University Dynamical Systems Seminar.

An infinite sequence $\langle u_n \rangle$ of real numbers is holonomic if it satisfies a linear recurrence relation with polynomial …

An infinite sequence $\langle u_n \rangle$ of real numbers is holonomic if it satisfies a linear recurrence relation with polynomial …

Joël Ouaknine gave an invited talk on holonomic techniques, periods, and decision problems at Foundations of Software Technology and Theoretical Computer Science conference (FSTTCS 2020). During his talk Joël presented some of our ongoing work on inequality decision problems for low-order holonomic sequences (see here).

The Markov Reachability Problem We are interested in decision problems for Markov chains and in particular, the Markov Reachability Problem. Given a stochastic matrix $K\in\mathbb{Q}^{d\times d}$ and positive $r\in\mathbb{Q}$, determine whether there exist an $n\in\mathbb{N}$ such that $K^n(1,2)=r$.