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)
68W30: Symbolic computation and algebraic computation
68Q45: Formal languages and automata
03B25: Decidability of theories and sets of sentences
16Y60: Semirings
Related Items
The product of rational languages, The closure under division and a characterization of the recognizable $\mathcal {Z}$-subsets, DECIDABILITY OF THE EQUIVALENCE PROBLEM FOR FINITELY AMBIGUOUS FINANCE AUTOMATA, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Distance desert automata and the star height problem, REACHABILITY PROBLEMS FOR PRODUCTS OF MATRICES IN SEMIRINGS, Unambiguity in Automata Theory, On High-Quality Synthesis, Decidable weighted expressions with Presburger combinators, Minimizing Deterministic Lattice Automata, Approximate comparison of functions computed by distance automata, Rigorous approximated determinization of weighted automata, Free iterative and iteration \(K\)-semialgebras, A coalgebraic perspective on linear weighted automata, Representations and complete semiring morphisms, Synthesis from component libraries with costs, Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton, Decidability, undecidability, and PSPACE-completeness of the twins property in the tropical semiring, Weighted automata and weighted logics with discounting, Closure properties and complexity of rational sets of regular languages, Component simulation-based substitutivity managing QoS and composition issues, Finite-valued distance automata, A generalized partition refinement algorithm, instantiated to language equivalence checking for weighted automata, Some properties of recognizable \(\mathcal Z\)-subsets, Equational theories of tropical semirings, On the Burnside problem for semigroups of matrices in the \((\max,+)\) algebra, Non-deterministic weighted automata evaluated over Markov chains, Finite sequentiality of unambiguous max-plus tree automata, What's decidable about weighted automata?, Weighted automata, Max-plus automata, Learning weighted automata over principal ideal domains, Freeness properties of weighted and probabilistic automata over bounded languages, Streamable regular transductions, New representations for (max,+) automata with applications to performance evaluation and control of discrete event systems, Weighted automata and weighted logics, Axiomatizing rational power series over natural numbers, Isomorphisms of scattered automatic linear orders, On Finite and Polynomial Ambiguity of Weighted Tree Automata, Models for quantitative distributed systems and multi-valued logics, Coinduction in Concurrent Timed Systems, Stochastization of Weighted Automata, Parameterized Weighted Containment, Up-To Techniques for Weighted Systems, Series which are both max-plus and min-plus rational are unambiguous, Weight Assignment Logic, Weighted Automata and Weighted Logics with Discounting, A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata, How to Tackle Integer Weighted Automata Positivity
