DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2009 · 27 citations · 17 references
ComputingComputer ScienceMathematicsAlgorithmsTheory Of ComputationAmbiguity ResolutionAutomata TheoryFinite AutomataFinite-state MachinesModel TheoryAutomata EquivalenceAutomata-based Equivalence CheckingAutomata-theoretic CharacterizationsFinite Automata Theory
This paper solves the unambiguity and the sequentiality problem for polynomially ambiguous min-plus automata. This result is proved through a decidable algebraic characterization involving so-called metatransitions and an application of results from the structure theory of finite semigroups. It is noteworthy that the equivalence problem is known to be undecidable for polynomially ambiguous automata.
17