3 papers
cs.FL2026
Representing One Letter Weighted Automata Over the Tropical Semiring
Shaull Almagor, Ismaël Jecker, Filip Mazowiecki +3
We consider weighted automata over the tropical semiring . Recently, it was shown that determinisation is decidable; in this paper we focus on the comple…
cs.FL2026
Pumping-Like Results for Copyless Cost Register Automata and Polynomially Ambiguous Weighted Automata
Filip Mazowiecki, Antoni Puch, Daniel Smertnig
In this work we consider two rich subclasses of weighted automata over fields: polynomially ambiguous weighted automata and copyless cost register automata. Primarily we are intere…
cs.FL2025
Fine-Grained Complexity of Ambiguity Problems on Automata and Directed Graphs
Karolina Drabik, Anita Dürr, Fabian Frei +2
In the field of computational logic, two classes of finite automata are considered fundamental: deterministic and nondeterministic automata (DFAs and NFAs). In a more fine-grained…