Experimental Descriptive Complexity
Marco Carmosino1? , Neil Immerman1? , and Charles Jordan2??
1

Computer Science Dept.
University of Massachusetts, Amherst
2
Division of Computer Science
Hokkaido University{mcarmosi,immerman}@cs.umass.edu, skip@ist.hokudai.ac.jp

Abstract. We describe our development and use of DescriptiveEnvironment (DE). This is a program to aid researchers in Finite Model Theory and students of logic to automatically generate examples, counterexamples of conjectures, reductions between problems, and visualizationsof structures and queries.
DescriptiveEnvironment is available for free use under an ISC licenseat http://www.cs.umass.edu/∼immerman/de . We encourage researchersand students at all levels to experiment with it. Please tell us of yourinsights, progress, suggestions, or extensions of DE.

Dedication
Dexter Kozen is a man of enormous energy. He plays soccer, rugby and ice
hockey; he volunteers at the Cayuga Heights Fire Department; he raises threeboys with Fran. In his spare time, Dexter proves theorems, teaches classes andwrites books.
How has he done it all? One aspect is that when Dexter is engaged on a
project, sleep is apparently unnecessary. Another is his plasticity: with an amazing ability to quickly master any relevant tool — whether it is a body of mathematics or a piece of software — that will add insight to what he is investigating,
Dexter can shape shift easily. Between his flexibility, grace (watch out for him
on the soccer field!) and his wide-ranging interests, Dexter has produced manyelegant results. His results are deep and his impact has been wide.
We doubt that he is really turning sixty (In the words of Garnet Rogers,“What’s Wrong With This Picture?” [Rog94]3 ), but we wish him happy birthday
all the same.

1

Introduction

When Neil Immerman was a graduate student at Cornell, he discovered Descriptive Complexity4 . His dream was that rather than writing complex, error-prone?

This research supported in part by NSF grants CCF 1115448; CCF 0830174.
Supported by a Grant-in-Aid for JSPS Fellows under Grant No. 2100195209.
3
Dexter has a rock band and it’s easy to imagine them performing this song.
4
Immerman originally called it “First Order Expressibility”; sometime later his advisor, Juris Hartmanis, suggested “Descriptive Complexity”.

??

programs, one could simply express the desired task in logic — leading to simple,
correct and flexible code. However, it turns out that it is not particularly easy
to write involved specifications in logic. Furthermore, just constructing examples and counter-examples of conjectures can be challenging. One tool to help
with this would be a program that would automatically construct the models described by logical formulas. This is the genesis of DescriptiveEnvironment(DE).
For many years, DE was simply a glimmer in Immerman’s eye. When Charles
Jordan was an undergraduate at the University of Massachusetts in the early
2000s, he built a prototype of DE as a senior project. During his early years asa graduate student in computer science at Hokkaido University, Jordan refined
DE. During a current visit to UMass Amherst, Jordan, along with graduate
student Marco Carmosino, have extended DE.
In this paper we will introduce DE and present its basic functionality. In particular we will discuss queries: the formalism for expressing properties, transforming structures, and building reductions between problems. We begin byintroducing some terminology from logic and Descriptive Complexity.

2

Descriptive Complexity: Mathematical Background

This background material is condensed from [Imm99]. The reader desiring moredetail should consult that book as well as [EF99,Lib04].
This paper is not meant to be an introduction or survey on Descriptive
Complexity. To satisfy the reader’s curiosity we will provide the following very
brief description of this subject. Beyond that, we point the reader to the following
short survey: [Imm95], or to the above three books to find out about the subject
in depth.
Descriptive Complexity began with Fagin’s Theorem which says that a property, e.g., a graph property, is in NP iff it is expressible in second-order existential
logic, i.e., NP = SO∃ [Fag74]. Since that time, essentially all important complexity classes have been characterized via standard logical languages.
Two fundamental translations from computational complexity to logic are
the following: (i) The parallel time needed to check whether an input structure
has a property is equal to the depth needed to describe that property in a
first-order inductive definition; and (ii) the amount of memory needed to check
whether an input structure has a property is characterized by the number ofdistinct variables needed to describe that property in first-order logic.
In general, the computational complexity of checking whether an input has agiven property can be exactly characterized as the richness of a logical language
needed to express that property.
Thus the secrets of computation can be understood with logic. For this reason, it is of great use to have tools such as DE to help us manipulate and reason
about the objects in question, i.e., structures and queries.
In the rest of this section we recall standard notation from mathematical
logic. A relational vocabulary, τ = hR1a1 , . . . , Rrar , c1 , . . . , cs i is a tuple of re-lation symbols of given arity and constant symbols. For example, the following
DE commands create the vocabularies “graph”, consisting of one binary relation
symbol, E, and two constant symbols, s, t; and “set” consisting of a single unary
relations symbol, S.
graph is new vocabulary{E:2, s, t}.
set is new vocabulary{S:1}.
A structure with vocabulary τ is a tuple,A=A
h|A|, R1A , . . . , RrA , cA
1 , . . . , cs i

