Efficient analysis of unambiguous automata using matrix semigroup techniques

DOI10.4230/LIPICS.MFCS.2019.82MaRDI QIDQ5092446zbMATH OpenFDO

Authors Stefan Kiefer, Cas Widdershoven

Publication date 21 July 2022

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

zbMATH Keywords

algorithmsautomataMarkov chainsmatrix semigroups

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Markov chains and unambiguous Büchi automata
• scientific article; zbMATH DE number 1512707
• Unambiguous Büchi automata.
• On finitely ambiguous Büchi automata
• Complementation, Disambiguation, and Determinization of Büchi Automata Unified

Cites work

• A Polynomial-Time Algorithm for the Equivalence of Probabilistic Automata
• Accuracy and Stability of Numerical Algorithms
• Automata, logics, and infinite games. A guide to current research
• Computer Aided Verification
• Depth-First Search and Linear Graph Algorithms
• Generalized matrix inversion is not harder than matrix multiplication
• scientific article; zbMATH DE number 734901 (Why is no real title available?)
• scientific article; zbMATH DE number 846904 (Why is no real title available?)
• scientific article; zbMATH DE number 5585443 (Why is no real title available?)
• LATIN 2004: Theoretical Informatics
• Markov chains and unambiguous Büchi automata
• Matrix semigroups with constant spectral radius
• Powers of tensors and fast matrix multiplication
• The complexity of probabilistic verification
• The generalised inverse
• Triangular Factorization and Inversion by Fast Matrix Multiplication

Cited in

(3)

• Semi-tensor product of matrices approach to reachability of finite automata with application to language recognition
• Image-binary automata
• Efficiently computing the minimum rank of a matrix in a monoid of zero-one matrices

This page was built for publication: Efficient analysis of unambiguous automata using matrix semigroup techniques

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