research
∙
04/27/2023
Multiplicity Problems on Algebraic Series and Context-Free Grammars
In this paper we obtain complexity bounds for computational problems on ...
share
research
∙
03/16/2023
The Membership Problem for Hypergeometric Sequences with Quadratic Parameters
Hypergeometric sequences are rational-valued sequences that satisfy firs...
research
∙
03/22/2022
Strategy Complexity of Reachability in Countable Stochastic 2-Player Games
We study countably infinite stochastic 2-player games with reachability ...
research
∙
02/16/2022
Identity Testing for Radical Expressions
We study the Radical Identity Testing problem (RIT): Given an algebraic ...
research
∙
02/15/2022
The Membership Problem for Hypergeometric Sequences with Rational Parameters
We investigate the Membership Problem for hypergeometric sequences: give...
research
∙
06/03/2021
On the Computation of the Algebraic Closure of Finitely Generated Groups of Matrices
We investigate the complexity of computing the Zariski closure of a fini...
research
∙
12/26/2020
Transience in Countable MDPs
The Transience objective is not to visit any state infinitely often. Whi...
research
∙
07/26/2020
Cyclotomic Identity Testing and Applications
We consider the cyclotomic identity testing (CIT) problem: given a polyn...
research
∙
07/07/2020
Strategy Complexity of Parity Objectives in Countable MDPs
We study countably infinite MDPs with parity objectives. Unlike in finit...
research
∙
09/13/2019
Controlling a Random Population is EXPTIME-hard
Bertrand et al. [1] (LMCS 2019) describe two-player zero-sum games in wh...
research
∙
02/18/2019
Coverability in 1-VASS with Disequality Tests
We show that the control-state reachability problem for one-dimensional ...
research
∙
07/13/2018
On the Complexity of Value Iteration
Value iteration is a fundamental algorithm for solving Markov Decision P...
research
∙
07/13/2018
On the Complexity of Iterative Tropical Computation with Applications to Markov Decision Processes
We study the complexity of evaluating powered functions implemented by s...
research
∙
03/05/2018