Author name cluster

Pascal Tesson

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 2009 Journal Article

Universal algebra and hardness results for constraint satisfaction problems

Benoît Larose
Pascal Tesson

We present algebraic conditions on constraint languages Γ that ensure the hardness of the constraint satisfaction problem CSP ( Γ ) for complexity classes L, NL, P, NP and Mod p L. These criteria also give non-expressibility results for various restrictions of Datalog. Furthermore, we show that if CSP ( Γ ) is not first-order definable then it is L-hard. Our proofs rely on tame congruence theory and on a fine-grain analysis of the complexity of reductions used in the algebraic study of CSP. The results pave the way for a refinement of the dichotomy conjecture stating that each CSP ( Γ ) lies in P or is NP-complete and they match the recent classification of [E. Allender, M. Bauland, N. Immerman, H. Schnoor, H. Vollmer, The complexity of satisfiability problems: Refining Schaefer’s theorem, in: Proc. 30 th Math. Found. of Comp. Sci. , MFCS’05, 2005, pp. 71–82] for Boolean CSP. We also infer a partial classification theorem for the complexity of CSP ( Γ ) when the associated algebra of Γ is the full idempotent reduct of a preprimal algebra.

Details DOI

CSL Conference 2006 Conference Paper

An Algebraic Point of View on the Crane Beach Property

Clemens Lautemann
Pascal Tesson
Denis Thérien

Abstract A letter e ∈Σ is said to be neutral for a language L if it can be inserted and deleted at will in a word without affecting membership in L. The Crane Beach Conjecture, which was recently disproved, stated that any language containing a neutral letter and definable in first-order with arbitrary numerical predicates ( \({\bf FO}[\mathit{Arb}]\) ) is in fact FO [<] definable and is thus a regular, star-free language. More generally, we say that a logic or a computational model has the Crane Beach property if the only languages with neutral letter that it can define/compute are regular. We develop an algebraic point of view on the Crane Beach properties using the program over monoid formalism which has proved of importance in circuit complexity. Using recent communication complexity results we establish a number of Crane Beach results for programs over specific classes of monoids. These can be viewed as Crane Beach theorems for classes of bounded-width branching programs. We also apply this to a standard extension of FO using modular-counting quantifiers and show that the boolean closure of this logic’s Σ 1 fragment has the CBP.

Details

I&C Journal 2006 Journal Article

Learning expressions and programs over monoids

Ricard Gavaldà
Pascal Tesson
Denis Thérien

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 computational complexity of the learning problem with the algebraic complexity of the finite monoid. Indeed, our results indicate a close connection between both kinds of complexity. We focus on monoids which are either groups or aperiodic, and on the learning model of exact learning from queries. For a group G, we prove that expressions over G are efficiently learnable if G is nilpotent, and impossible to learn efficiently (under cryptographic assumptions) if G is nonsolvable. We present some results for restricted classes of solvable groups, and point out a connection between their efficient learnability and the existence of lower bounds on their computational power in the program model. For aperiodic monoids, our results seem to indicate that the monoid class known as DA captures exactly learnability of expressions by polynomially many Evaluation queries. When using programs instead of expressions, we show that our results for groups remain true, while the situation is quite different for aperiodic monoids.

Details DOI

MFCS Conference 2006 Conference Paper

Systems of Equations over Finite Semigroups and the #CSP Dichotomy Conjecture

Ondrej Klíma 0001
Benoît Larose
Pascal Tesson

Abstract We study the complexity of counting the number of solutions to a system of equations over a fixed finite semigroup. We show that this problem is always either in FP or #P-complete and describe the borderline precisely. We use these results to convey some intuition about the conjectured dichotomy for the complexity of counting the number of solutions in constraint satisfaction problems.

Details

MFCS Conference 2001 Conference Paper

Satisfiability of Systems of Equations over Finite Monoids

Cristopher Moore
Pascal Tesson
Denis Thérien

Abstract We study the computational complexity of determining whether a systems of equations over a fixed finite monoid has a solution. In [ 6 ], it was shown that in the restricted case of groups the problem is tractable if the group is Abelian and NP-complete otherwise. We prove that in the case of an arbitrary finite monoid, the problem is in P if the monoid divides the direct product of an Abelian group and a commutative idempotent monoid, and is NP-complete otherwise. In the restricted case where only constants appear on the right-hand side, we show that the problem is in P if the monoid is in the class R 1 ∀ L 1, and is NP-complete otherwise. Furthermore interesting connections to the well known C ONSTARINT S ATISFIABILITY P ROBLEM are uncovered and exploited.

Details

MFCS Conference 2000 Conference Paper

Equation Satisfiability and Program Satisfiability for Finite Monoids

David A. Mix Barrington
Pierre McKenzie
Cristopher Moore
Pascal Tesson
Denis Thérien

Abstract We study the computational complexity of solving equations and of determining the satisfiability of programs over a fixed finite monoid. We partially answer an open problem of [ 4 ] by exhibiting quasi-polynomial time algorithms for a subclass of solvable non-nilpotent groups and relate this question to a natural circuit complexity conjecture. In the special case when M is aperiodic, we show that PROGRAM SATISFIABILITY is in P when the monoid belongs to the variety DA and is NP-complete otherwise. In contrast, we give an example of an aperiodic outside DA for which EQUATION SATISFIABILITY is computable in polynomial time and discuss the relative complexity of the two problems. We also study the closure properties of classes for which these problems belong to P and the extent to which these fail to form algebraic varieties.

Details