4 citations · 20 across the 27 of their papers we have counts for
11 papers · 1 filter
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…
Learning Weighted Automata over Number Rings, Concretely and Categorically
Quentin Aristote, Sam van Gool, Daniela Petrişan +1
We develop a generic reduction procedure for active learning problems. Our approach is inspired by a recent polynomial-time reduction of the exact learning problem for weighted aut…
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…
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…
Effective Definability of the Reachability Relation in Timed Automata
Martin Fränzle, Karin Quaas, Mahsa Shirmohammadi +1
We give a new proof of the result of Comon and Jurski that the binary reachability relation of a timed automaton is definable in linear arithmetic.
On the Complexity of Value Iteration
Nikhil Balaji, Stefan Kiefer, Petr Novotný +2
Value iteration is a fundamental algorithm for solving Markov Decision Processes (MDPs). It computes the maximal -step payoff by iterating times a recurrence equation which…
Synchronizing Data Words for Register Automata
Karin Quaas, Mahsa Shirmohammadi
Register automata (RAs) are finite automata extended with a finite set of registers to store and compare data from an infinite domain. We study the concept of synchronizing data wo…
On Restricted Nonnegative Matrix Factorization
Dmitry Chistikov, Stefan Kiefer, Ines Marušić +2
Nonnegative matrix factorization (NMF) is the problem of decomposing a given nonnegative matrix into a product of a nonnegative matrix and a nonne…
The Complexity of Synchronizing Markov Decision Processes
Laurent Doyen, Thierry Massart, Mahsa Shirmohammadi
We consider Markov decision processes (MDP) as generators of sequences of probability distributions over states. A probability distribution is p-synchronizing if the probability ma…
Infinite Synchronizing Words for Probabilistic Automata (Erratum)
Laurent Doyen, Thierry Massart, Mahsa Shirmohammadi
In [1], we introduced the weakly synchronizing languages for probabilistic automata. In this report, we show that the emptiness problem of weakly synchronizing languages for probab…