whose universe is the nonempty set |A|. For each relation symbol Ri of arity
ai in τ , A has a relation RiA of arity ai defined on |A|, and for each constantsymbol, cj , cA
j is an element of |A|.
The following command creates line10, a structure of vocabulary graph thatis a line graph on 10 vertices:line10 is new structure{graph, 10, E:2 is x2=x1+1, s is 0, t is 9}.
In DE, the universe of a structure with size n+1 is {0, 1, . . . , n}. The definitionof E has two free variables, x1 and x2, and the above command defines the edge
relation in line10 to be {(x1 , x2 ) | 0 ≤ x1 , x2 ≤ 9, x2 = x1 + 1} (see Fig. 1). In
DE, the definition of a relation symbol of arity a assumes that the free variables
are {x1 , . . . , xa }.
The next instruction creates primes100, a structure of vocabulary set that is
the set of all primes less than 100:primes100 is new structure{set,100, S:1 is (1< x1 &\A x, y.(x<=x1 & y<=x) : ((x*y=x1)->(x=1|y=1)))}.
The symbols \A and \E denote ∀ and ∃, and so S(x1) holds when x1 is prime.
Of course we can ask DE to print a given relation as follows, or to draw agiven structure (Fig. 1).
primes100.S.
:{(2), (3), (5), (7), (11), (13), (17), (19), (23), (29), (31),(37), (41), (43), (47), (53), (59), (61), (67), (71), (73), (79),(83), (89), (97)}2.1

QueriesA query is any mapping I : STRUC[σ] → STRUC[τ ] from structures of one
vocabulary to structures of another vocabulary, that is polynomially bounded.
A boolean query is a map Ib : STRUC[σ] → {0, 1}. In Descriptive Complexity,
computations are queries and decision problems are boolean queries.

s

1

2

3

4

5

6

7

8

t

Fig. 1. The result of DE command: draw(line10).

Let σ and τ be any two vocabularies where τ = hR1a1 , . . . , Rrar , c1 , . . . , cs i. A
first-order query, I : STRUC[σ] → STRUC[τ ],I = hk, ϕ0 , ϕ1 , . . . , ϕr , ψ1 , . . . , ψs i
is an r + s + 2-tuple consisting of a positive natural number k called the dimension of the query, plus formulas from the first-order language of σ, defining theuniverse of the image structure together with the relations and constants definedon the image structure.
For each structure A ∈ STRUC[σ], these formulas describe a structure
I(A) ∈ STRUC[τ ],
I(A)

=

I(A)

h|I(A)|, R1

I(A), . . . , RrI(A) , c1

, . . . , csI(A) i .

The universe of I(A) is a first-order definable subset of |A|k .
 1|I(A)| =hb , . . . , bk i ∈ |A|k A |= ϕ0 (b1 , . . . , bk )(Usually we will take ϕ0 ≡ true, thus letting |I(A)| be the set of all k-tuples
from |A|.)
I(A)Each relation Ri
is a first-order definable subset of |I(A)|ai ,
 1
I(A)
Ri
=
(hb1 , . . . , bk1 i, . . . , hb1ai , . . . , bkai i) ∈ |I(A)|ai A |= ϕi (b11 , . . . , bkai ) .
I(A)Each constant symbol cj
I(A)

cj

=

is a first-order definable element of |I(A)|,the unique hb1 , . . . , bk i ∈ |I(A)| such that A |= ψj (b1 , . . . , bk ) .

