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

DOI10.1016/S0304-3975(02)00236-0zbMath1021.08001MaRDI QIDQ1870591

Zoltán Ésik, Luca Aceto, Anna Ingólfsdóttir

Publication date: 14 May 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

equational logic; varieties; complete axiomatizations; exponential time complexity

Mathematics Subject Classification ID

08A70: Applications of universal algebra in computer science

68Q70: Algebraic theory of languages and automata

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

08B20: Free algebras

03C05: Equational classes, universal algebra in model theory

Related Items

Nested semantics over finite trees are equationally hard, Bisimilarity is not finitely based over BPA with interrupt, Equational theories of tropical semirings

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
• 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