Finite sequentiality of finitely ambiguous max-plus tree automata

DOI10.4230/LIPICS.ICALP.2020.137MaRDI QIDQ6842433zbMATH OpenFDO

Authors Erik Paul

Publication date 18 March 2026

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2020.137

zbMATH Keywords

decidabilityfinite ambiguityfinite sequentialitymax-plus tree automataweighted tree automata

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata
• Algorithms for determining relative star height and star height
• An efficient best-trees algorithm for weighted tree automata over the tropical semiring
• Automata that recognize intersections of free submonoids
• Coarse-to-fine natural language processing
• Comparison of max-plus automata and joint spectral radius of tropical matrices
• DECIDABILITY OF THE EQUIVALENCE PROBLEM FOR FINITELY AMBIGUOUS FINANCE AUTOMATA
• Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton
• Deciding unambiguity and sequentiality of polynomially ambiguous min-plus automata
• Determinization of weighted tree automata using factorizations
• Elements of automata theory. Translated from the French by Reuben Thomas
• Handbook of weighted automata
• scientific article; zbMATH DE number 4072419 (Why is no real title available?)
• scientific article; zbMATH DE number 41838 (Why is no real title available?)
• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 3588051 (Why is no real title available?)
• scientific article; zbMATH DE number 2040319 (Why is no real title available?)
• scientific article; zbMATH DE number 2040322 (Why is no real title available?)
• scientific article; zbMATH DE number 7354705 (Why is no real title available?)
• scientific article; zbMATH DE number 7559164 (Why is no real title available?)
• scientific article; zbMATH DE number 7204387 (Why is no real title available?)
• scientific article; zbMATH DE number 2211801 (Why is no real title available?)
• Max/Plus tree automata for termination of term rewriting
• On a problem of formal logic.
• On Context-Free Languages
• On delay and regret determinization of max-plus automata
• On finite and polynomial ambiguity of weighted tree automata
• On the definition of a family of automata
• On the degree of ambiguity of finite automata
• On the finite degree of ambiguity of finite tree automata
• Parikh's theorem: a simple and direct automaton construction
• Pumping lemmas for weighted automata
• Quantitative Monadic Second-Order Logic
• Recognizable formal power series on trees
• Solving numerical constraints
• THE EQUALITY PROBLEM FOR RATIONAL SERIES WITH MULTIPLICITIES IN THE TROPICAL SEMIRING IS UNDECIDABLE
• Unambiguous automata denoting finitely sequential functions
• Weighted automata for proving termination of string rewriting
• Weighted grammars and Kleene's theorem
• Weighted tree automata and tree transducers
• Which finitely ambiguous automata recognize finitely sequential functions? (extended abstract)

Cited in

(1)

• New techniques for universality in unambiguous register automata

This page was built for publication: Finite sequentiality of finitely ambiguous max-plus tree automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6842433)