TARSKI’S FINITE BASIS PROBLEM IS UNDECIDABLE

DOI10.1142/S0218196796000040zbMATH Open0844.08011MaRDI QIDQ4882918FDOQ4882918

Authors: Ralph McKenzie 

Publication date: 14 August 1996

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

Recommendations

• scientific article; zbMATH DE number 2144744
• An undecidable problem in finite combinatorics
• scientific article; zbMATH DE number 4031659
• Decidability and undecidability in the enumerable Turing degrees
• Proof of Recursive Unsolvability of Hilbert's Tenth Problem
• Undecidability, incompleteness and Arnol'd problems
• An undecidable problem in correspondence theory
• Undecidability in Weihrauch degrees
• Some proofs of undecidability of arithmetic
• Recursive unsolvability of a problem of Thue

zbMATH Keywords

varietyTuring machinefinite equational basefinitely-based algebra

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Varieties (08B99)

Cited In (58)

• A survey on varieties generated by small semigroups and a companion website
• Universal algebraic methods for non-classical logics
• On the variety generated by the monoid of triangular \(2\times 2\) matrices over a two-element field.
• Slim groupoids
• Finitary PCF is not decidable
• Lee monoid \(L_4^1\) is non-finitely based
• On the finite basis problem for the monoids of partial extensive injective transformations.
• Quasiequational Theories of Flat Algebras
• A NONFINITELY BASED FINITE SEMIRING
• Finite degree clones are undecidable
• Dualizability of automatic algebras.
• Semigroups embeddable in hyperplane face monoids.
• A finite basis theorem for difference-term varieties with a finite residual bound
• FINITELY BASED WORDS
• Unreasonable lattices of quasivarieties
• COMPUTATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM FOR VARIETIES
• Bases of identities for semigroups of bounded rank transformations of a set.
• Complexity of quasivariety lattices of pointed Abelian groups.
• The finite basis problem for words with at most two non-linear variables.
• Finite axiomatizability of congruence rich varieties
• The finite basis property of a certain semigroup of upper triangular matrices over a field.
• EQUATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM
• Inherently nonfinitely based lattices
• PROPERTIES OF VARIETIES DETERMINED BY THE DEGREES OF PROPER HYPERSUBSTITUTIONS
• Residual smallness relativized to congruence types. I
• Nonfinitely based ai-semirings with finitely based semigroup reducts
• Non-finitely based monoids.
• A finite basis theorem for residually finite, congruence meet-semidistributive varieties
• ON THE COMPLEXITY OF SOME MALTSEV CONDITIONS
• Algebraic properties of some quadratic dynamical systems
• Kripke completeness of strictly positive modal logics over meet-semilattices with operators
• THE TYPE SET OF A VARIETY IS NOT COMPUTABLE
• On the finite basis problem for the monoids of triangular Boolean matrices.
• THE FINITE BASIS PROBLEM FOR INVOLUTION SEMIGROUPS OF TRIANGULAR MATRICES
• Algebras from finite group actions and a question of Eilenberg and Schützenberger
• The max-plus algebra of the natural numbers has no finite equational basis
• Title not available (Why is that?)
• The finite basis problem for the monoid of two-by-two upper triangular tropical matrices
• On the finite basis problem for certain 2-limited words.
• The computational complexity of deciding whether a finite algebra generates a minimal variety
• A juggler's dozen of easy\(^\dag\) problems (\(^\dag\) Well, easily formulated \dots).
• COMPUTATIONALLY AND ALGEBRAICALLY COMPLEX FINITE ALGEBRA MEMBERSHIP PROBLEMS
• Constraint satisfaction, irredundant axiomatisability and continuous colouring
• Flat algebras and the translation of universal Horn logic to equational logic
• Flat unars: the primal, the semi-primal and the dualisable
• Finite basis problems and results for quasivarieties
• Title not available (Why is that?)
• The variety generated by an ai-semiring of order three
• Finite bases for flat graph algebras
• An undecidable property of recurrent double sequences
• On finite alphabets and infinite bases
• Two finitely generated varieties having no infinite simple members
• Catalan monoids inherently nonfinitely based relative to finite \(\mathscr{R}\)-trivial semigroups
• Recursive inseparability for residual bounds of finite algebras
• Finitely based, finite sets of words
• The finite basis problem for endomorphism semirings of finite semilattices with zero.
• The undecidability of the definability of principal subcongruences
• Equational theories of semigroups with involution.

This page was built for publication: TARSKI’S FINITE BASIS PROBLEM IS UNDECIDABLE

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