Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton

2004/08/17 by Ines Klimann, Sylvain Lombardy, Jean Mairesse +1 · 3 citations
Computer Science · Mathematics · #Advanced Algebra and Logic #Automaton #Combinatorics #Computer science #Deterministic automaton #Discrete mathematics #Logic, programming, and type systems #Mathematics #Theoretical computer science #cs.CC #semigroups and automata theory

paper · pdf · doi:10.1016/j.tcs.2004.02.049

published as Theoretical Computer Science 327, 3 (2004) 349-373

openalex publication_date 2004/08/17 · arxiv created 2007/09/26 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

Finite automata with weights in the max-plus semiring are considered. The main result is: it is decidable in an effective way whether a series that is recognized by a finitely ambiguous max-plus automaton is unambiguous, or is sequential. A collection of examples is given to illustrate the hierarchy of max-plus series with respect to ambiguity.

Cited by

• A simple algorithmic framework for disambiguation of finite automata
• Representing One Letter Weighted Automata Over the Tropical Semiring
• A Complexity Bound for Determinisation of Min-Plus Weighted Automata