113 citations · 317 across the 70 of their papers we have counts for
6 papers · 1 filter
Nonnegativity Problems for Matrix Semigroups
Julian D'Costa, Joel Ouaknine, James Worrell
The matrix semigroup membership problem asks, given square matrices of the same dimension, whether lies in the semigroup generated by . It is…
The Monadic Theory of Toric Words
Valérie Berthé, Toghrul Karimov, Joël Ouaknine +2
For which unary predicates is the MSO theory of the structure decidable? We survey the state of the art, leadin…
Transcendence of Sturmian Numbers over an Algebraic Base
Florian Luca, Joel Ouaknine, James Worrell
We consider numbers of the form for a Sturmian sequence over a binary alp…
Skolem Meets Bateman-Horn
Florian Luca, James Maynard, Armand Noubissie +2
The Skolem Problem asks to determine whether a given integer linear recurrence sequence has a zero term. This problem arises across a wide range of topics in computer science, incl…
Multiplicity Problems on Algebraic Series and Context-Free Grammars
Nikhil Balaji, Lorenzo Clemente, Klara Nosan +2
In this paper we obtain complexity bounds for computational problems on algebraic power series over several commuting variables. The power series are specified by systems of polyno…
The Membership Problem for Hypergeometric Sequences with Quadratic Parameters
George Kenison, Klara Nosan, Mahsa Shirmohammadi +1
Hypergeometric sequences are rational-valued sequences that satisfy first-order linear recurrence relations with polynomial coefficients; that is, a hypergeometric sequence $\langl…