For example, the following creates a binary first-order query I from graphs
to sets. The universe formula for I is true, denoted in DE as \t:
I is new query{graph,string,2,\t,S:1 is E(x1,x2)}.
Applying I to line10 results in a set of 100 potential elements, populated byexactly the 9 edges of line10:
set100 is I(line10).
set100.S.
:{(1), (12), (23), (34), (45), (56), (67), (78), (89)}Here is a slightly more interesting query:
R is new query{graph,graph,2,\t,E:2 is (x1=x3 & E(x2,x3))| (x1+1=x2 & x2=x3 &x3=x4), s is x1=0 & x2=0,
t is x1=max & x2=max}.
Here max denotes the maximum element of the universe. Let REACH be theset of graphs that have a path from s to t. Observe that for an undirected graph
G, R(G) is in REACH iff G is connected. Thus R is a first-order reduction fromconnectivity of undirected graphs to REACH.
In general, if S and T are finite sets of structures of vocabulary σ and τ ,respectively, and R is a first-order query from STRUC[σ] to STRUC[τ ], then R isa first-order reduction from S to T iff for all finite structures A ∈ STRUC[σ],A∈S⇔

R(A) ∈ T .

One of the reasons that complexity theory has been so successful in characterizing the complexity of problems is that naturally arising computational
problems tend to be complete for important complexity classes such as NP, P,
PSPACE, NSPACE[log n], DSPACE[log n], and a few others. This is true in spiteof the fact that a well-known theorem of Ladner says that for any two of theseclasses that are distinct, there are intermediate problems, i.e., in but not complete for the larger class, but not in the smaller class [Lad75]. Contrast this withthe fact that there are thousands of natural NP-complete problems, many dozensof P-complete problems, but only about four known natural problems that are
in NP but not known to be in P nor NP complete.
A related phenomenon is that all those natural complete problems, originallyshown complete via fairly powerful reductions, e.g., polynomial-time many-one
reductions, tend to remain complete under first-order reductions. Remarkably,
the extremely weak first-order projections (fop), quantifier-free reductions, andeven quantifier-free projections (qfp) also usually suffice [Imm99,Val82].
For example, consider the first-order reduction R above. It is a qfp. It isquantifier-free because the definitions of the new relations and constants – E, s,t – are quantifier free. It is a projection because each bit of the output structure
R(G) depends on at most one bit of the input structure G.
Relatively simple queries suffice to construct many of the objects of interest. Furthermore, it is possible to program via reductions, i.e., build a carefully
constructed and optimized program for a complete problem, C, and then solve
other problems by simply writing the reduction to C. An extremely successful
example of this point of view occurs when C = SAT: We already have generalautomatic problem solving via SAT solvers.
Here is another example of the potential value of being able to reason about
simple reductions. (See [Imm99] for details.) The problem REACH mentioned
above is complete via qfps for the complexity class NSPACE[log n] = NL. Let
REACHd be the subset of REACH containing graphs of out-degree at mostone. (See Fig. 1 for a simple example.) REACHd is complete via qfps forDSPACE[log n] = L. The following containments are well known and easy toprove:
L ⊆ NL ⊆ P ⊆ NP .
Everyone knows that is is open whether P = NP, but in fact it is open
whether L = NP. Since three-colorability of graphs (3-COLOR) is complete for
NP via logspace reductions (in fact, fops), it follows that 3-COLOR is reducible
to REACHd via qfps iff L= NP. In symbols,
3-COLOR ≤qfp REACHd⇔

L = NP

Thus reasoning about first-order and quantifier-free reductions is valuable forproving upper and lower bounds on complexity.

3

Order-Independent P: a Motivating Example for DE

