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

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)

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

• 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?)
• 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
• INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS
• Identities of a five-element \(0\)-simple semigroup
• On McKenzie's method
• On classes of relations and graphs determined by subobjects and factorobjects
• Residual properties of reflexive, anti-symmetric digraphs
• Standard topological algebras: syntactic and principal congruences and profiniteness
• The axiomatizability of topological prevarieties

Cited in

(19)

• Equational theories of semigroups with involution.
• Finite basis problem for Catalan monoids with involution
• The finite basis problem for infinite involution semigroups of triangular \(2 \times 2\) matrices
• Non-Specht variety generated by an involution semigroup of order five
• 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
• On identities of finite involution semigroups.
• FINITE BASIS PROBLEM FOR INVOLUTION MONOIDS OF ORDER FIVE

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)