Transcript Slides

Finite monoids,
regular languages,
circuit complexity and logic
Pascal Tesson
Laval University, Quebec City, Canada
• Fact: Circuit complexity is difficult...
• ... so it’s important to develop numerous angles
of attack on the central questions.
• Logic has been very helpful.
(e.g. logical characterizations of AC0, ACC0.)
• Algebra has been helpful:
– Smolensky’s lower bounds.
– Programs over finite monoids (Barrington, Straubing,
Thérien).
P.Tesson
Dagstuhl Seminar on Circuits, Logic and Games
2
Quick circuit reminder
• NC1: languages recognized by family of AND/OR
circuits with fan-in 2 and depth O(log n).
• AC0: languages recognized by family of AND/OR
circuits with arbitrary fan-in, depth O(1) and
poly-size.
• ACC0: languages recognized by family of
AND/OR/MODq circuits with arbitrary fan-in,
depth O(1) and poly-size.
• CC0: languages recognized by family of MODq
circuits with arbitrary fan-in, depth O(1) and
poly-size.
P.Tesson
Dagstuhl Seminar on Circuits, Logic and Games
3
In this talk...
• Finite monoids to understand regular languages.
• Finite monoids to characterize boolean circuit
complexity classes.
• Finite monoids to understand the circuit
complexity of regular languages.
Regular languages
and finite monoids
Circuit complexity
P.Tesson
Dagstuhl Seminar on Circuits, Logic and Games
First order logic
over words
4
Outline
I.
II.
III.
IV.
V.
P.Tesson
Finite automata and finite monoids
Programs over finite monoids
Some tools for lower bounds
Circuit complexity of regular languages
Conclusion
Dagstuhl Seminar on Circuits, Logic and Games
5
Finite monoids and automata
• Monoid: set + binary associative operation +
identity element.
• Examples
– * is a monoid under concatenation. Empty word  is
the identity element.
– For every k, the set Tk of functions t:[k]  [k] forms
a monoid under composition.
– For a finite automaton A, each finite word induces a
transformation on the set of states. The transition
monoid of A is the submonoid of T|A|.
P.Tesson
Dagstuhl Seminar on Circuits, Logic and Games
6
Finite monoids = finite automata
• A finite monoid can be conveniently represented
by a finite automaton
– states: elements of the monoid.
– alphabet: elements of the monoid.
– transitions: (m,n) = mn
• Finite monoid  finite automata: just two points
of view.
P.Tesson
Dagstuhl Seminar on Circuits, Logic and Games
7
Def’n: A language L  * is recognized by the
finite monoid M if there exists homomorphism
:*  M and a subset F  M such that
-1 (F) = L.
Theorem: L is regular iff it is recognized by some
finite monoid M.
Def’n: The syntactic monoid of L is the transition
monoid of its minimal automaton.
P.Tesson
Dagstuhl Seminar on Circuits, Logic and Games
8
Algebraic automata theory
Why use this algebraic point of view?
• Important classes of regular languages can be
characterized by the algebraic properties of
their syntactic monoids.
• Often gives algorithms to test membership in a
given class of regular languages.
P.Tesson
Dagstuhl Seminar on Circuits, Logic and Games
9
Star-free languages
• A regular language is star-free if it can be
defined by a regular expression using , ;,
concatenation and boolean operations but
without the Kleene star.
• Example: L = (ab)* is a star-free language since
L = ;cb Å a;c Å (;caa;c)c Å (;cbb;c)c
• But how does one decide whether a given regular
language is star-free?
P.Tesson
Dagstuhl Seminar on Circuits, Logic and Games
10
Theorem: [Schützenberger]
L is star-free iff its syntactic monoid is
aperiodic, i.e. contains no non-trivial subgroup.
It can also be shown that M is aperiodic iff there
exists n s.t. xn+1 = xn for all x 2 M.
P.Tesson
Dagstuhl Seminar on Circuits, Logic and Games
11
Logic over words
View finite words over  as a linearly ordered -colored
structure.
We construct first-order sentences using the following
atomic formulas:
1. for each a 2  a unary predicate Qa
w ² Qax
iff wx = a
2. x < y
(with the obvious semantics)
We can also augment the logic with modular counting
quantifiers.
9i mod p x (x)
(there exist i modulo p x’s s.t.  holds)
P.Tesson
Dagstuhl Seminar on Circuits, Logic and Games
12
1.
x y Qax  ((y < x)  Qby)
defines the language b*a*
2. To define (ab)* we can use the sentence:
8x 8y (Qb x ! [9 z (z<x)]) Æ (Qax ! [9 z (x < z)]) Æ
[((x  y) Æ Qax Æ Qay) Ç ((x  y) Æ Qb x Æ Qby)]
! 9 z [(x <z<y) Ç (y <z<x)]
P.Tesson
Dagstuhl Seminar on Circuits, Logic and Games
13
Theorem: [McNaughton-Papert]
L is star-free iff it is definable in FO[<] iff L’s
syntactic monoid is aperiodic.
Theorem:
L is definable in FO+MOD[<] iff its syntactic
monoid is solvable.
Theorem:
L is definable in MOD[<] iff its syntactic monoid
is a solvable group.
P.Tesson
Dagstuhl Seminar on Circuits, Logic and Games
14
Outline
I.
II.
III.
IV.
V.
P.Tesson
Finite automata and finite monoids
Programs over finite monoids
Some tools for lower bounds
Circuit complexity of regular languages
Conclusion
Dagstuhl Seminar on Circuits, Logic and Games
15
From homomorphisms to programs
a1
a2
...
an-1
an
homomorphism 
m1
m2
...
mn-1
mn
Multiply in M
result is m = (input)
accept if m  F
P.Tesson
Dagstuhl Seminar on Circuits, Logic and Games
16
From homomorphisms to programs
a1
a2
...
an-1
an
program over M: each output
element depends on a single
input position
m1
m2
m3
...
ms-1
ms
Multiply in M
result is m = (input)
accept if m  F
P.Tesson
Dagstuhl Seminar on Circuits, Logic and Games
17
Programs over monoids
An n-input program  over M of length s is a sequence of
instructions I1 I2 ... Is where each instruction is a pair:
Ij = (fj, kj) where fj:  M and 1  kj  n.
The output of  on input w = a1 ... an is the monoid element
(w) = f1(ak1)  f2(ak2)  ...  fs(aks)
A language L  n is recognized by a program  over M if
there exists F  M such that w  L iff (w)  F.
P.Tesson
Dagstuhl Seminar on Circuits, Logic and Games
18
Programs over monoids
To recognize subsets of * we use a family {n}n  0 where
each n processes inputs of length n. The length of such
a family is then a function of n.
Often, we require that {n}n ¸ 0 is s.t. the nth program is
constructible within some resource bound.
) uniformity restrictions. (not our problem today!)
P.Tesson
Dagstuhl Seminar on Circuits, Logic and Games
19
Bounded-width branching programs
• Programs over monoids: originally a point of view on
bounded width branching programs.
x1
x7
x5
x1
On input x1x2 ... xn: the red arrows are followed when the queried
bit is 0, the blue arrows are followed when the bit is 1.
For example if x1 = 0, x7 = 1.
P.Tesson
Dagstuhl Seminar on Circuits, Logic and Games
20
Barrington’s theorem
Theorem: [Barrington]
A language lies in NC1 iff it can be recognized by
a polynomial length family of programs over a
finite monoid. In fact, any simple non-Abelian
group will do.
Recall: the commutator of two group elements
[g,h] = g-1h-1gh.
If G is simple and non-Abelian, then [G,G] = G.
P.Tesson
Dagstuhl Seminar on Circuits, Logic and Games
21
Barrington’s theorem (proof)
Easy direction: show that L recognized by a polylength program over a finite monoid ) L 2 NC1.
(more on this later)
Hard direction: suppose L 2 NC1 and G simple nonAbelian. Show by induction on depth d: if C is an
AND/OR circuit with binary fan-in and g 2 G,
there is a program C,g of length O(4d) whose
output is g if C evaluates to 1 and 1G otherwise.
P.Tesson
Dagstuhl Seminar on Circuits, Logic and Games
22
Barrington theorem’s proof (cont’d)
Suppose for simplicity that g = [g1,g2] and assume
the ouput of C is AND(C1,C2). By induction,
exists C1,g1 and C2,g2 of length O(4d-1).
Define C,g = [C1,g1,C2,g2]
If C1 = 0 then C1,g1 outputs 1G and so
[1G,C2,g2] = C2,g21 C2,g2 = 1G.
If C1 and C2 both evaluate to 1, the program C,g
outputs [g1,g2] = g.
P.Tesson
Dagstuhl Seminar on Circuits, Logic and Games
23
• Alternative point of view: if L is a regular
language whose syntactic monoid is non-solvable
then L is NC1 complete under non-uniform
projections.
P.Tesson
Dagstuhl Seminar on Circuits, Logic and Games
24
Algebraic characterizations in NC1
Theorem:
K 2 AC0 iff K is recognized by a poly-length
program over a finite aperiodic monoid.
K 2 CC0 iff K is recognized by a poly-length
program over a finite solvable group.
K 2 ACC0 iff K is recognized by a poly-length
program over a finite solvable monoid.
P.Tesson
Dagstuhl Seminar on Circuits, Logic and Games
25
Contrast with:
Theorem:
K 2 AC0 iff K is definable in FO[Arb], i.e. FO
extended with arbitrary numerical predicates.
K 2 CC0 iff K is definable in MOD[Arb].
K 2 ACC0 iff K is definable in FO+MOD[Arb]
P.Tesson
Dagstuhl Seminar on Circuits, Logic and Games
26
So what?
Looks nice but how is that useful?
1.
Provides some insight into the power and limitations of
these circuit classes. Since AC0 corresponds to
aperiodic monoids, it’s natural to see PARITY as the
canonical example of a language that these circuits
can’t compute.
2. Separation conjectures can be reformulated
algebraically. Showing CC0  ACC0 translates into show
AND cannot be computed by a poly-length program
over a solvable group.
3. Roadmap: start with very simple classes of solvable
groups and work your way up.
4. More generally, finer grain in the analysis: the power of
the program depends both on length and on structure
of underlying monoid.
P.Tesson
Dagstuhl Seminar on Circuits, Logic and Games
27
Some results
Theorem: [Barrington-Straubing]
If L has a neutral letter and is recognized by a
program of length o(n log log n) over some finite
monoid M then L can be recognized via morphism
by a direct product of M and its reverse Mr.
P.Tesson
Dagstuhl Seminar on Circuits, Logic and Games
28
Theorem [Barrington-Straubing-Thérien]
Any program over a group G such that [G,G] is a
p-group requires exponential length to compute
AND.
P.Tesson
Dagstuhl Seminar on Circuits, Logic and Games
29
Outline
I.
II.
III.
IV.
V.
P.Tesson
Finite automata and finite monoids
Programs over finite monoids
One useful tool for lower bounds
Circuit complexity of regular languages
Conclusion
Dagstuhl Seminar on Circuits, Logic and Games
30
Communication complexity
•
•
k players collaborate to determine if an input string w = a1 a2 ... an belongs
to a given language L.
The player j sees each ai except those such that i  j (mod k).
a1 a4 a7 ...
a2 a5 a8 ...
a3 a6 a9 ...
The k-party communication complexity of L is the least amount of bits that
the parties need to exchange in the worst-case to determine if their
input belongs to L.
One can similarly define the communication complexity of a monoid M as
the complexity of evaluating the product m1m2 ... mn in M.
P.Tesson
Dagstuhl Seminar on Circuits, Logic and Games
31
A general framework for lower bounds
Theorem:
If M has communication complexity O(f), then
any language recognized by a program of length
s over M has communication complexity at most
O(f(s)).
The same holds for various variants of the
communication complexity model.
This gives an algebraic point of view on these
lower bound techniques and exposes their limits.
P.Tesson
Dagstuhl Seminar on Circuits, Logic and Games
32
Theorem: [T., Thérien]
In the two-party model, a monoid M has
communication complexity:
(1) iff M is commutative
(log n) iff M is non commutative but every
subgroup of M is abelian and M satisfies
(xy)n(yx)n(xy)n = (xy)n for some n. (we denote
this class as DO Å H(Ab) )
(n) otherwise.
P.Tesson
Dagstuhl Seminar on Circuits, Logic and Games
33
Outline
I.
II.
III.
IV.
V.
P.Tesson
Finite automata and finite monoids
Programs over finite monoids
One useful tool for lower bounds
Circuit complexity of regular languages
Conclusion
Dagstuhl Seminar on Circuits, Logic and Games
34
• The classical result PARITY  AC0 shows that
understanding the circuit complexity of regular
languages is central to progress in the field.
• By the algebraic characterizations of AC0, CC0
and ACC0 we already have good tools for a first,
rough classification.
• How precise can we be about the circuit
complexity of regular languages?
P.Tesson
Dagstuhl Seminar on Circuits, Logic and Games
35
Theorem: [Koucký, Pudlák, Thérien]
A regular language (with a neutral letter) can be
computed by an ACC0 circuit using O(n) wires iff
its syntactic monoid lies in DO Å H(Ab).
Theorem: [Chandra, Fortune, Lipton]
Any regular language in ACC0 can be computed by a
circuit using only O(ng-1(n)) wires for any
primitive recursive g.
P.Tesson
Dagstuhl Seminar on Circuits, Logic and Games
36
Some ideas of the proof
The upper bound relies on the combinatorial
characterization of the regular languages with
syntactic monoids in this class.
For the lower bound: deep results about
superconcentrators are needed to show that if L
is regular with 2-party communication
complexity (n) then L requires a superlinear
number of wires.
P.Tesson
Dagstuhl Seminar on Circuits, Logic and Games
37
Open problem
Question: What regular languages can be
computed by an AC0, CC0 or ACC0 circuit using
only linearly many gates?
Hint: These correspond exactly to FO2[Arb],
MOD2[Arb] and FO+MOD2[Arb]. (see
[Koucký,Lautemann,Thérien])
Conjectured answers:
It is believed that the answer will have some
algebraic form. In particular: show that AC0
circuits for (ab)* require a superlinear number
of gates in the presence of a neutral letter.
P.Tesson
Dagstuhl Seminar on Circuits, Logic and Games
38
Conclusion
Open problems suggested by the algebraic point of
view:
– Show that AND cannot be computed by poly-length
program over S4.
– Show that AND cannot be computed by poly-length
program over a super-solvable group.
P.Tesson
Dagstuhl Seminar on Circuits, Logic and Games
39