In 1982 Immerman and Vardi independently characterized polynomial time as
the set of properties expressible in first-order logic plus the power to define new
relations by induction: P = FO(LFP) [Imm86,Var82].
But that was for ordered structures. When a graph or other logical structure is encoded in a computer, the vertices appear in some order. Furthermore,algorithms exploit this ordering by searching, for example, along the first edge
leaving a particular vertex. To even the playing field, the languages we use to describe computational properties, starting with FO, include some arbitrary totalordering relation on the universe. (This is handled in DE by having the universe of all structures of size n + 1 be {0, 1, . . . , n}, where ordering, addition andmultiplication on the integers is available.)
Graph properties are order-independent in the sense that they would notchange if we changed the order in which the vertices are stored in your computer.
However, since programs and formulas in FO(LFP) may use that arbitrary ordering, they may be computing a property of the ordered graph that depends
on that ordering and so is not a graph property at all.
It is of great interest to capture order-independent P with a logical language. Whether this is possible remains open. If one simply removes orderingfrom FO(LFP), the resulting language is too weak. It cannot even count whether
there are an even number of vertices in a graph. It was natural to ask whether
FO(LFP, COUNT) – first-order logic with fixed point and counting quantifiers,
but no ordering – captures order-independent P.
In 1981, Immerman and Eric Lander began investigating this question. It
suffices to check it on graphs. They showed that this result holds for all trees
and almost all graphs even when the formulas in question use only two variables[IL90].
If a graph is ordered, then each of its vertices has a unique name, i.e., thefirst vertex, the second vertex, etc. It is natural to consider graphs with unary
relations representing colorings of the vertices. The color-class size of a graphis the number of vertices of the most popular color, e.g., if a graph had two
green vertices, one blue vertex, three red vertices and two yellow vertices then it
would have color-class size 3. In some sense being ordered is the same as beingof color-class size one.
In the paper [IL90], Immerman and Lander also showed that on graphs ofcolor-class size at most 3, FO(LFP, COUNT) captures order-independent P, andthree variables are necessary and sufficient.
Five years later, Jin-yi Cai (another Cornellian) and Immerman were trying
to extend this result to larger color classes, in particular, trying to figure out
whether this result held for color-class size 4 graphs. It doesn’t; the CFI gadget
discovered by Cai and Immerman and independently Fürer [CFI92], is a basis
for the counterexample.
Fact 1 There is a linear-time computable property of graphs of color-class size 4that is not expressible in FO(LFP, COUNT). To express this property for graphs
on n vertices in FO(LFP, COUNT) requires Ω(n) distinct variables, while any
fixed formula in FO(LFP, COUNT) only has a bounded number of variables.
Although it remains open whether it is possible to capture order-independent
P, there has been great progress on this problem. An operator giving the rankof a matrix makes the CFI property expressible, so FO(LFP, rank) is a strict
extension of FO(LFP, COUNT) that is a new candidate for capturing orderindependent P [DGH09]. Furthermore, in a break-through result, Grohe has
shown that FO(LFP, COUNT) captures order-independent P for all classes ofgraphs having an excluded minor [Gro10].

4

Basic Functionality of DE

The CFI gadget took many blackboards, pieces of paper, and years to discover.
With DE, we could have found it back then in minutes; today it would only takeseconds. We have already seen a few DE commands. We now explain more ofwhat DE can do.
As we have seen, DE lets us easily define vocabularies, structures, and queries.
For example, let agraph be the vocabulary of graphs with two colors:
agraph is new vocabulary{A:1, E:2}.
In addition to defining structures explicitly as we did for line10 and set100
in §2, DE uses the tool Mace45 to generate a structure satisfying a given firstorder sentence. For example, the following command calls Mace4 to create anundirected bipartite graph whose vertices all have degree at least 2:
bip2 is mace(agraph, \A x: \E y1,y2.y1!=y2: (E(x,y1) & E(x,y2)) &\A x,y: (E(x,y)->(E(y,x) & (A(x)<->~A(y))))).
5

Available at http://www.cs.unm.edu/∼mccune/prover9/ .

The result is the smallest such graph: the complete bipartite graph K2,2 .
Built into DE are the boolean queries minisat() and zchaff() for calling
SAT solvers MiniSat6 and zChaff7 to check the satisfiability of a propositional
formula.
The vocabulary sat for propositional formulas is
sat is new vocabulary{P:2, N:2}.
Here P (c, xi ) means that variable xi occurs positively in clause c and N (c, xi )means that literal xi occurs in c. The default is that a clause that has no literals
is ignored.
DE makes it easy to use SAT solvers to solve a wide class of problems. For
example, consider the following 3-ary reduction from 3COLOR to SAT:
thrcoltosat is new query{graph, sat, 3, x1<=3,
P:2 is x1=3 & x2=0 & x3=x6 & x4=0 & x5<3,
N:2 is x4=0 & E(x2,x3) & (x1=x5 & (x6=x2 | x6=x3)) & x1<3}.
Here, boolean variable h0, c, xi means “vertex x is color c”, clause h3, 0, xi saysthat “vertex x is some color” and if E(x, y) then clause ha, x, yi (for 0 ≤ a ≤ 2)says that, “then x and y are not both color a”.
We can then use the SAT solver to check 3-colorability. For example, if wehave the DIMACS-format graph myciel3.col8 , we can use DE to check if it is
3-colorable:
myciel3 is load("myciel3.col").
mycielfmla is thrcolortosat(myciel3).
minisat(mycielfmla).
:\fHere mycielfmla is a boolean formula that is satisfiable iff the graph myciel3is 3-colorable. In this case, it is not satisfiable and thus we can conclude thatmyciel3 is not 3-colorable.
DE currently allows formulas from SO∃(TC)9 , i.e., in addition to first-orderlogic, second-order existential logic, a transitive closure operator, and arithmetic
are all available. Thus queries using TC and even second-order quantification
may be written and evaluated. In the following two boolean queries, reach isdefined using TC and isat is defined using second-order existential quantification. Not surprisingly, it is faster to use minisat and zchaff than to evaluate isat6

