The algebra of adjacency patterns: Rees matrix semigroups with reversion

DOI10.1007/978-3-642-15025-8_20zbMATH Open1287.08010arXiv0907.2634OpenAlexW3101220573MaRDI QIDQ3586013FDOQ3586013

Authors: Marcel Jackson, M. V. Volkov 

Publication date: 3 September 2010

Published in: Fields of Logic and Computation (Search for Journal in Brave)

Abstract: We establish a surprisingly close relationship between universal Horn classes of directed graphs and varieties generated by so-called adjacency semigroups which are Rees matrix semigroups over the trivial group with the unary operation of reversion. In particular, the lattice of subvarieties of the variety generated by adjacency semigroups that are regular unary semigroups is essentially the same as the lattice of universal Horn classes of reflexive directed graphs. A number of examples follow, including a limit variety of regular unary semigroups and finite unary semigroups with NP-hard variety membership problems.

Full work available at URL: https://arxiv.org/abs/0907.2634

Recommendations

• Graph algebras and graph varieties
• scientific article; zbMATH DE number 3875543
• Some properties of semigroup graph algebras
• On Correspondences Between Unary Algebras, Automata, Semigroups and Congruences
• On subalgebra lattices of a finite unary algebra. I

zbMATH Keywords

graphfinite basis problemRees matrix semigroupuniversal Horn classuniversal Horn sentenceunary semigroup identityunary semigroup varietyvariety membership problem

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Lattices of varieties (08B15) Varieties and pseudovarieties of semigroups (20M07)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Algorithmic problems for finite groups and finite \(0\)-simple semigroups
• Title not available (Why is that?)
• Standard topological algebras: syntactic and principal congruences and profiniteness
• The axiomatizability of topological prevarieties
• On classes of relations and graphs determined by subobjects and factorobjects
• Antivarieties and colour-families of graphs.
• COMBINATORIAL REES–SUSHKEVICH VARIETIES ARE FINITELY BASED
• Flat algebras and the translation of universal Horn logic to equational logic
• Residual properties of reflexive, anti-symmetric digraphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS
• Finitely axiomatizable quasivarieties of graphs
• Title not available (Why is that?)
• Identities of a five-element \(0\)-simple semigroup
• Title not available (Why is that?)
• On McKenzie's method
• Title not available (Why is that?)

Cited In (19)

• Finite basis problem for Catalan monoids with involution
• Non-Specht variety generated by an involution semigroup of order five
• The finite basis problem for infinite involution semigroups of triangular \(2 \times 2\) matrices
• Finite degree: algebras in general and semigroups in particular
• A groupoid approach to regular \(\ast \)-semigroups
• Non-finitely based finite involution semigroups with finitely based semigroup reducts
• Finitely based finite involution semigroups with non-finitely based reducts
• Unary enhancements of inherently non-finitely based semigroups.
• Equational theories of upper triangular tropical matrix semigroups
• The monoid of \(2 \times 2\) triangular Boolean matrices under skew transposition is non-finitely based
• The finite basis problem for Kiselman monoids.
• Equational theories of unstable involution semigroups
• Finite basis problem for Lee monoids with involution
• Finite basis problem for involution monoids of unitriangular Boolean matrices
• Intervals of varieties of involution semigroups with contrasting reduct intervals
• A non-finitely based involution semigroup of order five
• FINITE BASIS PROBLEM FOR INVOLUTION MONOIDS OF ORDER FIVE
• On identities of finite involution semigroups.
• Equational theories of semigroups with involution.

This page was built for publication: The algebra of adjacency patterns: Rees matrix semigroups with reversion

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