Zobrazeno 1 - 10
of 41
pro vyhledávání: '"Tesson, Pascal"'
We completely classify the computational complexity of the list H-colouring problem for graphs (with possible loops) in combinatorial and algebraic terms: for every graph H the problem is either NP-complete, NL-complete, L-complete or is first-order
Externí odkaz:
http://arxiv.org/abs/0912.3802
Autor:
Tesson, Pascal, Therien, Denis
Publikováno v:
Logical Methods in Computer Science, Volume 3, Issue 1 (February 23, 2007) lmcs:2226
The study of finite automata and regular languages is a privileged meeting point of algebra and logic. Since the work of Buchi, regular languages have been classified according to their descriptive complexity, i.e. the type of logical formalism requi
Externí odkaz:
http://arxiv.org/abs/cs/0701154
Publikováno v:
In Information and Computation December 2014 239:13-28
Autor:
Larose, Benoît, Tesson, Pascal
Publikováno v:
In Theoretical Computer Science 2009 410(18):1629-1647
Publikováno v:
In Information and Computation 2006 204(2):177-209
Autor:
Tesson, Pascal1 ptesso@cs.mcgill.ca, Thérien, Denis1 denis@cs.mcgill.ca
Publikováno v:
Theory of Computing Systems. Mar/Apr2005, Vol. 38 Issue 2, p135-159. 25p.
Autor:
Tesson, Pascal, Thérien, Denis
The formalism of programs over monoids has been studied for its close connection to parallel complexity classes defined by small-depth boolean circuits. We investigate two basic questions about this model. When is a monoid rich enough that it can rec
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::99920bc1849827d82169de679a498947