Finite sequentiality of unambiguous max-plus tree automata

DOI10.1007/s00224-020-10021-wOpenAlexW3146407687MaRDI QIDQ2048206

Erik Paul

Publication date: 5 August 2021

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-020-10021-w

zbMATH Keywords

decidabilityambiguityweighted tree automatafinite sequentialitymax-plus tree automata

Mathematics Subject Classification ID

Theory of computing (68Qxx) Generalizations (16Yxx)

Related Items (4)

Equivalence, Unambiguity, and Sequentiality of Finitely Ambiguous Max-Plus Tree Automata ⋮ Approximated determinisation of weighted tree automata ⋮ Finite ambiguity and finite sequentiality in weighted automata over fields ⋮ Ambiguity hierarchies for weighted tree automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Coarse-to-fine natural language processing
• Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton
• Decidability, undecidability, and PSPACE-completeness of the twins property in the tropical semiring
• Handbook of weighted automata
• Weighted grammars and Kleene's theorem
• Algorithms for determining relative star height and star height
• Recognizable formal power series on trees
• On the degree of ambiguity of finite automata
• Sur les rélations rationnelles entre monoides libres
• A construction on finite automata that has remained hidden
• On the finite degree of ambiguity of finite tree automata
• Squaring transducers: An efficient procedure for deciding functionality and sequentiality.
• An Efficient Best-Trees Algorithm for Weighted Tree Automata over the Tropical Semiring
• Which Finitely Ambiguous Automata Recognize Finitely Sequential Functions?
• On the definition of a family of automata
• A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata
• Automata that recognize intersections of free submonoids
• THE EQUALITY PROBLEM FOR RATIONAL SERIES WITH MULTIPLICITIES IN THE TROPICAL SEMIRING IS UNDECIDABLE
• Front Matter, Table of Contents, Preface, Conference Organization
• DECIDABILITY OF THE EQUIVALENCE PROBLEM FOR FINITELY AMBIGUOUS FINANCE AUTOMATA
• Unambiguous Automata Denoting Finitely Sequential Functions
• Weighted Automata Algorithms
• Weighted Tree Automata and Tree Transducers
• Comparison of max-plus automata and joint spectral radius of tropical matrices
• Deciding Unambiguity and Sequentiality of Polynomially Ambiguous Min-Plus Automata

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