http://minisat.se
Available at http://www.princeton.edu/∼chaff/zchaff.html . Due to licensing
issues, users who wish to use zChaff must download it themselves.
8
Available from http://mat.gsia.cmu.edu/COLOR/instances.html.
9
Except when using Mace4, when we are restricted to first-order.

7

directly:
reach is new bquery{graph, TC[x,y:E(x,y)](s,t)}.
isat is new bquery{sat, \E S:1:\A z,x:\E y:(~P(z,x) & ~N(z,x)) |(P(z,y) & S(y)) |(N(z,y) & ~S(y))}.

5

A Motivating Example for ReductionFinder

Fact 2 [Imm88,Sze88] For all s(n) ≥ log n, NSPACE[s(n)] = co-NSPACE[s(n)].
When Immerman proved Fact 2, he was motivated by the fact that REACH
is complete for NSPACE[log n] via quantifier-free projections (qfp) [Imm99].
Thus he knew that NSPACE[log n] (NL) is closed under complementation iff
there is a qfp from REACH to REACH.
In fact, his original proof of Fact 2 was just that: a dimension 8 qfp from
REACH to REACH. The construction, somewhat analogous to the much simpler reduction R from §2.1, proceeds by stepping through distances d, from 1
to n, and target vertices t, from 0 to n − 1, computing the exact number nd ofvertices reachable from s in distance at most d, using the previously computed
constant, nd−1 .
Immerman was struck at the time by how constraining – and thus useful – it
was to have to build a qfp. It seemed either easy or impossible in the sense thatat most steps of building the reduction there was only one possible thing to do.
This feeling led many years later to the building of ReductionFinder, a program that repeatedly uses a SAT solver to search for a small quantifier-free
reduction between two problem specifications [CIE10]. At present writing, ReductionFinder is good at finding very small quantifier-free reductions – dimension 8 is way beyond the current capability. Still we feel that this approachhas enormous potential. We are currently making the interface between DE andReductionFinder.

6

Education

One of the differences between experts and students or novices is the experts’ability to visualize concepts relevant to their field. This ability aids in the construction and interpretation of diagrams, which allow communication between
experts and discovery of new results. Students do not gain as much knowledge
from examining domain-specific diagrams as experts do; they simply lack thecontext and skills to interpret diagrams.
In Descriptive Complexity, our diagrams are generally graphs depicting partsof logical structures before and after queries, or gadgets like the CFI construction.
There are many high-quality open-source tools for drawing and labeling graphs.
We have implemented a script that transforms the saved output of DE structures
into files for GraphViz10 .
10

http://www.graphviz.org/

To make the process as easy as possible, we have added a “draw” command toDE, so that users can make changes to defined structures and then immediately
observe their effect. This process mimics the visualization skills of the expert,
and will allow students to gain a deeper understanding of how structures aredefined by logical formulas.
In the future, we will extend “draw” to operate on queries, showing a beforeand-after view of the logical structure, and a typeset presentation of the relevant
logical formulas in one image. This will not only help students understand example queries through modifying and plotting them, it will help researchers examineand verify the results of more complex queries.
Ehrenfeucht-Fraı̈ssé games and their generalizations are a vital tool for Descriptive Complexity. It would be easier to teach students to play these games
if we had software to play them automatically. We will build an EF-game engine for DE, because it is convenient to do so: all of the relevant datatypes are
already available. Playing against an automated Samson or Delilah, each stepof the game will be drawn to the screen. We expect that students will develop
an intuition for EF-games and their generalizations faster and easier when acomputer implementation of the game with graphics is readily available.
In the longer term, DE can be used as the backend for a web-based system.
This would be the most convenient and easy format for students, and would
allow the use of a rich web UI for playing EF games and playing with example
queries and structures.

