Zobrazeno 1 - 10
of 26
pro vyhledávání: '"Martin Beaudry"'
Publikováno v:
Information and Computation. 239:13-28
The notion of recognition of a language by a finite semigroup can be generalized to recognition by finite groupoids, i.e. sets equipped with a binary operation '?' which is not necessarily associative. It is well known that L can be recognized by a g
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::a56621b04780b52c778017fc0666e540
https://doi.org/10.1016/j.ic.2014.08.005
https://doi.org/10.1016/j.ic.2014.08.005
Autor:
Martin Beaudry, Markus Holzer
Publikováno v:
computational complexity. 16:60-111
We continue the study of tensor calculus over semirings in terms of complexity theory initiated by Damm et al. (2003). First, we look at tensor circuits, a natural generalization of tensor formulas; we show that the problem to determine whether the c
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::5a3d491af93540eb25b5f86987409a92
https://doi.org/10.1007/s00037-007-0222-0
https://doi.org/10.1007/s00037-007-0222-0
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:
Theoretical Computer Science. 345:206-234
We study the computational complexity of the problem SFT (Sum-free Formula partial Trace): given a tensor formula F over a subsemiring of the complex field (C,+,.) plus a positive integer k, under the restrictions that all inputs are column vectors o
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e273923e2e600ff67e03abbd7f51b190
https://doi.org/10.1016/j.tcs.2005.07.008
https://doi.org/10.1016/j.tcs.2005.07.008
Autor:
Martin Beaudry
Publikováno v:
Theoretical Computer Science. 209(1-2):299-317
We study the context-free languages recognized by a groupoid G in terms of the algebraic properties of the multiplication monoid ω(G) of G. Concentrating on the case where ω(G) is group-free, we show that all regular languages can be recognized by
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::cb7f70e6139ca4a10ec2cfde66b14b9a
Autor:
Martin Beaudry
Publikováno v:
RAIRO - Theoretical Informatics and Applications. 32:127-140
On s'interesse ici aux langages que peuvent reconnaitre les groupoides dont le monoide multiplicatif appartient a la variete A 1 des monoides idempotents. On demontre que ceux ci reconnaissent un sous-ensemble strict de la classe des langages sans et
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::eed685b9b1357936d476d514a4dddfc1
https://doi.org/10.1051/ita/1998324-601271
https://doi.org/10.1051/ita/1998324-601271
Publikováno v:
SIAM Journal on Computing. 26:138-152
The problem of evaluating a circuit whose wires carry values from a finite monoid $M$ and whose gates perform the monoid operation provides a meaningful generalization to the well-studied problem of evaluating a word over $M$. Evaluating words over m
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::3fa0a07854d28e5fdea2d73d2c307b9d
https://doi.org/10.1137/s0097539793249530
https://doi.org/10.1137/s0097539793249530
Publikováno v:
Journal of the ACM. 39:599-616
The problem of testing membership in aperiodic or “group-free” transformation monoids is the natural counterpart to the well-studied membership problem in permutation groups. The class A of all finite aperiodic monoids and the class G of all fini
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::57ee16d3b78306c7a294c02f9ef2f825
https://doi.org/10.1145/146637.146661
https://doi.org/10.1145/146637.146661
Autor:
François Lemieux, Martin Beaudry
Publikováno v:
Automata, Languages and Programming ISBN: 9783642029295
ICALP (2)
ICALP (2)
One of the main objectives of the algebraic theory of regular languages concerns the classification of regular languages based on Eilenberg's variety theorem [10]. This theorem states that there exists a bijection between varieties of regular languag
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::127c51a4b8ea06b912ad7eb73efbdf08
https://doi.org/10.1007/978-3-642-02930-1_5
https://doi.org/10.1007/978-3-642-02930-1_5
Publikováno v:
STACS 2001 ISBN: 9783540416951
STACS
STACS
It is known that recognition of regular languages by finite monoids can be generalized to context-free languages and finite groupoids, which are finite sets closed under a binary operation. A loop is a groupoid with a neutral element and in which eac
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::43c8fe5413c2d0e168e23485d0c0da90
https://doi.org/10.1007/3-540-44693-1_8
https://doi.org/10.1007/3-540-44693-1_8