The max-plus algebra of the natural numbers has no finite equational basis
From MaRDI portal
Publication:1870591
DOI10.1016/S0304-3975(02)00236-0zbMath1021.08001OpenAlexW2080117016MaRDI QIDQ1870591
Anna Ingólfsdóttir, Luca Aceto, Zoltán Ésik
Publication date: 14 May 2003
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00236-0
Applications of universal algebra in computer science (08A70) Algebraic theory of languages and automata (68Q70) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Free algebras (08B20) Equational classes, universal algebra in model theory (03C05)
Related Items (7)
Equational theories of tropical semirings ⋮ Bisimilarity is not finitely based over BPA with interrupt ⋮ The max-plus algebra of exponent matrices of tiled orders ⋮ Nested semantics over finite trees are equationally hard ⋮ Semiring identities of finite inverse semigroups ⋮ Flat extensions of groups and limit varieties of additively idempotent semirings ⋮ Nonfinitely based ai-semirings with finitely based semigroup reducts
Cites Work
- Nonfinite axiomatizability of the equational theory of shuffle
- Bisimulation through probabilistic testing
- A field guide to equational logic
- The variety of Kleene algebras with conversion is not finitely based
- Identical relations in finite groups
- Equational Bases for Lattice Theories.
- A menagerie of non-finitely based process semantics over BPA* – from ready simulation to completed traces
- Bisimulation can't be traced
- TARSKI’S FINITE BASIS PROBLEM IS UNDECIDABLE
- Identities in Two-Valued Calculi
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: The max-plus algebra of the natural numbers has no finite equational basis
