Denis Thérien

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.

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.

FOCS Conference 2006 Conference Paper

Lower bounds for circuits with MOD_m gates

• Arkadev Chattopadhyay
• Navin Goyal
• Pavel Pudlák
• Denis Thérien

Let CC o(n) [m] be the class of circuits that have size o(n) and in which all gates are MOD[m] gates. We show that CC [m] circuits cannot compute MOD q in sub-linear size when m, q > 1 are co-prime integers. No non-trivial lower bounds were known before on the size of CC [m] circuits of constant depth for computing MOD q. On the other hand, our results show circuits of type MAJ o CC o(n) [m] need exponential size to compute MOD q. Using Bourgain's recent breakthrough result on estimates of exponential sums, we extend our bound to the case where small fan-in AND gates are allowed at the bottom of such circuits i. e. circuits of type MAJ o CC[m] o AND epsiv log n, where epsiv > 0 is a sufficiently small constant. CC [m] circuits of constant depth need superlinear number of wires to compute both the AND and MOD q functions. To prove this, we show that any circuit computing such functions has a certain connectivity property that is similar to that of superconcentration. We show a superlinear lower bound on the number of edges of such graphs extending results on superconcentrators

STOC Conference 2005 Conference Paper

Bounded-depth circuits: separating wires from gates

• Michal Koucký 0001
• Pavel Pudlák
• Denis Thérien

I&C Journal 2003 Journal Article

An algebraic approach to data languages and timed languages

• Patricia Bouyer
• Antoine Petit
• Denis Thérien

Algebra offers an elegant and powerful approach to understand regular languages and finite automata. Such framework has been notoriously lacking for timed languages and timed automata. We introduce the notion of monoid recognizability for data languages, which includes timed languages as special case, in a way that respects the spirit of the classical situation. We study closure properties and hierarchies in this model and prove that emptiness is decidable under natural hypotheses. Our class of recognizable languages properly includes many families of deterministic timed languages that have been proposed until now, and the same holds for non-deterministic versions.

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.

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.

TCS Journal 2000 Journal Article

Programs over semigroups of dot-depth one

• Alexis Maciel
• Pierre Péladeau
• Denis Thérien

The notion of a p-variety arises in the algebraic approach to Boolean circuit complexity. It has great significance, since many known and conjectured lower bounds on circuits are equivalent to the assertion that certain classes of semigroups form p-varieties. In this paper, we prove that semigroups of dot-depth one form a p-variety. This example has the following implication: if a Boolean combination of Σ1 formulas, using arbitrary numerical predicates, defines a regular language, one can then find an equivalent Σ1 formula all of whose numerical predicates are regular.

I&C Journal 1999 Journal Article

Efficient Threshold Circuits for Power Series

• Alexis Maciel
• Denis Thérien

We show that functions with convergent real power series can be well approximated by two classes of polynomial-size small-weight threshold circuits: depth-three circuits with threshold gates on all levels and depth-four circuits with threshold gates on the first two levels and AND–OR gates on the last two. This is done without restricting the input to a fixed closed subinterval of the interval of convergence of the series. We also point out that rational functions and the logarithm of x in base b can be well approximated by the same classes of circuits when both x and b are given as input.

STOC Conference 1998 Conference Paper

Over Words, Two Variables Are as Powerful as One Quantifier Alternation

• Denis Thérien
• Thomas Wilke

I&C Journal 1998 Journal Article

Threshold Circuits of Small Majority-Depth

• Alexis Maciel
• Denis Thérien

Constant-depth polynomial-size threshold circuits are usually classified according to their total depth. For example, the best known threshold circuits for iterated multiplication and division have depths four and three, respectively. In this paper, the complexity of threshold circuits is investigated from a different point of view: explicit AND, OR gates are allowed in the circuits, and a threshold circuit is said to have majority-depthdif no path traverses more thandthreshold gates. It is then shown that iterated multiplication can be computed by polynomial-size threshold circuits of total depth five but of majority-depth three. Circuits of depth four and majority-depth two are obtained for division and powering. These results rely on a careful implementation of iterated addition and Chinese remaindering. In addition, a simple symbolic calculus for composing circuit classes is developed: this notation allows for a concise and elegant presentation of the results.

