4 papers
Stronger bounds on the degree of ambiguity of finite automata
Stefan Kiefer, Filip Mazowiecki, Andrew Ryzhikov +1
Ambiguity measures the number of accepting runs in nondeterministic finite automata (NFA). We consider finitely ambiguous NFA, where there exists a constant such that over ever…
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…
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…
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…