数理解析研究所講究録
1533 巻 2007 年 24-38

24Characterizations and Problems on LOGCFL
黒田覚 (Satoru Kuroda)
群馬県立女子大学

Gunma Prefectural Women’s University

Introduction

1

The class LOGCFL is defined as those sets LOGSPACE-reducible to contextfree languages and it turned out that the class has alternative characterizations based on Boolean circuits, word problems on groupoids and so on.
The class is also known to enjoy approaches from logic such as descriptive
complexity, bounded arithmetic and satisfiability problem. In this note wewill review some of these results together with open problems.

What is LOGCFL?

2First we will define the class LOGCFL. Throughout this note, we will consentrate on the string language. Let $\Sigma=\{0,1\}$ . We denote the set of finite
strings over by . We denote the length of a string by .
We assume the reader the familiarity with basic definitions of formal
language theory.
$\Sigma^{*}$$\Sigma$$x$

Definition 1 A context-free grammar $(CFG)$ is a quadraple$|x|$$G=\langle N, \Sigma, P, S\rangle$

where,$\bullet$$\bullet$$N$

is a finite set of nonterminal symbols,$P$

is a finite set of rules of the form$(N\cup\Sigma)^{*}$$\bullet$$S\in N$A string$A\Rightarrow G$,

a where $A\in N$ and a$\in$is called the start symbol.

$w\in\Sigma^{*}$

is generated by$G$

if there exists a finite sequence such that$s\mathrm{g}_{\alpha_{1}}\mathrm{g}_{\alpha_{2}}s\ldots\Rightarrow wG$

.

25

A set
that

$A\subseteq\Sigma^{*}$

is a context-free language (CFL) if there exists a CFG$\forall w\in\Sigma^{*}$($w\in A\Leftrightarrow w$

is generated by$G$$\mathrm{G}$

such

).

We will also assume basic notions of Turing machines and computational
complexity.
Deflnition 2 Let $A,$
is logspace many-one reducible to $B$ (de) if there exists a logspace bounded computable function
noted bysuch that$B\subseteq\Sigma^{*}.$$A$$A\leq_{m}^{log}B$$f$$\forall w\in\Sigma^{*}(w\in A\Leftrightarrow f(w)\in B)$.

Now we can define the class LOGCFL as
Deflnition 3 LOGCFL $=\{A\subseteq\Sigma^{*} : \exists B:CFL(A\leq_{m}^{log}B)\}$ .
Remark. The class LOGCFL is a “uniform” class, that is all sets in
LOGCFL are recursive.

3

Circuit characterization

The class LOGCFL has several alternative characterizations. First we will
give a circuit based characterzation established by Venkateswaran [11].
A Boolean circuit with inputs is a directed acyclic graph $C$ such thatehac vertices are labeled as follows:$\mathrm{H}$$n$$\bullet$a vertice of indegree$x_{1},$$\bullet$$\ldots,$$x_{n},$$x_{1}^{-},$$\ldots,$$x_{n}^{-}$a vertice of indegree
one of and V.

$0$,

is called an input and labeled by either one of$\geq 1$is callled a (inner) gate and labeled by either$\wedge$A gate with outdegree is called an output of the circuit. In this note we
consider only single-output circuits.
The computation of a circuit $C$ on input with $|x|=n$ is done by
bit ofassigning the
bit of to each input , the complement of
to each input , and evaluating each inner gate using the truth table of its
label. Thus a circuit with input computes a predicate on “.
contains strings of arbitraryOn the other hand, any infinite set
lengths. So we need infinitely many circuits to decide it. We formalize thisas follows:
$0$

$x$

$i\mathrm{t}\mathrm{h}$$i\mathrm{t}\mathrm{h}$$x$$x_{i}$$\overline{x}_{i}$$\Sigma$$n$$A\subseteq\Sigma^{*}$

$x$