I&C Journal 1996 Journal Article

Logspace and Logtime Leaf Languages

• Birgit Jenner
• Pierre McKenzie
• Denis Thérien

The computation tree of a nondeterministic machineMwith inputxgives rise to aleaf stringformed by concatenating the outcomes of all the computations in the tree in lexicographical order. We may characterize problems by considering, for a particular “leaf language”Y, the set of allxfor which the leaf string ofMis contained inY. In this way, in the context of polynomial time computation, leaf languages were shown to capture many complexity classes. In this paper, we study the expressibility of the leaf language mechanism in the contexts of logarithmic space and of logarithmic time computation. We show that logspace leaf languages yield a much finer classification scheme for complexity classes than polynomial time leaf languages, capturing also many classes withinP. In contrast, logtime leaf languages basically behave like logtime reducibilities. Both cases are more subtle to handle than the polynomial time case. We also raise the issue of balanced versus nonbalanced computation trees underlying the leaf language. We indicate that it is a nontrivial problem to obtain information about the leaf string of a nonbalanced computation tree and present conditions under which it does not matter whether the computation tree is balanced or not.

FOCS Conference 1996 Conference Paper

Temporal Logic and Semidirect Products: An Effective Characterization of the Until Hierarchy

• Denis Thérien
• Thomas Wilke

We reveal an intimate connection between semidirect products of finite semigroups and substitution of formulas in linear temporal logic. We use this connection to obtain an algebraic characterization of the 'until' hierarchy of linear temporal logic; the k-th level of that hierarchy is comprised of all temporal properties that are expressible by a formula of nesting depth at most k in the 'until' operator. Applying deep results from finite semigroup theory we are able to prove that each level of the until hierarchy is decidable.

CSL Conference 1995 Conference Paper

Logics For Context-Free Languages

• Clemens Lautemann
• Thomas Schwentick
• Denis Thérien

Abstract We define matchings, and show that they capture the essence of context-freeness. More precisely, we show that the class of context-free languages coincides with the class of those sets of strings which can be defined by sentences of the form ∃ bϕ, where ϕ is first order, b is a binary predicate symbol, and the range of the second order quantifier is restricted to the class of matchings. Several variations and extensions are discussed.

I&C Journal 1990 Journal Article

Non-uniform automata over groups

• David A. Mix Barrington
• Howard Straubing
• Denis Thérien

A new model, non-uniform deterministic finite automata (NUDFA's) over general finite monoids, has recently been developed as a strong link between the theory of finite automata and low-level parallel complexity. Achievements of this model include the proof that width 5 branching programs recognize exactly the languages in non-uniform NC 1, NUDFA characterizations of several important subclasses of NC 1, and a new proof of the old result that the dot-dephth hierarchy is infinite, using M. Sipser's (1983, in “Proceedings, 15th ACM Symposium on the Theory of Computing, ” Association for Computing Machinery, New York, pp. 61–69) work on constant depth circuits. Here we extend this theory to NUDFA's over solvable groups (NUDFA's over non-solvable groups have the maximum possible computing power). We characterize the power of NUDFA's over nilpotent groups and prove some optimal lower bounds for NUDFA's over certain groups which are solvable but not nilpotent. Most of these results appeared in preliminary form in (D. A. Barrington and D. Thérien, 1987, in “Automata, Languages, and Programming: 14th International Colloquium, ” Springer-Verlag, Berlin, pp. 163–173).

STOC Conference 1987 Conference Paper

Finite Monoids and the Fine Structure of NC¹

• David A. Mix Barrington
• Denis Thérien

TCS Journal 1981 Journal Article

Classification of finite monoids: the language approach

• Denis Thérien

The concept of a ∗-variety of congruences is introduced and related to ∗-variety of languages and variety of monoids. A systematic construction of increasingly complex ∗-varieties of congruences is presented. This construction is powerful enough to generate all monoids containing solvable groups. Some hierarchies occurring through this process are shown to correspond to well-known hierarchies of monoids, thus indicating that our construction is natural from an algebraic point of view. Some problems that remain open are also discussed.