154 citations · 947 across the 39 of their papers we have counts for
5 papers · 1 filter
Optimal Approximate Minimization of One-Letter Weighted Finite Automata
Clara Lacroce, Borja Balle, Prakash Panangaden +1
In this paper, we study the approximate minimization problem of weighted finite automata (WFAs): to compute the best possible approximation of a WFA given a bound on the number of…
Optimal Spectral-Norm Approximate Minimization of Weighted Finite Automata
Borja Balle, Clara Lacroce, Prakash Panangaden +2
We address the approximate minimization problem for weighted finite automata (WFAs) with weights in , over a one-letter alphabet: to compute the best possible approxima…
Singular value automata and approximate minimization
Borja Balle, Prakash Panangaden, Doina Precup
The present paper uses spectral theory of linear operators to construct approximately minimal realizations of weighted languages. Our new contributions are: (i) a new algorithm for…
Bisimulation Metrics for Weighted Automata
Borja Balle, Pascale Gourdeau, Prakash Panangaden
We develop a new bisimulation (pseudo)metric for weighted finite automata (WFA) that generalizes Boreale's linear bisimulation relation. Our metrics are induced by seminorms on the…
Ergodicity of Random Walks on Random DFA
Borja Balle
Given a DFA we consider the random walk that starts at the initial state and at each time step moves to a new state by taking a random transition from the current state. This paper…