7

Conclusions

We have explained some of the motivations for building DE, together with someof its functionality. We encourage anyone to use it. Please send us your examples,
questions, suggestions, improvements, and extensions.
In the near future we anticipate adding more features and visualization tools.
In particular, we can hardly wait until DE is able to play Ehrenfeucht-Fraı̈ssé
games. It will also aid in visualizing a query by drawing the input and output
structures, and letting the user choose points in the input or output and having
the display highlight where they lead to or come from. We will add sliders to
help students and researchers visualize the computations of transitive closuresand fixed points.
There are many great programs and systems related to logic that are being
developed and used that we have omitted in this introduction to DE. Our plan
is to have an easy-to-use, extensible testbed. If there are great tools available,
such as SAT solvers, Mace, ReductionFinder, that we can call to make DE more
useful, then we are delighted to do so. The intent of DE is to make the researchand teaching of logical methods easier and more fun.

References[CFI92] J. Cai, M. Fürer, N. Immerman, “An Optimal Lower Bound on the Numberof Variables for Graph Identification,” Combinatorica 12 (4) (1992) 389-410.

[CIE10] Michael Crouch, Neil Immerman, and J. Eliot B. Moss, “Finding Reductions
Automatically”, Fields of Logic and Computation: Essays Dedicated to Yuri
Gurevich on the Occasion of His 70th Birthday, A. Blass, N. Dershowitz, and
W. Reisig, eds., (2010), Lecture Notes in Computer Science, volume 6300,
Springer-Verlag, 181 - 200.
[EF99] Heinz-Dieter Ebbinghaus and Jörg Flum, Finite Model Theory, Second Edition, 1999, Springer-Verlag.
[DGH09] Anuj Dawar, Martin Grohe, Bjarki Holm, and Bastian Laubner, “Logics with
Rank Operators,” IEEE Symp. Logic In Comput. Sci. (2009), 113-122.
[Fag74] Ron Fagin, “Generalized First-Order Spectra and Polynomial-Time Recognizable Sets,” in Complexity of Computation, (ed. R. Karp), SIAM-AMS
Proc. 7, 1974, 43-73.
[Gro10] Martin Grohe, “Fixed-Point Definability and Polynomial Time on Graphswith Excluded Minors,” IEEE Symp. Logic In Comput. Sci. (2010), 179-188.
[Imm99] Neil Immerman, Descriptive Complexity, 1999, Springer Graduate Texts in
Computer Science, New York.
[Imm95] N. Immerman, “Descriptive Complexity: A Logician’s Approach to Computation,” Notices of the American Mathematical Society 42(10) (1995), 1127
- 1133.
[Imm88] Neil Immerman, “Nondeterministic Space is Closed Under Complementation,” SIAM J. Comput. 17(5) (1988), 935-938.
[Imm87] Neil Immerman, “Languages That Capture Complexity Classes,” SIAM J.
Comput. 16(4) (1987), 760–778.
[Imm86] N. Immerman, “Relational Queries Computable in Polynomial Time,” Information and Control, 68 (1986), 86-104. A preliminary version of this paper
appeared in ACM Symp. Theory Of Comput. (1982), 147-152.
[IL90]
Neil Immerman and Eric S. Lander, “Describing Graphs: A First-Order Approach to Graph Canonization,” in Complexity Theory Retrospective, Alan
Selman, ed., Springer-Verlag (1990), 59-81.
[Lad75] Richard Ladner, “On the structure of polynomial time reducibility,” J. Assoc. Comput. Mach. 22(1) (1975), 155-171.
[Lib04] Leonid Libkin, Elements of Finite Model Theory, 2004, Springer.
[Rog94] Garnet
Rogers,“What’s
Wrong
With
This
Picture?”,http://www.garnetrogers.com/lyrics/
What’s%20Wrong%20With%20This%20Picture.txt[Sze88] Róbert Szelepcsényi, “The Method of Forced Enumeration for Nondeterministic Automata,” Acta Informatica 26 (1988), 279-284.
[Var82] Moshe Vardi, “Complexity of Relational Query Languages,” ACM Symp.
Theory Of Comput. (1982), 137-146.
[Val82] Leslie Valiant, “Reducibility By Algebraic Projections,” L’Enseignement
mathématique, T. XXVIII, 3–4 (1982), 253–268.