Stability and Complexity of Minimising Probabilistic Automata

DOI10.1007/978-3-662-43951-7_23MaRDI QIDQ5167844zbMATH OpenOpenAlexFDO

Authors Stefan Kiefer, Björn Wachter

Publication date 1 July 2014

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.6673

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Computing methodologies for image processing (68U10)

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.

Recommendations

• scientific article; zbMATH DE number 3862442
• scientific article; zbMATH DE number 3854424
• The quest for minimal quotients for probabilistic automata
• scientific article; zbMATH DE number 3377122
• On the Complexity of the Equivalence Problem for Probabilistic Automata
• The quest for minimal quotients for probabilistic and Markov automata
• scientific article; zbMATH DE number 20623
• On the computational complexity of approximating distributions by probabilistic automata
• The dimension of stability of stochastic automata
• scientific article; zbMATH DE number 58753

Cited in

(10)

• The quest for minimal quotients for probabilistic and Markov automata
• Equivalence checking of quantum finite-state machines
• scientific article; zbMATH DE number 3854424 (Why is no real title available?)
• scientific article; zbMATH DE number 4061424 (Why is no real title available?)
• Singular value automata and approximate minimization
• The quest for minimal quotients for probabilistic automata
• Process symmetry in probabilistic transducers
• On the complexity of minimizing probabilistic and quantum automata
• Stabilization of probabilistic finite automata based on semi-tensor product of matrices
• Generalized minimal forms of stochastic automata with periodically varying structure

This page was built for publication: Stability and Complexity of Minimising Probabilistic Automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5167844)