On the Complexity of Equivalence and Minimisation for Q-weighted Automata

DOI10.2168/LMCS-9(1:8)2013zbMath1260.68207arXiv1302.2818MaRDI QIDQ4913771

Stefan Kiefer, Björn Wachter, Andrzej S. Murawski, Joël Ouaknine, James Worrell

Publication date: 9 April 2013

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

weighted automataequivalence checkingpolynomial identity testingminimisation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (9)

Integer weighted automata on infinite words ⋮ Complexity of Equivalence and Learning for Multiplicity Tree Automata ⋮ Stochastization of Weighted Automata ⋮ Minimisation of Multiplicity Tree Automata ⋮ Complexity of regular functions ⋮ Integer Weighted Automata on Infinite Words ⋮ The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete ⋮ Unnamed Item ⋮ Derandomizing Isolation in Space-Bounded Settings

This page was built for publication: On the Complexity of Equivalence and Minimisation for Q-weighted Automata