26
is computed by a circuit family
Deflnition 4 A set
is a circuit with inputs andif for all$A\subseteq\Sigma^{*}$$n\in\omega_{f}C_{n}$$C=\{C_{n}\}_{n\in\omega}$$n$$\forall x\in\Sigma^{n}(X\in A\Leftrightarrow C_{n}$accepts$x$.

We are interested in deciding the complexity of the circuit family which. To measure the complexity, we introduce thecomputs a given$A\subseteq\Sigma^{*}$

following notations:
Let $C$ be a circuit. The size of $C$ (denoted by size $(C)$ ) is the numberof gates in $C$ . The depth of (denoted by depth $(C)$ ) is the maximum oflengths of paths from an input to the output. Note that the size and thedepth of a circuit family are functions of the length of inputs.
A circuit family
is called bounded fan-in if indegrees of gates inare bounded by some constant. Otherwise it is called unbounded fan-in.
Further more it is called semi-unbounded fan-in if indegrees of A-gates arebounded by a constant while those of -gates are not bounded.
Now we define circuit complexity classes.
$C$

$n$

$\{C_{n}\}_{n\in\omega}$$C_{n}$$\vee$. We define the class
Deflnition 5 Let
to be the class of sets
which can be computed by an unbounded fan-in family of circuits withdepth $O((\log n)^{i})$ and size
. The classes
and $SAC^{i}$ are definedin the same manner as
for bounded fan-in and semi-unbouded fan-in
circuits.
$AC^{i}$$i\in\omega$$A\subseteq\Sigma^{*}$$n^{O(1)}$$NC^{i}$$AC^{i}$

Note that these circuit classes are non-uniform. In fact, there exists
ancircuit family computing a non-recursive set. In roder to consider
inclusion relations between circuit classses and classes defined by other computation models, we need uniform version of these classes. So we define thefollowing uniform notion.
$NC^{0}$Definition 6 Let
be circuit family. The Direct Connection Lan$(g,$(DCL)$
guage
is the set of h, l,0^{n})$ where receives an input from inand is a label of . The familyis-uniform if its $DCL$ is
DLOGTIME-computable.
$\{C_{n}\}_{n\in\omega}$

$h$

$g$

$C_{n}$$l$$g$$\{C_{n}\}_{n\in\omega}$$U_{E}*$

We assume-uniformity for any circuits class unless otherwise stated.
For the relation between LOGCFL and circuit classes, Venkateswaran[11] proved the following suprising result.
$U_{E}*$

Theorem 1 (Venkateswaran [11]) The class LOGCFL is equal touniform SAC 1.

$U_{E}$.

-

27
This gives the following inclusions neither of which is known whether it isproper or not:$L\subseteq NL$ $c$

LOGCFL $=SAC^{1}\subseteq AC^{1}$ .

The problem whether LOGCFL is closed under complementation operation is not obvious and was proved by Borodin et. al. The proof isthe application of the inductive counting argument by Immerman [6] andSzelepsc\’enyi [10].

Theorem 2 (Borodin et.al. [1]) The non-uniform SACi is closed undercomplementation.

(Proof Idea). Let
be an SAC1 circuit with inputs whose depth andso that therespectively. We can transform
width areandresulting circuit has at most polynomial increase of width and satisfies thefollowing conditions:$C$$|\alpha(n)|$

$n$

$C$

$\beta(n)$1. synchronicity: all inputs are on row , output is on row
all gates on row receive inputs from row $k-1$ ,$0$$2|\alpha(n)|$

, and

$k$

2. strict alternation: for $0<k<|\alpha(n)|$ all gates on row $2k$ are AND
gates and all gates on row $2k-1$ are OR gates.
Based on this reformulation of the original circuit, we construct theinductive counting circuit to compute its complement. The general idea ofthe construction is to add two kinds of gates. The first kind is called the“contingent complement gate”. Let be a gate in $C$ and be a number
less than or equal to the width of $C$ . Then a contingent complement gate
$cc(g|c)$ outputs 1 if and only if
outputs , provided that is the number
of l’s in the input rows to .
The second kind is the”counting gate”,denoted by COUNT $(c, k)$ , which
outputs 1 if and only if the number of l’s in the -th row of $C$ is equal to
$c$

$g$

$g$

$0$

$c$

$g$

$2\mathrm{k}$$c$.

Thus computing the disjunct of all $cc(g|c)$ A COUNT $(c, k)$ for $0\leq c\leq$$width(C)$ computes the complement of the original gate on row $2k$ .
Next let us see how each gates above are defined. The definition of The
according to the row of . If iscontingent complement gate
$2k$(that is, is an AND gate) thenon row$g$$cc(g|c)\mathrm{d}\mathrm{i}\mathrm{f}\mathrm{f}\mathrm{e}\mathrm{r}8$$g$$cc(g|\mathrm{c})=cc(h_{0}|c)\vee cc(h_{1}|c)$

$g$

$g$

28
and
where
gate) then$h_{0}$$h_{1}$are inputs to$g$. If is on row $2k-1$ (that is,$g$$cc(g|c)=c- THRES$ { $h:h$ is the non-input of

$g$

$g$

is an ORon row $2k-2$ },where -THRES outputs 1 if and only if the number of l’s in its inputs are
more than or equal to .
The counting gate COUNT $(c, k)$ is inductively defined as
$c$

$c$

COUNT $(c, k)=\beta(n)d=0\vee AND(COUNT(d, k-1),$ TH 1 $(c, k),$$TH\mathrm{O}(c, k, d))$,where $TH$ I $(c, k)$ is the -THRES of all original gates (that is gates in ) on
is the $(c-d)$ -THRES of all $cc(g|c)$ where is therow $2k$ andoriginal gate on row $2k$ .
Finally, let
be the output gate of the original circuit. Then thecomplement can be computed by
$C$

$c$

$TH\mathrm{O}(c, k, d)$$g$$g_{out}$$\vee$$(cc(g_{out}|c)\wedge COUNT(c, \alpha(n)-1))$.

$0\leq c\leq\beta(n)$Note that throughout the construction, gates likeare defined using arbitrary threshold gates and replac
which is given by

c-THRES$=\vee^{c}$

TH 1 andby SACi subcircuits$TH\mathrm{O}$$c\mathrm{c}(g|c),$$e\mathrm{d}$$(x_{1}, \ldots, x_{n})$(k-THRES$(x_{1},$$\ldots,$$x_{\lfloor\frac{n}{2}\rfloor}k=0)$

A $(c-k)- THRES(x_{\lfloor\frac{n}{2}\rfloor+1’)}\ldots x_{n})$ ).

