Stability and Complexity of Minimising Probabilistic Automata

2014/04/26 by Stefan Kiefer, Kiefer, Stefan, Björn Wachter +1 · 1 citation
Computer Science · #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #Machine Learning and Algorithms #cs.FL #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1404.6673

This is the full version of an ICALP'14 paper

openalex publication_date 2014/04/26 · arxiv created 2014/05/01 · arxiv updated 2014/05/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the state-minimisation problem for weighted and probabilistic automata. We provide a numerically stable polynomial-time minimisation algorithm for weighted automata, with guaranteed bounds on the numerical error when run with floating-point arithmetic. Our algorithm can also be used for "lossy" minimisation with bounded error. We show an application in image compression. In the second part of the paper we study the complexity of the minimisation problem for probabilistic automata. We prove that the problem is NP-hard and in PSPACE, improving a recent EXPTIME-result.

Citations

• Unitary Triangularization of a Nonsymmetric Matrix

Cited by

• On Numbers of Simplicial Walks and Equivalent Canonizations for Graph Recognition

Related

• On the Efficiency of Deciding Probabilistic Automata Weak Bisimulation
• On probabilistic analog automata
• Bisimilarity of Probabilistic Pushdown Automata
• Lower bounds for the state complexity of probabilistic languages and the language of prime numbers
• Decidable Problems for Probabilistic Automata on Infinite Words