The algebra of adjacency patterns: Rees matrix semigroups with reversion

DOI10.1007/978-3-642-15025-8_20MaRDI QIDQ3586013zbMATH OpenOpenAlexFDO

Authors Marcel Jackson, M. V. Volkov

Publication date 3 September 2010

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

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

zbMATH Keywords

finite basis problemgraphRees matrix semigroupunary semigroup identityunary semigroup varietyuniversal Horn classuniversal Horn sentencevariety membership problem

Mathematics Subject Classification ID

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

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.

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

Cites work

• Algorithmic problems for finite groups and finite \(0\)-simple semigroups
• Antivarieties and colour-families of graphs.
• COMBINATORIAL REES–SUSHKEVICH VARIETIES ARE FINITELY BASED
• Finitely axiomatizable quasivarieties of graphs
• Flat algebras and the translation of universal Horn logic to equational logic
• scientific article; zbMATH DE number 3809626 (Why is no real title available?)
• scientific article; zbMATH DE number 3672372 (Why is no real title available?)
• scientific article; zbMATH DE number 3751028 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1226187 (Why is no real title available?)
• scientific article; zbMATH DE number 2167516 (Why is no real title available?)
• scientific article; zbMATH DE number 789816 (Why is no real title available?)
• scientific article; zbMATH DE number 798167 (Why is no real title available?)
• scientific article; zbMATH DE number 1389739 (Why is no real title available?)
• Identities of a five-element \(0\)-simple semigroup
• INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS
• On classes of relations and graphs determined by subobjects and factorobjects
• On McKenzie's method
• Residual properties of reflexive, anti-symmetric digraphs
• Standard topological algebras: syntactic and principal congruences and profiniteness
• The axiomatizability of topological prevarieties

Cited in

(24)

• Equational theories of unstable involution semigroups
• Equational theories of semigroups with involution.
• Finite basis problem for involution monoids of unitriangular Boolean matrices
• Equational theories of upper triangular tropical matrix semigroups
• Intervals of varieties of involution semigroups with contrasting reduct intervals
• A non-finitely based involution semigroup of order five
• On identities of finite involution semigroups.
• The monoid of \(2 \times 2\) triangular Boolean matrices under skew transposition is non-finitely based
• The finite basis problem for infinite involution semigroups of triangular \(2 \times 2\) matrices
• Unary enhancements of inherently non-finitely based semigroups.
• Non-Specht variety generated by an involution semigroup of order five
• Finite basis problem for Catalan monoids with involution
• Non-finitely based finite involution semigroups with finitely based semigroup reducts
• Finitely based finite involution semigroups with non-finitely based reducts
• Finite basis problem for Lee monoids with involution
• FINITE BASIS PROBLEM FOR INVOLUTION MONOIDS OF ORDER FIVE
• A groupoid approach to regular -semigroups
• Finite basis problem for involution semigroups of order four
• Equational theories of the Boolean matrix monoid \(\mathscr{BR}_n\) with involutions
• Projection algebras and free projection- and idempotent-generated regular -semigroups
• Uncountable interval of varieties of involution semigroups sharing a common semigroup variety reduct
• Maximal subgroups of free projection- and idempotent-generated semigroups with applications to partition monoids
• Finite degree: algebras in general and semigroups in particular
• The finite basis problem for Kiselman monoids.

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)