Corollary 1 The class LOGCFL is closed under complementation.

This closure property guarantees the robustness of the corresponding
function class. Let
be the class of functions :
such
that
$\mathcal{F}_{LOGCFL}$$\bullet$$\bullet$there exists a polynomial$\Sigma^{*}arrow\Sigma^{*}$

$f$

$p$

such thatthe predicate “the ith bit of$f(\tilde{x})$$|f(\overline{x})|\leq p(|\vec{x}|)$.

is 1” is computed in LOGCFL.

Then we have
Corollary 2 The class .7 LOGCFL is closed under complementation.

29

Logic for LOGCFL

4

It is a fundamental problem in comptational complexity to give logical characterizations, or to find logical properties for complexity classes.

Descriptive characterization

4.1

Descriptive complexity can be seen as an application of model theory tocomplexity theory. The intuitive idea is as follows: given an algorithm A fora problem, we express it by a logical formula . Similarly an input to thealgorithm can be exressed by a structure $A$ with universe $\{0,1, \ldots, n-1\}$
where is the length of the input so that$\varphi_{A}$$n$$A\models\varphi_{A}\Leftrightarrow A$

accepts the input expressed by $A$ .

Generally speaking, the computational complexity of.
logical complexity of
To formalize this correspondence we define$A$

corresponds to the$\varphi_{A}$Definition 7 Let be a class of formulae and $C$ be a complexity class. $We$
say that captures $C$ (over arithmetical structures) if$\Phi$$\Phi$

1. for all$A\models\Phi$there exists an algorithm in$A$structure.
where is an a$\varphi\in\Phi$$C$which checks whether$r\dot{\tau}thmetical$

2. for all $L\in C$ there exists$\varphi\in\Phi$such that$A\models\varphi\Leftrightarrow bin(A)\in L$

where bin $(A)$ is a suitable binary coding of $A$ .
For example following correspondence is known:$\bullet$The class of existential second order formulae$NP$$\bullet$.

$SO\exists$

captures the class

The class of first order formulae $FO$ captures the class$AC^{0}$.

A descriptive characterization for the class LOGCFL is first given by
Vollmer et. al. by way of generalized quantifiers expressing word problems
for finite groupoids. See [12].
A similar characterization using the alternation path in SACi circuits
are given in Kuroda [9].

30
4.2

Satisfiability problem for LOGCFL

Satififiability problems are typical complete problems for several complexity
classes. For example, the satisfiability for propositional formulae called SAT-complete. Also restrictions to the form of propositional formulae leadsisto complete problems: the satisfiability for Horn formula (Horn-SAT) andare complete for and NL respectively.
The satisfiablity for LOGCFL was given by Gottlob et. al. [5] in aslightly different form. Boolean conjunctive queries are regarded as seaching witnesses to given conditions over relational databeases. Consider thefollowing example:$\mathrm{N}\mathrm{P}$$\mathrm{P}$$\mathit{2}\mathrm{C}\mathrm{N}\mathrm{F}(\mathit{2}\mathrm{S}\mathrm{A}\mathrm{T})$Example 1 Suppose that we have a relational database with the following
relational schema:
u-tokyo(Student, Year, Faculty),
kyoto-u(Student, Year, Faculty),
sisters(Student 1, Student2).

We can consider the following$Q_{1}$$quer\dot{\mathrm{v}}es$over this database.

