Author name cluster

Martin Beaudry

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers

2 author rows

I&C Journal 2014 Journal Article

Conservative groupoids recognize only regular languages

Martin Beaudry
Danny Dubé
Maxime Dubé
Mario Latendresse
Pascal Tesson

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 groupoid iff L is context-free. However it is also known that some subclasses of groupoids can only recognize regular languages. A groupoid H is said to be conservative if a ⋅ b ∈ { a, b } for all a, b ∈ H. The first result of this paper is that conservative groupoids can only recognize regular languages. This class of groupoids is incomparable with the ones identified so far which share this property, so we are exhibiting a new way in which a groupoid can be too weak to recognize non-regular languages. We also study the class L cons of regular languages that can be recognized in this way and explain how it fits within the well-known Straubing–Thérien hierarchy. In particular we show that L cons contains depth 1/2 of the hierarchy and is entirely contained in depth 3/2.

Details DOI

TCS Journal 2011 Journal Article

On the size of inverse semigroups given by generators

Martin Beaudry
Markus Holzer

The size of the transformation semigroup of a reversible deterministic finite automaton with n states, or equivalently, of a semigroup given by generators of injective partial functions on n objects, had remained unexplored in the case where the set of generators is a pair. We show that in this case, the maximal size is attained by a semigroup generated by a permutation that satisfies a property depending on n and a partial injective mapping whose domain and image both have size n − 1. Moreover, we give precise formulas in terms of n for this maximal size.

Details DOI

TCS Journal 2005 Journal Article

A common algebraic description for probabilistic and quantum computations

Martin Beaudry
José M. Fernandez
Markus Holzer

Through the study of gate arrays we develop a unified framework to deal with probabilistic and quantum computations, where the former is shown to be a natural special case of the latter. On this basis we show how to encode a probabilistic or quantum gate array into a sum-free tensor formula which satisfies the conditions of the partial trace problem, and vice-versa; that is, given a tensor formula F of order n × 1 over a semiring S plus a positive integer k, deciding whether the kth partial trace of the matrix val S n, n ( F · F T ) fulfills a certain property. We use this to show that a certain promise version of the sum-free partial trace problem is complete for the class pr- BPP (promise BPP) for formulas over the semiring ( Q +, +, · ) of the positive rational numbers, for pr-BQP (promise BQP) in the case of formulas defined over the field ( Q +, +, · ), and if the promise is given up, then completeness for PP is shown, regardless whether tensor formulas over positive rationals or rationals in general are used. This suggests that the difference between probabilistic and quantum polytime computers may ultimately lie in the possibility, in the latter case, of having destructive interference between computations occurring in parallel. Moreover, by considering variants of this problem, classes like ⊕ P, NP, C = P, its complement co - C = P, the promise version of Valiant's class UP, its generalization promise SPP, and unique polytime US can be characterized by carrying the problem properties and the underlying semiring.

Details DOI

MFCS Conference 2004 Conference Paper

A Common Algebraic Description for Probabilistic and Quantum Computations (Extended Abstract)

Martin Beaudry
José M. Fernandez 0001
Markus Holzer 0001

Abstract Through the study of gate arrays we develop a unified framework to deal with probabilistic and quantum computations, where the former is shown to be a natural special case of the latter. On this basis we show how to encode a probabilistic or quantum gate array into a sum-free tensor formula which satisfies the conditions of the partial trace problem, and vice-versa. In this way complete problems for the classes pr-BPP (promise BPP) and pr-BQP (promise BQP) are given when changing the semiring from (ℚ +, +, ·) to the field (ℚ, +, ·). Moreover, by variants of the problem under consideration, classes like ⊕P, NP, C = P, its complement co-C = P, the promise version of Valiant’s class UP, its generalization promise SPP, and unique polytime US are captured as problem property and the semiring varies.

Details

MFCS Conference 2001 Conference Paper

The Complexity of Tensor Circuit Evaluation

Martin Beaudry
Markus Holzer 0001

Abstract The study of tensor calculus over semirings in terms of complexity theory was initiated by Damm et al. in [ 8 ]. Here we first look at tensor circuits, a natural generalization of tensor formulas; we show that the problem of asking whether the output of such circuits is non-zero is complete for the class NE = NTIME(2 o ( n ) ) for circuits over the boolean semiring, ⊕E for the field \( \mathbb{F}_2 \), and analogous results for other semirings. Common sense restrictions such as imposing a logarithmic upper bound on circuit depth are also discussed. Second, we analyze other natural problems concerning tensor formulas and circuits over various semirings, such as asking whether the output matrix is diagonal or a null matrix.

Details

TCS Journal 1998 Journal Article

Languages recognized by finite aperiodic groupoids

Martin Beaudry

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 groupoids for which M(G) is -trivial of threshold 2 and that all groupoids for which ω(G) belongs to the larger variety DA recognize only regular languages. Further, we give an example of a groupoid such that ω(G) is in the smallest variety outside of DA, and which recognizes all context-free languages not containing the empty word.

Details DOI

I&C Journal 1988 Journal Article

Membership testing in commutative transformation semigroups

Martin Beaudry

Given a finite set X of states, a finite set of commuting transformations of X (generators), and another transformation f of X, we analyze the complexity of deciding whether f can be obtained by composition of the generators. Looking first at the action of a commutative semigroup of transformations of a finite set, we obtain an algorithm for membership testing, valid for arbitrary commutative semigroups. We then show that the complexity of the problem varies with the threshold of the semigroup: polynomial-time (NC 3 in parallel) with threshold zero or one, and NP-complete otherwise.

Details DOI