THE EQUALITY PROBLEM FOR RATIONAL SERIES WITH MULTIPLICITIES IN THE TROPICAL SEMIRING IS UNDECIDABLE
From MaRDI portal
Publication:4316608
DOI10.1142/S0218196794000063zbMath0834.68058MaRDI QIDQ4316608
Publication date: 1 April 1996
Published in: International Journal of Algebra and Computation (Search for Journal in Brave)
Symbolic computation and algebraic computation (68W30) Formal languages and automata (68Q45) Decidability of theories and sets of sentences (03B25) Semirings (16Y60)
Related Items (63)
Equational theories of tropical semirings ⋮ Coalgebras for Bisimulation of Weighted Automata over Semirings ⋮ DECIDABILITY OF THE EQUIVALENCE PROBLEM FOR FINITELY AMBIGUOUS FINANCE AUTOMATA ⋮ Approximate comparison of functions computed by distance automata ⋮ Finite-valued distance automata ⋮ Weighted automata and weighted logics ⋮ Weight Assignment Logic ⋮ Weighted automata and weighted logics with discounting ⋮ Multi-Valued Reasoning about Reactive Systems ⋮ Axiomatizing rational power series over natural numbers ⋮ Coinduction in Concurrent Timed Systems ⋮ Distance desert automata and the star height problem ⋮ Weighted Automata and Weighted Logics ⋮ On the Burnside problem for semigroups of matrices in the \((\max,+)\) algebra ⋮ Rigorous approximated determinization of weighted automata ⋮ Stochastization of Weighted Automata ⋮ Parameterized Weighted Containment ⋮ Closure properties and complexity of rational sets of regular languages ⋮ Ambiguity Hierarchies for Weighted Tree Automata ⋮ Decidability Boundaries for the Finite-Image Property of Weighted Finite Automata ⋮ Weighted Automata and Weighted Logics with Discounting ⋮ Free iterative and iteration \(K\)-semialgebras ⋮ A coalgebraic perspective on linear weighted automata ⋮ Equivalence, Unambiguity, and Sequentiality of Finitely Ambiguous Max-Plus Tree Automata ⋮ Learning weighted automata over principal ideal domains ⋮ A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata ⋮ Isomorphisms of scattered automatic linear orders ⋮ Unnamed Item ⋮ The product of rational languages ⋮ Up-To Techniques for Weighted Systems ⋮ Representations and complete semiring morphisms ⋮ Non-deterministic Weighted Automata on Random Words ⋮ Synthesis from component libraries with costs ⋮ On High-Quality Synthesis ⋮ Non-deterministic weighted automata evaluated over Markov chains ⋮ Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton ⋮ Unnamed Item ⋮ Component simulation-based substitutivity managing QoS and composition issues ⋮ Unnamed Item ⋮ Decidable weighted expressions with Presburger combinators ⋮ Unnamed Item ⋮ Freeness properties of weighted and probabilistic automata over bounded languages ⋮ Streamable regular transductions ⋮ A generalized partition refinement algorithm, instantiated to language equivalence checking for weighted automata ⋮ Minimizing Deterministic Lattice Automata ⋮ Series which are both max-plus and min-plus rational are unambiguous ⋮ Unnamed Item ⋮ Finite sequentiality of unambiguous max-plus tree automata ⋮ On Finite and Polynomial Ambiguity of Weighted Tree Automata ⋮ The closure under division and a characterization of the recognizable $\mathcal {Z}$-subsets ⋮ What's decidable about weighted automata? ⋮ REACHABILITY PROBLEMS FOR PRODUCTS OF MATRICES IN SEMIRINGS ⋮ How to Tackle Integer Weighted Automata Positivity ⋮ Unnamed Item ⋮ Decidability, undecidability, and PSPACE-completeness of the twins property in the tropical semiring ⋮ Weighted automata ⋮ Max-plus automata ⋮ Unambiguity in Automata Theory ⋮ Models for quantitative distributed systems and multi-valued logics ⋮ Disambiguation of weighted tree automata ⋮ New representations for (max,+) automata with applications to performance evaluation and control of discrete event systems ⋮ Some properties of recognizable \(\mathcal Z\)-subsets ⋮ Ambiguity hierarchies for weighted tree automata
This page was built for publication: THE EQUALITY PROBLEM FOR RATIONAL SERIES WITH MULTIPLICITIES IN THE TROPICAL SEMIRING IS UNDECIDABLE