: $ansarrow u- tokyo(S1, \mathrm{Y}, F)$ A kyoto-u$(S2, \mathrm{Y}, F’)$A sisters $(S1, S2)$ ,: $ansarrow u- tokyo(S1, \mathrm{Y}, F)\wedge kyoto- u(S2, \mathrm{Y}’, F’)\wedge sisters(S1, S2)$,: $ansarrow body$ and if body is a
In general, queries are of the form
conjunction of atomic formulae then the query is called a Boolean conjunctive
query.
A Boolean conjunctive query is expressed as a hypergraph, that is,
the pair $G=(V, E)$ where$Q_{2}$$Q$$Q$$V=\mathrm{t}\mathrm{h}\mathrm{e}$

$E=$

{

set of variables occurring in ,, ) : nameis a conjunct in$(v_{1},$$Q$$\ldots$$v_{k}$$(v_{1},$$\ldots,$$v_{k})$$Q$}.

A Boolean conjunctive query is called cyclic (acyclic) if the correspondingandin example 1 are
hypergraph is cyclic (resp. acyclic). Note thatcyclic and acyclic respectively.
Now let us briefly formalize this argument. A relatinal schema consistsof a name of a relation and a finite ordered list of attributes. In Example
1, sister(Student 1, Student2) is a relational scheme with a name sister andattributes Studentl and Student2.
For an attrubute $A,$ $Dom(A)$ be a countable domain of atomic values.
Let $R=(A_{1}, \ldots, A_{k})$ be a relation. A relation instance is a subset$S\subseteq Dom(A_{1})\cross\cdots\cross Dom(A_{k})$ so that $|S|<\omega$ . A database schema $DS$
consists of a finite set of relation schemata.
Database db over $DS=\{R_{1}, \ldots, R_{m}\}$ consists of:$Q_{1}$$Q_{2}$

$R$

$r$

31

$\bullet$$\bullet$relation instance
universe$r_{1},$$\ldots,$$r_{m}$

for$R_{1},$$\ldots,$$R_{m}$, and$U \subseteq\bigcup_{R_{i}(A_{1}^{i},\ldots,A_{k_{i}}^{i})\in DS}Dom(A_{1}^{i})\cup\cdots\cup Dom(A_{k_{i}}^{i})$,such that all data values in db are from .
Now we define conjunctive query on database schema as follows:$U$

Definition 8 Let $DS=\{R_{1}, \ldots, R_{m}\}$ be a database schema. A conjunctive
query on $RS$ consists of a rule of the form
$Q$

$Q:ans(u)arrow r_{1}(u_{1})\wedge\cdots r_{n}(u_{n})$

where
and

$r_{1},$$DS_{f}$$\ldots,$$u_{1},$$r_{n}$$\ldots,$are relation names in $DS$ , ans is a relation name not inare terms of appropriate length.

$u_{n}$

Next we define the satisfaction relation for conjunctive queries. For a
conjunctive query we define $var(Q)$ to be the set of variables occurringin it and atom $(Q)$ to be the set of atomic formulae occurring in its body.
$Q$

Definition 9 The answer of a conjunctive query on a database db withconsists of a relation ans whose arity is equal to theassociated universe
length of defined as follows:
$Q$

$U$

$u$

ans contains all tuples $uS$ where $S:var(Q)arrow U$ is a substitution replacing each variable in $var(Q)$ by a value of so that$U$$r_{i}(u_{i})S\in \mathrm{d}\mathrm{b}$We say thatfor all$1\leq i\leq n$.

evaluates to true on db if there exists a substitution
db for all $1\leq i\leq n$ .

$Q$that $r_{i}(u_{i})S\in$

$S$

such

We say that is a Boolean conjunctive query if its head does not containvariables.
As stated above, we can associate a hypergraph $H(Q)=(V, E)$ for eachconjunctive query which is defined as:
$Q$

$Q$

$\bullet$$\bullet$$V$

is the set of variables occurring in

$Q$

,

if
is an atomic formula occurring in the body oftains a hypergraph consisting of all variables in .
$r_{i}(u_{i})$$Q$then $E$ con-$u_{i}$

is an acyclic conjunctive query if $H(Q)$ is acyclic.
Finally we define the satisfiability of (acyclic) Boolean conjunctive query
as follows:$Q$

32
BCQ: Given a database db and a Boolean conjunctive query
whether evaluates to true on
.
$Q$

$Q$

. Decide$\mathrm{d}\mathrm{b}$ABCQ: Given a database db and an acyclic Boolean conjunctive query
Decide whether evaluates to true on
.
$Q$

$Q$

.

$\mathrm{d}\mathrm{b}$Note that $BCQ$ was previously known to belowing result is rather surprising:$\mathrm{N}\mathrm{P}$-complete. So the fol-

