Zobrazeno 1 - 10
of 94
pro vyhledávání: '"Denis Thérien"'
Publikováno v:
International Journal of Algebra and Computation. 20:319-341
Unlike the wreath product, the block product is not associative at the level of varieties. All decomposition theorems involving block products, such as the bilateral version of Krohn–Rhodes' theorem, have always assumed a right-to-left bracketing o
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::a7217f0a92ae5e7d9050bf36fd12725a
https://doi.org/10.1142/s0218196710005686
https://doi.org/10.1142/s0218196710005686
Publikováno v:
Information and Computation. 204(2):177-209
We study the problem of learning an unknown function represented as an expression or a program over a known finite monoid. As in other areas of computational complexity where programs over algebras have been used, the goal is to relate the computatio
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::69e09bdb05a1c780832271ba37b3423a
Autor:
Martin Beaudry, Marats Golovkins, Andris Ambainis, Denis Thérien, Arnolds Kikusts, Mark Mercer
Publikováno v:
Theory of Computing Systems. 39:165-188
We use tools from the algebraic theory of automata to investigate the class of languages recognized by two models of Quantum Finite Automata (QFA): Brodsky and Pippenger's end-decisive model (which we call BPQFA) and a new QFA model (which we call LQ
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::61e708e0ac90c08ef53fb74d7301e53f
https://doi.org/10.1007/s00224-005-1263-x
https://doi.org/10.1007/s00224-005-1263-x
Publikováno v:
Theory of Computing Systems. 40:263-297
We consider the problem of testing whether a given system of equations over a fixed finite semigroup S has a solution. For the case where S is a monoid, we prove that the problem is computable in polynomial time when S is commutative and is the union
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ee8fad18a1d7b0ea958e193f0c3316f9
https://doi.org/10.1007/s00224-005-1279-2
https://doi.org/10.1007/s00224-005-1279-2
Publikováno v:
International Journal of Foundations of Computer Science. 16:625-644
It is well-known that the Σk- and Πk-levels of the dot-depth hierarchy and the polynomial hierarchy correspond via leaf languages. We extend this correspondence to the Δk-levels of these hierarchies: [Formula: see text]. The same methods are used
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::6f1461f9f04cacb5553c9b2ed79a7c0e
https://doi.org/10.1142/s0129054105003200
https://doi.org/10.1142/s0129054105003200
Autor:
Howard Straubing, Denis Thérien
Publikováno v:
Theory of Computing Systems. 39:699-706
We give a new proof of recent results of Grolmusz and Tardos on the computing power of constant-depth circuits consisting of a single layer of $MOD_m$ gates followed by a fixed number of layers of $MOD_{p^k}$ -gates, where p is prime.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::bd6fd0fcba402b4066b3a1ff9ed70a53
https://doi.org/10.1007/s00224-004-1210-2
https://doi.org/10.1007/s00224-004-1210-2
Autor:
Denis Thérien
Publikováno v:
RAIRO - Theoretical Informatics and Applications. 39:297-304
This short note reviews the main contributions of the Ph.D. thesis of Imre Simon. His graduate work had major impact on algebraic theory of automata and thirty years later we are in a good position to appreciate how sensitive he was in selecting good
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::bdd31cfbb27562403dfcf90276133833
https://doi.org/10.1051/ita:2005017
https://doi.org/10.1051/ita:2005017
Autor:
Pascal Tesson, Denis Thérien
Publikováno v:
Theory of Computing Systems. 38:135-159
We show that every regular language L has either constant, logarithmic or linear two-party communication complexity (in a worst-case partition sense). We prove similar classifications for the communication complexity of regular languages for the simu
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ceb1635d229445fbca8fb02d9294d68d
https://doi.org/10.1007/s00224-004-1190-2
https://doi.org/10.1007/s00224-004-1190-2
Autor:
Denis Thérien, Pascal Tesson
Publikováno v:
International Journal of Algebra and Computation. 14:801-816
This contribution wishes to argue in favor of increased interaction between experts on finite monoids and specialists of theory of computation. Developing the algebraic approach to formal computations as well as the computational point of view on mon
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::3eab1d99cf97ec90c6ea630790463bbc
https://doi.org/10.1142/s0218196704001979
https://doi.org/10.1142/s0218196704001979
Autor:
Thomas Wilke, Denis Thérien
Publikováno v:
Theory of Computing Systems. 37:111-131
We provide an effective characterization of the “until-since hierarchy” of linear temporal logic over finite models (strings), that is, we show how to compute for a given temporal property of strings the minimal nesting depth in “until” and
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::839ae262b0368042d1c4f8a700635475
https://doi.org/10.1007/s00224-003-1109-3
https://doi.org/10.1007/s00224-003-1109-3