Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/112092
Title: The Algebra of Adjacency Patterns: Rees Matrix Semigroups with Reversion
Authors: Jackson, M.
Volkov, M.
Issue Date: 2010
Publisher: Springer Berlin Heidelberg
Citation: Jackson M. The Algebra of Adjacency Patterns: Rees Matrix Semigroups with Reversion / M. Jackson, M. Volkov // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2010. — Vol. 6300 LNCS. — P. 414-443.
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. © 2010 Springer-Verlag Berlin Heidelberg.
Keywords: FINITE BASIS PROBLEM
GRAPH
REES MATRIX SEMIGROUP
UNARY SEMIGROUP IDENTITY
UNARY SEMIGROUP VARIETY
UNIVERSAL HORN CLASS
UNIVERSAL HORN SENTENCE
VARIETY MEMBERSHIP PROBLEM
FINITE BASIS PROBLEM
GRAPH
MATRIX
MEMBERSHIP PROBLEM
SEMI-GROUP
UNIVERSAL HORN CLASS
UNIVERSAL HORN SENTENCE
COMPUTER SCIENCE
GRAPH THEORY
TECHNICAL PRESENTATIONS
MATRIX ALGEBRA
URI: http://hdl.handle.net/10995/112092
Access: info:eu-repo/semantics/openAccess
Conference name: 35th International Symposium on Mathematical Foundations of Computer Science, MFCS 2010, and 19th EACSL Annual Conference on Computer Science Logic, CSL 2010
Conference date: 22 August 2010 through 22 August 2010
SCOPUS ID: 77956565649
ISSN: 0302-9743
ISBN: 3642150241
9783642150241
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-77956565649.pdf407,99 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.