Theorem 3 (Gottlob et.al. [5]) The problem ABCQ is complete for LOGCFL
under logspace reduction.

4.3

Bounded arithmetic

The main idea of bounded arithmetic is to characterize a given function classas provably total functions in a weak subsystems of Peano Arithmetic or its
variants. More precisely, let be a class of formulae.. Then a function
is said to be -definable in a system if there exists a formula
such
that
$\Phi$$f$$T$$\Phi$$\varphi\in\Phi$$T\vdash(\forall x)(\exists!ty)\varphi(x, y)$$\mathrm{N}\models(\forall x)\varphi(x, f(x))$.

,

S. Buss [2] was the first to give such systems for levels of the polynomial
time hierarchy. Namely, he defined a series of systems
such that$S_{2}^{i}(i\geq 0)$

Theorem 4 For $i\geq 1$ , a function is polynomial time computable with anoracle from
if and only if it is definable in .
$\Sigma_{i-1}^{p}$$\Sigma_{i}^{b}$$S_{2}^{i}$Buss’ systems are defined in the language of natural numbers. On theother hand, S. Cook and his students developed a theory of binary strings
called two-sort systems and based on this formulation, A. Kolokolova [8] gave
a relation between descriptive complexity and two-sort bounded arithmetic.
Furthermore, the author [9] used Kolokolova’s argument to define a twosort system whose provably total functions are exactly those bitwise computable in LOGCFL. In the following we briefly review this work.
The languageof two sort systems has two kinds of variables, namely$L_{2}$$\bullet$$\bullet$number variables denoted by lower case letters$x,$ $y,$ $z,$

string variables denoted by upper case letters $X,$

$Y,$ $Z,$$\ldots$, and$\ldots$

and contains function symbols $Z(x)=0,$ $s(x)=x+1,$ $x+y,$$|X|$ (thelength of string $X$ ) and a relation symbol $x\leq y$ . Terms and formulae arebuilt up in the usual manner. The standard model ofis the pair.
$x\cdot y,$$L_{2}$$(\mathrm{N}, \Sigma^{*})$

33
are called bounded numand
Quantifiers of the form
not including . Quantifiers of the form
ber quantifiers where is a
are called bounded string quantifiers whose intended$(\exists x\leq t)$$(\forall x\leq t)$

$t$

$x$

$\mathrm{t}e\mathrm{r}\mathrm{m}$$\mathrm{m}\mathrm{e}\mathrm{a}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{s}\mathrm{a}\mathrm{r}\mathrm{e}(\forall X\leq t)\mathrm{a}\mathrm{n}\mathrm{d}(\exists X\leq t)$$(\forall X\leq t)\varphi\equiv(\forall X)(|X|\leq tarrow\varphi)$,$(\exists X\leq t)\varphi\equiv(\exists X)(|X|\leq t\wedge\varphi)$

where is a term not containing $X$ .
to be the class of -formulae in which all quantifiers are
We definebe the class of -formulae in which allbounded number quantifiers andquantifiers are either bounded number quantifiers, positive occurrences ofbounded existential string quantifiers, or negative appearances of bounded
universal string quantifiers.
by introducing an operator which applies
We augment the language
be an -formula with free variables as
to -formulae. Let
terms with the only parameter . Then webeandshown andintroduce a new relation$t$$L_{2}$$\Sigma_{0}^{B}$$L_{2}$$\Sigma_{1}^{B}$$L_{2}$$\varphi(g, h, z,\overline{x},\overline{\mathrm{Y}})$$L_{2}$$\alpha(z)$$\beta(z)$$L_{2}$$z$$L_{2}$$\mathrm{Q}^{SAC}[\varphi(g, h, z,\overline{x},\overline{\mathrm{Y}}), \alpha(z), \beta(z)](t,n,\overline{p},\overline{Q},X)$$(*)$

extended by
to be
For a class of -formulae we define
be the class of formulae of the form
. Let
for all$(*)$ where.
be an SAC1 circuit
The intended meaning of $(*)$ is as follows: Let
respectively, andandwith inputs whose depth and width are, that is, receives
its direct connection language is given by. Here and denote thean input from if and only if$\Phi$$\mathrm{Q}^{SAC}[\varphi]$$QL_{2}(\Phi)$$L_{2}$$\varphi\in\Phi$$L_{2}$$\mathrm{Q}^{SAC}(\Phi)$$\varphi\in\Phi$$C_{\varphi,\alpha,\beta}$$|\alpha(n)|$$n$$\beta(n)$$h$$\varphi(g, h, n,\overline{p},\overline{Q})$$g$$\varphi(g, h, n,\overline{p}_{)}\overline{Q})$

