The Algebra of Adjacency Patterns: Rees Matrix Semigroups with Reversion / Jackson Marcel,Volkov Mikhail // . - 2010. - V. 6300, l. . - P. 414+.

ISSN/EISSN:

0302-9743 / нет данных

Type:

Proceedings Paper

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.

Author keywords:

Rees matrix semigroup; unary semigroup identity; unary semigroup variety; graph; universal Horn sentence; universal Horn class; variety membership problem; finite basis problem GRAPHS; QUASIVARIETIES

DOI:

нет данных

Web of Science ID:

ISI:000286783000021

Соавторы в МНС:

—

Другие поля

Поле	Значение
Editor	Blass, A and Dershowitz, N and Reisig, W
Booktitle	FIELDS OF LOGIC AND COMPUTATION: ESSAYS DEDICATED TO YURI GUREVICH ON THE OCCASION OF HIS 70TH BIRTHDAY
Series	Lecture Notes in Computer Science
Note	YuriFest: Symposium on Logic in Computer Science, Brno, CZECH REPUBLIC, AUG 22, 2010
Publisher	SPRINGER-VERLAG BERLIN
Address	HEIDELBERGER PLATZ 3, D-14197 BERLIN, GERMANY
Language	English
ISBN	978-3-642-15024-1
Keywords-Plus	GRAPHS; QUASIVARIETIES
Research-Areas	Computer Science; Mathematics
Web-of-Science-Categories	Computer Science, Software Engineering; Computer Science, Theory \& Methods; Mathematics, Applied
Author-Email	M.G.Jackson@latrobe.edu.au Mikhail.Volkov@usu.ru
ResearcherID-Numbers	Volkov, Mikhail/F-1407-2014
ORCID-Numbers	Volkov, Mikhail/0000-0002-9327-243X
Funding-Acknowledgement	ARC {[}DP0342459, DP1094578]; Russian Education Agency {[}2.1.1/3537]; Russian Foundation for Basic Research {[}09-01-12142, 10-01-00524]
Funding-Text	The first author was supported by ARC Discovery Project Grant DP0342459. The authors were partially supported also by ARC Discovery Project Grant DP1094578.; The second author was supported by the Program 2.1.1/3537 of the Russian Education Agency and by the Russian Foundation for Basic Research, grants 09-01-12142 and 10-01-00524.
Number-of-Cited-References	25
Doc-Delivery-Number	BTF31