Determinisation and Unambiguisation of Polynomially-Ambiguous Rational Weighted Automata

2023/10/03 by Jecker, Ismaël, Mazowiecki, Filip, Purser, David · 1 citation
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.2310.02204

Abstract

We study the determinisation and unambiguisation problems of weighted automata over the rational field: Given a weighted automaton, can we determine whether there exists an equivalent deterministic, respectively unambiguous, weighted automaton? Recent results by Bell and Smertnig show that the problem is decidable, however they do not provide any complexity bounds. We show that both problems are in PSPACE for polynomially-ambiguous weighted automata.

Cited by

• Unambiguisability and Register Minimisation of Min-Plus Models

Related

• Pumping-Like Results for Copyless Cost Register Automata and Polynomially Ambiguous Weighted Automata
• Bideterministic Weighted Automata
• Notes on Equivalence and Minimization of Weighted Automata
• Fined-Grained Complexity of Ambiguity Problems on Automata and Directed Graphs
• Computing the linear hull: Deciding Deterministic? and Unambiguous? for weighted automata over fields