$h$

$g$

$\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{s}.\mathrm{o}\mathrm{f}\mathrm{g}\mathrm{a}\mathrm{t}\mathrm{e}\mathrm{s},\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{t}\mathrm{h}\mathrm{r}\mathrm{o}\mathrm{u}\mathrm{g}\mathrm{h},\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{e}\mathrm{i}\mathrm{d}\mathrm{e}\mathrm{n}\mathrm{i}\mathfrak{h}^{r}\mathrm{g}\mathrm{a}\mathrm{t}\mathrm{e}\mathrm{s}\mathrm{w}\mathrm{i}\mathrm{t}\mathrm{h}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{i}\mathrm{r}\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{T}\mathrm{h}\mathrm{e}\mathrm{n}\mathrm{Q}^{SAc_{[\varphi(g,h,z}\frac{\mathrm{t}}{p}}\frac{}{x},\overline{Y}),\alpha(Z),\beta(z)](t,n,,\overline{Q},X)\mathrm{h}\mathrm{o}1\mathrm{d}_{\mathrm{S}}\mathrm{i}\mathrm{f}\mathrm{t}\mathrm{d}$only if there exists an “ alternating path” $Z$ from the input $X$ to the gate
which satisfies:$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$Z$

contains no input node whose value is ,$Z$

contains at least one node whose value is 1,

if

if

$0$

$g$

$g$

is an AND gate and all its offsprings are in$Z$

is an OR gate and some of its offsprings is in

the gate is at the top of
$t$

$Z$

.

then so is ,
$g$

$Z$

then so is ,
$g$

$t$

34

accepts the input $X$ if and only if there exists
Note that the circuit
such an alternating path .
-uniform $SAC^{1}$ , we will concentrate on
Since we are interested in the.
the language
Now we will formalize the above conditions to give the defining axiom for. First of all, the defining axiom formust containthe operator
that
sayingdefines a circuit. Remember that the combinatorial
formulaestructure of circuits is that of directed acyclic graphs. In our setting, circuits. This is explained as
are coded by the tuple
follows:$C_{\varphi,\alpha,\beta}$$Z$$\mathrm{F}\mathrm{O}$$QL_{2}(\Sigma_{0}^{b})$$\mathrm{Q}^{SAC}$$\mathrm{Q}^{SAC}$$\varphi$$\langle\varphi(g, h, z,\overline{x},\overline{Y}), \alpha(z), \beta(z)\rangle$$\bullet$$\bullet$$\bullet$each gate infor$C_{\varphi,\alpha,\beta}$

is assigned an unique vaiue $g<|\alpha(n)|\cdot\beta(n)$ ,$g,$ $h<|\alpha(n)|\cdot\beta(n),$$C_{\varphi,\alpha,\beta}$

is divided into

So two gates

$g$

and

$h$

$g$

is an input of$|\alpha(n)|$

$h$

if

$\varphi(g, h, z,\overline{x},\overline{Y})$rows, each containing

are in the same row if and only if$\beta(n)$, andgates.

$\lfloor_{\overline{\beta}}n\mathrm{b}\rfloor=\lfloor\frac{h}{\beta(n)}\rfloor$.

For the sake of readability, we defineand$Rem(g, \beta(n))$ to denote the vertical and horizontal positions of the gate
respectively. We omit the subscript if it is clear from the context. Notedefinable in .
that these functions are
Now gives an edge
for a directed acyclic graph if whenever$g<|\alpha(n)|\cdot\beta(n)$ receives an input from $h<|\alpha(n)|\cdot\beta(n)$ then row $(g)\leq l(h)$ .
We define this formally as$\mathrm{r}\mathrm{o}\mathrm{w}_{\beta}(g)=\lfloor_{\partial}\mathrm{b}"\rfloor$$\mathrm{c}\mathrm{o}1_{\beta}(g)=$$g$$\beta$$V^{0}$$\Sigma_{0}^{B}$$\mathrm{r}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\dot{\mathrm{n}}$$\varphi$$Circuit_{\varphi(g,h,z,\overline{x},\overline{\mathrm{Y}})}^{\alpha,\beta}(n,\overline{p},\overline{Q})$$\Leftrightarrow(\forall g<|\alpha(n)|\cdot\beta(n))(\forall h<|\alpha(z)|\cdot\beta(z))(\varphi(g, h, n,\overline{p},\overline{Q})$$arrow \mathrm{r}\mathrm{o}\mathrm{w}_{\beta}(g)<\mathrm{r}\mathrm{o}\mathrm{w}\rho(h))$.

