Complexity of equations valid in algebras of relations. I: Strong non-finitizability

DOI10.1016/S0168-0072(97)00027-4zbMath0898.03023OpenAlexW2013191336MaRDI QIDQ1377625

Hajnalka Andréka

Publication date: 1 November 1998

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0168-0072(97)00027-4

zbMATH Keywords

relation algebrasvarietiesaxiomatizabilitycylindric algebraspolyadic algebrasrepresentable algebrasequational axiomatization

Mathematics Subject Classification ID

Cylindric and polyadic algebras; relation algebras (03G15)

Related Items

Relation algebra reducts of cylindric algebras and an application to proof theory, Quasi-polyadic algebras and their dual position, On the complexity of axiomatizations of the class of representable quasi-polyadic equality algebras, On notions of representability for cylindric‐polyadic algebras, and a solution to the finitizability problem for quantifier logics with equality, Non-finitely axiomatisable two-dimensional modal logics, Complexity of equations valid in algebras of relations. II: Finite axiomatizations, Bare canonicity of representable cylindric and polyadic algebras, Omitting types algebraically and more about amalgamation for modal cylindric algebras, A brief history of Tarskian algebraic logic with new perspectives and innovations, Cylindric algebras and finite polyadic algebras, Neat embeddings, omitting types, and interpolation: an overview, Strongly representable atom structures of relation algebras, Some results about neat reducts, Relation algebras from cylindric algebras. II, Cylindric structures and dependencies in relational databases, Algebraic Logic, Where Does it Stand Today?, Strongly representable atom structures of cylindric algebras, Omitting types for algebraizable extensions of first order logic, Atom-canonicity in varieties of cylindric algebras with applications to omitting types in multi-modal logic, Epimorphisms in cylindric algebras and definability in finite variable logic

Cites Work

• The relational model of data and cylindric algebras
• The representation of relation algebras. II
• Relation algebras and projective geometries
• Measures on cylindric algebras
• Varieties of relation algebras
• Definability with bounded number of bound variables
• Weakly higher order cylindric algebras and finite axiomatization of the representables
• Epimorphisms in cylindric algebras and definability in finite variable logic
• On the chromatic number of certain highly symmetric graphs
• Cylindric algebras. Part II
• Dynamic algebras with test
• One-generated clones of operations on binary relations
• On varieties of cylindric algebras with applications to logic
• On taking subalgebras of relativized relation algebras
• Stone duality for first order logic
• A proof system for the first-order relational calculus
• Every free algebra in the variety generated by the representable dynamic algebras is separable and representable
• Dimension-complemented and locally finite dimensional cylindric algebras are elementarily equivalent
• Cylindric set algebras. Cylindric set algebras and related structures. By L. Henkin, J. D. Monk, and A. Tarski. On cylindric-relativized set algebras. By H. Andreka and I. Nemeti
• One variable is not enough for defining relation algebras, but two are
• The origin of relation algebras in the development and axiomatization of the calculus of relations
• Dynamic algebras: Examples, constructions, applications
• A simple, purely algebraic proof of the completeness of some first order logics
• Logic in algebraic form. Three languages and theories
• On systems of varieties definable by schemes of equations
• Propositional dynamic logic of regular programs
• Isomorphic but not lower base-isomorphic cylindric algebras of finite dimension
• Non-embeddable simple relation algebras
• Notions of density that imply representability in algebraic logic
• Weakly representable but not representable relation algebras
• A unifying theorem for algebraic semantics and dynamic logics
• The equational theory of union-free algebras of relations
• Adjoining units to residuated Boolean algebras
• Taming logic
• Axiomatization of identity-free equations valid in relation algebras
• A remark of representable positive cylindric algebras
• On inducing homomorphisms between relation set algebras
• Representations of distributive lattice-ordered semigroups with binary relations
• On representable relation algebras
• On the representation theory for cylindric algebras
• Relation algebras and function semigroups
• Extending Boolean operations
• Varieties of complex algebras
• The Neat Embedding Problem and the Number of Variables Required in Proofs
• Representation of Modular Lattices and Of Relation Algebras
• Cylindric algebras with terms
• Galois Theory for Cylindric Algebras and its Applications
• Isomorphic but not lower base-isomorphic cylindric set algebras
• Finitary Algebraic Logic
• Algebraizable logics
• Canonical Relativized Cylindric Set Algebras
• GENERAL DYNAMICS
• Non-finite-axiomatizability results in algebraic logic
• Representations of ordered semigroups and lattices by binary relations
• Nonfinite axiomatizability results for cylindric and relation algebras
• The Structure of Relation Algebras Generated by Relativizations
• The lattice of varieties of representable relation algebras
• Step by step – Building representations in algebraic logic
• Finite schematizable algebraic logic
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the search for a finitizable algebraization of first order logic
• On the equational theory of representable polyadic equality algebras
• Arguesian lattices which are not linear
• Representation of ordered semigroups
• Cylindric modal logic
• Nonfinitizability of classes of representable cylindric algebras
• Nonfinitizability of classes of representable polyadic algebras
• On an algebra of sets of finite sequences
• Lawvere's elementary theories and polyadic and cylindric algebras
• Substitution algebras in their relation to cylindric algebras
• Copeland algebras
• Cylindric Algebras and Algebras of Substitutions
• Splitting in Relation Algebras
• Algebras and their subalgebras
• Boolean Algebras with Operators
• POLYADIC BOOLEAN ALGEBRAS
• Combinatorial Relations and Chromatic Graphs
• Free algebras in discriminator varieties