The max-plus algebra of the natural numbers has no finite equational basis

DOI10.1016/S0304-3975(02)00236-0MaRDI QIDQ1870591zbMATH OpenOpenAlexFDO

Authors Luca Aceto, Anna Ingolfsdottir, 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

zbMATH Keywords

varietiesequational logiccomplete axiomatizationsexponential time complexity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algebraic theory of languages and automata (68Q70) Equational classes, universal algebra in model theory (03C05) Free algebras (08B20) Applications of universal algebra in computer science (08A70)

Recommendations

• scientific article; zbMATH DE number 1500521
• Which two-sorted algebras of Booleans and naturals have a finite basis?
• Equational theories of tropical semirings
• scientific article; zbMATH DE number 1701345
• Maxpolynomial equations

Cites work

• scientific article; zbMATH DE number 3645165 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3716792 (Why is no real title available?)
• scientific article; zbMATH DE number 3751028 (Why is no real title available?)
• scientific article; zbMATH DE number 3770925 (Why is no real title available?)
• scientific article; zbMATH DE number 3501006 (Why is no real title available?)
• scientific article; zbMATH DE number 3554198 (Why is no real title available?)
• scientific article; zbMATH DE number 3639689 (Why is no real title available?)
• scientific article; zbMATH DE number 1500521 (Why is no real title available?)
• scientific article; zbMATH DE number 1555176 (Why is no real title available?)
• scientific article; zbMATH DE number 3248007 (Why is no real title available?)
• scientific article; zbMATH DE number 3366846 (Why is no real title available?)
• A field guide to equational logic
• A menagerie of non-finitely based process semantics over BPA* – from ready simulation to completed traces
• Bisimulation can't be traced
• Bisimulation through probabilistic testing
• Equational Bases for Lattice Theories.
• Identical relations in finite groups
• Identities in Two-Valued Calculi
• Nonfinite axiomatizability of the equational theory of shuffle
• TARSKI’S FINITE BASIS PROBLEM IS UNDECIDABLE
• The variety of Kleene algebras with conversion is not finitely based

Cited in

(10)

• Another Characterization of the Natural Numbers
• Equational theories of tropical semirings
• Bisimilarity is not finitely based over BPA with interrupt
• Nested semantics over finite trees are equationally hard
• Which two-sorted algebras of Booleans and naturals have a finite basis?
• Semiring identities of finite inverse semigroups
• Nonfinitely based ai-semirings with finitely based semigroup reducts
• The max-plus algebra of exponent matrices of tiled orders
• Semiring identities of the semigroup \(B_0\)
• Flat extensions of groups and limit varieties of additively idempotent semirings

This page was built for publication: The max-plus algebra of the natural numbers has no finite equational basis

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