We will not add formulae to explain what semi-unbounded circuits are.
Instead, we may consider that any
is an SAC1 circuit by assumingthat$C_{\varphi,\alpha,\beta}$$\bullet$$\bullet$gates with fan-in more than two are OR gates, andgates with fan-in less than or equal to two are AND gates.

Note that negations are only applied to the input row for SACi circuits.
So we assume that inputs already contain the complement for each bit:
Input(X, )$n$$\Leftrightarrow|X|=\mathit{2}n+\mathit{2}$

A $(\forall x<n)(X[x]rightarrow\neg X[x+n])$ A $X[2n]$ A$\neg X[\mathit{2}n+1]$.

35This means that the actual input is given by the first bits and next bits
gives the bitwise complement of the input. For a technical reason, we add
which always evaluates to 1 andandtwo more bits at positions
respectively.
Now we give the formal definition of alternating paths on SAC1 circuits.
is a conjunction of the following
The formula
formulae:
$n$

$n$

$0$

$\mathit{2}n+1$$\mathit{2}n$$APATH_{\varphi}^{\alpha,\beta}(t, n,\overline{p},\overline{Q}, X, Z)$$\bullet$

No inputs with the value zero are in the path:($(\forall g<|\alpha(n)|\cdot\beta(n))$$\bullet$$\mathrm{r}\mathrm{o}\mathrm{w}_{\beta}(g)=0$

there exists at least one input with the value one in the path:$(\exists g<|\alpha(n)|\cdot\beta(n))$$\bullet$

A $\neg X[g]arrow\neg Z[g]$ ),($\mathrm{r}\mathrm{o}\mathrm{w}_{\beta}(g)=0$

A $X[g]$ A $Z[g]$ ),is an OR gate and either one of its offsprings is in the path thenso is :
if

$g$

$g$

$(\forall g<|\alpha(n)|\cdot\beta(n))$$(\exists h_{0}<|\alpha(n)|\cdot\beta(n))(\exists h_{1}<|\alpha(n)|\cdot\beta(n))(\exists h_{2}<|\alpha(n)|\cdot\beta(n))$($\varphi(h_{i},g, n,\overline{p},\overline{Q})\wedge h_{0}\neq h_{1}$A$h_{0}\neq h_{2}$A$h_{1}\neq h_{2}$,$(\exists h<|\alpha(n)|\cdot\beta(n))\varphi(h,g, n,\overline{p},\overline{Q})\wedge Z[h]rightarrow Z[g])$$\bullet$

if is an AND gate and both of its offsprings are in the path then so
is :
$g$

$g$

$(\forall g<|\alpha(n)|\cdot\beta(n))(\exists h_{0}<|\alpha(n)|\cdot\beta(n))(\exists h_{1}<|\alpha(n)|\cdot\beta(n))$$(\varphi(h0,g, n,\overline{p},\overline{Q})\wedge\varphi(h_{1},g, n,\overline{p},\overline{Q})\wedge$$(\forall h<|\alpha(n)|\cdot\beta(n))(\varphi(h,g, n,\overline{p},\overline{Q})arrow(h=h_{0}\vee h=h_{1}))$$\wedge Z[h_{0}]$$\bullet$A $Z[h_{1}]arrow Z[g])$ ,the gate is at the top of :
$Z$

$t$

$Z[t]\wedge(\forall g)(g\neq t\wedge Z[g]arrow(\exists h)\varphi(g, h, z,\overline{x},\overline{Y})\wedge Z[h])$So$APATH_{\varphi}^{\alpha,\beta}(t, n,\overline{p},\overline{Q}, X, Z)$$C_{\varphi,\alpha,\beta}$starting from the gate

Deflnition 10 Let Ax-Q SAC

$t$

.

.

says that there exists an alternating path in$(\varphi)$be the following axiom:$\mathrm{Q}^{SAC}[\varphi(g, h,\overline{x},\overline{\mathrm{Y}}), \alpha(z), \beta(z)](t, n,\overline{p},\overline{Q})rightarrow$($Circu\iota’t_{\varphi}^{\alpha,\beta}(n,\overline{p},\overline{Q})$A $Input^{\alpha,\beta}(X,$ $n)arrow(\exists Z)APATH_{\varphi}^{\alpha,\beta}(t,$$n,\overline{p},\overline{Q},$$X,$ $Z)$

).

36

.
is
Note that the righthand side of Ax-Q
Based on the above formulation, we will now define our system which
captures the class LOGCFL.
$\Sigma_{1}^{B}(\varphi)$$(\varphi)$

