7 papers
Positivity of Second-Order Nearly Linearly Recurrent Sequences
Amaury Pouly, Mahsa Shirmohammadi, James Worrell
Nearly linear recurrences generalise linear recurrences and can be represented as special cases of both linear time-invariant systems in control theory and linear-constraint loops…
On the growth of hypergeometric sequences
George Kenison, Jakub Konieczny, Florian Luca +3
Hypergeometric sequences obey first-order linear recurrence relations with polynomial coefficients and are commonplace throughout the mathematical and computational sciences. For c…
Algebraic Closure of Matrix Sets Recognized by 1-VASS
Rida Ait El Manssour, Mahsa Naraghi, Mahsa Shirmohammadi +1
It is known how to compute the Zariski closure of a finitely generated monoid of matrices and, more generally, of a set of matrices specified by a regular language. This result was…
Reachability for Multi-Priced Timed Automata with Positive and Negative Rates
Andrew Scoones, Mahsa Shirmohammadi, James Worrell
Multi-priced timed automata (MPTA) are timed automata with observer variables whose derivatives can change from one location to another. Observers are write-only variables, that is…
Differential Tree Automata
Rida Ait El Manssour, Vincent Cheval, Mahsa Shirmohammadi +1
A rationally dynamically algebraic (RDA) power series is one that arises as (a component of) the solution of a system of differential equations of the form $\boldsymbol{y}' = F(\bo…
Determination Problems for Orbit Closures and Matrix Groups
Rida Ait El Manssour, George Kenison, Mahsa Shirmohammadi +2
Computational problems concerning the orbit of a point under the action of a matrix group occur throughout computer science, including in program analysis, complexity theory, quant…
On Learning Polynomial Recursive Programs
Alex Buna-Marginean, Vincent Cheval, Mahsa Shirmohammadi +1
We introduce the class of P-finite automata. These are a generalisation of weighted automata, in which the weights of transitions can depend polynomially on the length of the input…