Definition 11 The system V-Q SAC
ioms are$(\Sigma_{0}^{B})$is the$QL_{2}(\Sigma_{0}^{b})$theory whose ax-$\bullet BASIC_{2f}$$\bullet Ax- \mathrm{Q}^{SAC}(\varphi)$$\bullet$$\mathrm{Q}^{SAC}(\Sigma_{0}^{B})$for$\varphi\in\Sigma_{0}^{B}$,-bit-comprehension:$(\exists P)(\forall k<c)(P[k]rightarrow$$Q^{SAC}[\varphi(g, h, z,\overline{x}, y,\overline{\mathrm{Y}}), \alpha(z), \beta(z)](|\alpha(n)|\cdot\beta(n)-1, n,\overline{p}, k,\overline{Q}, X))$.

Using the technique developed by Kolokolova [8], the author [9] showedthat

Theorem 5 (K) A function is in $F_{LOGCFL}$ if and only if it is.
in V-Q SAC$\Sigma_{1}^{B}$

definable$(\Sigma_{0}^{B})$5

Problems

It is an open problem whether a fragment of second order logic captures theclass LOGCFL in the sense of descriptive complexity. Since a second order, it is natural to conjecture that
captures the classexistential logic.
captur es complexity classes insidesubsets of
In fact, Gr\"adel [4] gave a second order existential logic which captures
if it is of the form
. A formula is said to be restrictedand$SO\exists$$\mathrm{N}\mathrm{P}$$SO\exists$$\mathrm{P}$$\mathrm{N}\mathrm{P}$$SO\exists$$\mathrm{N}\mathrm{L}$$(\exists P_{1})\cdots(\exists P_{k})(\forall\vec{y})\varphi(\tilde{P},\vec{y})$where$\varphi(\vec{P},\tilde{y})$

,

$(*)$

is quantifier free. Gr\"adel defined

Definition 12 A formula is $SO\exists- Hom$ if it is aformula such thatits quantifier free part is in conjunction nomal form where each conjunctcontains at most one negative literal.
-Krom if it is a
A formula isformula such that its quantifier
free part is in conjunction normal form where each conjunct contains at most
two literals.
$SO\exists$$SO\exists$$SO\exists$

37-Horn captures
Theorem 6 (Gr\"adel [4])$NL$ over arithmetical structures.
$SO\exists$

$P$

and

$SO\exists$-Krom captures

The proof uses the fact that the satisPability for Horn formulae andformulae are complete for and NL respectively.
Now, turning our attension back to the class LOGCFL, there is a possibility that the acyclic Boolean conjunctive queries can be used to give a classof restricted
formulae which captures the class LOGCFL. To this end,$(*)$
the formula inmust express the acyclic Boolean conjunctive queries.

$2\mathrm{C}\mathrm{N}\mathrm{F}$$\mathrm{P}$$SO\exists$$\varphi$

References[1] A.Borodin, S.A.Cook, P.W.Dymond, W.L.Ruzzo and M.Tompa, Twoapplications of inductive counting for complementation problems.
SIAM J.Comput., vol.18, No.3, pp.559-578 (1989)[2] Buss. S. R., Bounded Arithmetic. Ph.D thesis. (1985) Published in 1986
by Bibliopolis, Naples.
[3] Fagin, R., Generalized first-order spectra and polynomial-time recognizable sets. In Comlexity of Computation, R. Karp, ed., SIAM-AMS
Proceedings, 7 (1974), pp.43–73.

[4] Gr\"adel, E., Capturing complexity classes by fragments of second orderlogic. Theoretical Computer Science, 101 (1992), pp.35-57.

[5] Gottlob, G., N. Leone and F. Scarcello, The Complexity of Acyclic
Conjunctive Queries, Journal of ACM, vol.43, No.3, pp.431-498 (2001)[6] Immerman, N., Nondeterministic space is closed under complementation. SIAM Journal on Computing, 17 (1988), pp.935-938.
[7] Immerman, N., Descriptive Complexity. Guraduate Texts in Computer
Science, Springer (1999).
[8] A.Kolokolova, Systems of bounded arithmetic from descriptive complexity. Ph.D.Thesis, University of Toronto (2005)[9] Kuroda, S., A bounded arithmetic theory for LOGCFL, to appear inArchive for Mathematical Logic. (2007)[10] Szelepsc\’enyi, R., The method of forced enumeration for nondeterministic automata. Acta Informatica, 26 (1988) pp.279-284.

38[11] H.Venkateswaran, Properties that characterizes LOGCFL. J. Computerand System Sciences, 42, pp.380-404 (1991)[12] C.Lautemann, P.McKenzie, T.Schwentick and H.Vollmer, The Descriptive Complexity Approach to LOGCFL. J. Computer and System Sciences, 62(4), pp.629-652 (2001)