On the Theory of Structural Subtyping
Viktor Kuncak and Martin Rinard
Laboratory for Computer Science
Massachusetts Institute of Technology
Cambridge, MA 02139, USA
{vkuncak, rinard}@lcs.mit.edu

arXiv:cs/0408015v1 [cs.LO] 5 Aug 2004

MIT-LCS-TR-879, January 2003

Abstract

Contents

We show that the first-order theory of structural subtyping
of non-recursive types is decidable.
Let Σ be a language consisting of function symbols (representing type constructors) and C a decidable structure in
the relational language L containing a binary relation ≤. C
represents primitive types; ≤ represents a subtype ordering.
We introduce the notion of Σ-term-power of C, which generalizes the structure arising in structural subtyping. The
domain of the Σ-term-power of C is the set of Σ-terms over
the set of elements of C.
We show that the decidability of the first-order theory of
C implies the decidability of the first-order theory of the Σterm-power of C. This result implies the decidability of the
first-order theory of structural subtyping of non-recursive
types.
Our decision procedure is based on quantifier elimination
and makes use of quantifier elimination for term algebras
and Feferman-Vaught construction for products of decidable
structures.
We also explore connections between the theory of structural subtyping of recursive types and monadic second-order
theory of tree-like structures. In particular, we give an embedding of the monadic second-order theory of infinite binary tree into the first-order theory of structural subtyping
of recursive types.

1 Introduction

2

2 Preliminaries
2.1 Term Algebra . . . . . . . . . . . . . . . . . .
2.2 Terms as Trees . . . . . . . . . . . . . . . . .
2.3 First Order Structures with Partial Functions

2
3
3
3

.
.
.
.
.

.
.
.
.
.

25
26
27
27
28
29

Keywords: Structural Subtyping, Quantifier Elimination, Term Algebra, Decision Problem, Monadic SecondOrder Logic

6 Term-Powers of Decidable Theories
6.1 Product Theory of Terms of a Given Shape
6.2 A Logic for Term-Power Algebras . . . . . .
6.3 Some Properties of Term-Power Structure .
6.4 Quantifier Elimination . . . . . . . . . . . .
6.5 Handling Contravariant Constructors . . . .
6.6 A Note on Element Selection . . . . . . . .

.
.
.
.
.
.

31
31
32
32
37
43
44

. . .
. . .
. . .
. . .
. . .
Sets

44
45
46
47
47
47
48

3 Some Quantifier Elimination Procedures
3.1 Quantifier Elimination . . . . . . . . . . . .
3.2 Quantifier Elimination for Boolean Algebras
3.3 Feferman-Vaught Theorem . . . . . . . . . .
3.4 Term Algebras . . . . . . . . . . . . . . . .
3.4.1 Term Algebra in Selector Language .
3.4.2 Quantifier Elimination . . . . . . . .
4 The
4.1
4.2
4.3

7 Some Connections with MSOL
7.1 Structural Subtyping Recursive Types .
7.2 A Decidable Substructure . . . . . . . .
7.3 Embedding Terms into Terms . . . . . .
7.4 Subtyping Trees of Known Shape . . . .
7.5 Recursive Feature Trees . . . . . . . . .
7.6 Reversed Binary Tree with Prefix-Closed
8 Conclusion

1

6
6
7
8
11
11
12

Pair Constructor and Two Constants
16
Boolean Algebras on Equivalent Terms . . . . 16
A Multisorted Logic . . . . . . . . . . . . . . 17
Quantifier Elimination for Two Constants . . 18

5 A Finite Number of Constants
5.1 Extended Term-Power Structure . . . .
5.2 Structural Base Formulas . . . . . . . .
5.3 Conversion to Base Formulas . . . . . .
5.4 Conversion to Quantifier-Free Formulas
5.5 One-Relation-Symbol Variance . . . . .

∗
This research was supported in part by DARPA Contract F3361500-C-1692, NSF Grant CCR00-86154, NSF Grant CCR00-63513, and
the Singapore-MIT Alliance.
†
Draft of February 5, 2018, 11:28pm,
see http://www.mit.edu/~vkuncak/papers for later versions.

.
.
.
.
.
.

.
.
.
.
.

48

1

Introduction

[31, Chapter 23], [39, 30], with membership constraints [10]
and with queues [43], decidability of products [35, 14], [31,
Chapter 12], and algebraically closed fields [50],
The complexity of the decision problem for the first-order
theory of structural subtyping has a non-elementary lower
bound. This is a consequence of a general theorem about
pairing functions [15, Theorem 1.2, Page 163] and applies to
term algebras already, as observed in [39, 43].

Subtyping constraints are an important technique for checking and inferring program properties, used both in type systems and program analyses [34, 16, 13, 28, 23, 4, 3, 1, 2, 20,
41, 17, 54, 7, 8, 5, 42, 47, 19].
This paper presents a decision procedure for the firstorder theory of structural subtyping of non-recursive types.
This result solves (for the case of non-recursive types) a
problem left open in [48]. [48] provides the decidability result for structural subtyping of only unary type constructors,
whereas we solve the problem for any number of constructors
of any arity. Furthermore, we do not impose any constraints
on the subtyping relation ≤, it need not even be a partial order. The generality of our construction makes it potentially
of independent interest in logic and model theory.
We approach the problem of structural subtyping using
quantifier elimination and, to some extent, using monadic
second-order logic of tree-like structures. This paper makes
the contributions:

2

Preliminaries

In this section we review some notions used in the this paper.
If w is a word over some alphabet, we write |w| for the
length of w. We write w1 · w2 to denote the concatenation
of words w1 and w2 .
A node v in a directed graph is a sink if v has no outgoing
edges. A node v in a directed graph is a source if v has no
incoming edges.
We write E1 ≡ E2 to denote equality of syntactic entities
E1 and E2 .
We write x̄ to denote some sequence of variables
x1 , . . . , xn .
We assume that formulas are built from propositional
connectives ∧, ∨, ¬, the remaining connectives are defined
as shorthands. Connective ¬ binds the strongest, followed
by ∧ and ∨.
A literal L is an atomic formula A or a negation of an
atomic formula ¬A. We define complementation of a literal
by A = ¬A and ¬A = A.
A formula ψ is in prenex form if it is of the form

• we give a new presentation of Feferman-Vaught theorem for direct products using a multisorted logic (Section 3.3); for completeness we also include proof of
quantifier-elimination for boolean algebras of sets (Section 3.2);
• we give a new presentation of decidability of the firstorder theory of term algebras; the proof uses the language of both constructor and selector symbols (Section 3.4);
• as an introduction to main result, we show decidability
of structural subtyping with one covariant binary constructor and two constants (Section 4), this result does
not rely on Feferman-Vaught technique;

Q1 x1 . . . . Qn xn .φ
where Qi ∈ {∀, ∃} for 1 ≤ i ≤ n and φ is a quantifier free
formula. We call φ a matrix of ψ.
If φ is a formula then FV(φ) denotes the set of free variables in φ.
We write [x1 7→ a1 , . . . , xk 7→ ak ] for the substitution σ
such that σ(xi ) = ai for 1 ≤ i ≤ k.
If φ is a formula and t1 , . . . , tk terms, we write φ[x1 :=
t1 , . . . , xk := tk ] for the result of simultaneously substituting
free occurrences of variables xi with term ti , for 1 ≤ i ≤ k.
We write h(t) for the height of term t. h(a) = 0 if a is
a constant, h(x) = 0 if x is a variable. If f (t1 , . . . , tk ) is a
term then

• we present a new construction, term-power algebra for
creating tree-like theories based on existing theories
(Section 5);
• as a central result, we prove that if the base theory
is decidable, so is the theory of term-power with arbitrary variance of constructors; we give an effective
decision procedure for quantifier elimination in termpower structure; the procedure combines elements of
quantifier elimination in Feferman-Vaught theorem and
quantifier elimination in term algebras (Sections 5, 6).

h(f (t1 , . . . , tk )) = 1 + max(h(t1 ), . . . , h(tk ))

• we show the decidability of structural subtyping nonrecursive types as a direct consequence of the main result;

We assume that all function symbols are of finite arity. If
there are finitely many function symbols then for any nonnegative integer k there is only a finite number of terms t
such that h(t) ≤ k.
If φ(u) is a conjunction of literals, we say that φ′ results
from ∃u.φ(u) by dropping quantified variable u iff φ′ is the
result of eliminating from φ(u) all conjunctions containing
u. More generally, if ψ is a formula of form

• we give a simple embedding of monadic second-order
theory of infinite binary tree into the theory of structural subtyping of recursive types with two primitive
types (Section 7.1);
• we show that structural subtyping of recursive types
where terms range over constant shapes is decidable
(Section 7.4);

Q1 x1 . . . Qu . . . Qk xk . ψ0
then the result of dropping u from ψ is

In addition to showing the decidability of structural subtyping, our hope is to promote the important technique of
quantifier elimination, which forms the basis of our result.
Quantifier elimination [22, Section 2.7] is a fruitful technique that was used to show decidability and classification
of boolean algebras [46, 51] decidability of term algebras

Q1 x1 . . . Qk xk . ψ0′
where ψ0′ is the result of dropping u from ∃u.φ0 .
An equality is an atomic formula t1 = t2 where t1 and t2
are terms. A disequality is negation of an equality.
2

Let Cons(Σ) be the term algebra interpretation of signature Σ, defined as follows [22, Page 14]. For every f ∈ Σ with
ar(f ) = k define Jf K ∈ Cons(Σ), with Jf K : FT(Σ)k → FT(Σ)
by
Jf K(t1 , . . . , tk ) = f (t1 , . . . , tk )

We use the usual Tarskian semantics of formulas. Unless
otherwise stated φ |= ψ will denote that formula φ ⇒ ψ
is true in a fixed relational structure that is under current
consideration.
Occasionally we find it convenient to work with multisorted logic, where domain is union of disjoint sets called
sorts, and arity specifies the sorts of all operations. Constants are operations with zero arguments. Relations are
operations that return the result in a distinguished sort bool
interpreted over the boolean lattice {false, true} or over the
distributive lattice of three-valued logic {false, true, undef}
from Section 2.3).
A structure C of a given language L is a pair of domain
C and the interpretation function J KC . Hence, we name operations of the structure using symbols of the language and
the interpretation function. If C is clear from the context
we write simply J K for J KC .
In Section 3.3 and Section 6 we use logic with several
kinds of quantifiers. Our logic is first-order, but we give
higher-order types to quantifiers. For example, a quantifier

We will write f instead of Jf K when it causes no confusion.
2.2

We define trees representing terms as follows.
We use sequences of nonegative integers to denote paths
in the tree. Let Σ be a signature. A tree over Σ is a partial
function t from the set Nat∗ of paths to the set Σ of function
symbols such that:
1. if w ∈ Nat∗ , x ∈ Nat, and t(w · x) is defined, then t(w)
is defined as well;
2. if t(w) = f with ar(f ) = k, then
{i | t(w · i) is defined } = {1, . . . , k}

Q :: (A → B) → B

A finite tree is a tree with a finite domain.

denotes a quantifier that binds variables of A sort enclosed
within an expression of B sort and returns an expression of
B sort. If X and Y are sets then X → Y denotes the set of
all functions from A to B. When specifying the semantics
of the quantifier Q we specify a function

2.3

The semantics of an expression M of sort B takes an environment σ which is a function from variable names to elements
of A and produces an element of B, hence JM Kσ ∈ JBK. We
define the semantics of an expression Qx. M by:
JQx. M Kσ = JQKh
where h : JAK → JBK is the function
h(a) = JM K(σ[x := a])

σ[x := a](y) =

(

σ(y),

if y 6≡ x

a,

if y ≡ x

Specifying types for quantifiers allows to express more
Let σA be some arbitrary dummy global environment. If
F is a formula without global variables we write JF KσA to
denote the truth value of F ; clearly JF KσA does not depend
on σA and we denote it simply JF K when no ambiguity arises.
We use Hilbert’s epsilon as a notational convenience in
metatheory. If P (x) is a unary predicate, then εx.P (x) denotes an arbitrary element d such that P (d) holds, if such
element exists, or an arbitrary object otherwise.
2.1

First Order Structures with Partial Functions

We make use of partial functions in our quantifier elimination procedures. In this section we briefly describe the approach to partial functions we chose to use; other approaches
would work as well, see e.g. [24].
A language of partial functions Σ1 contains partial function symbols in addition to total function symbols and relation symbols. Consider a structure with the domain A interpreting a language with partial function symbols Σ1 . Given
some environment σ, we have JtKσ ∈ A ∪ {⊥} where ⊥ ∈
/A
is a special value denoting undefined results. We require the
interpretations of total and partial function symbols to be
strict in ⊥, i.e. f (a1 , . . . , ai , ⊥, ai+2 , . . . , ak ) = ⊥.
We interpret atomic formulas and their negations over
the three-valued domain {false, true, undef} using strong
Kleene’s three-valued logic [26, 24, 44]. We require that
JRK(a1 , . . . , ai , ⊥, ai+2 , . . . , ak ) = undef for every relational
symbol R. Logical connectives in Kleene’s strong threevalued logic are the strongest “regular” extension of the corresponding connectives on the two-valued domain [26]. The
regularity requirement means that the three-valued logic is
a sound approximation of two-valued logic in the following
sense. We may obtain the truth tables for three-valued logic
by considering the truth values false, true, undef as shorthands for sets {false}, {true}, {false, true} and defining each
logical operation ∗ by:

JQK : (JAK → JBK) → JBK

Here

Terms as Trees

s1 J∗K s2 = {b1 ◦ b2 | b1 ∈ s1 ∧ b2 ∈ s2 }
where ◦ denotes the corresponding operation in the twovalued logic. As in a call-by-value semantics of lambda calculus, variables in the environments (σ) do not range over
⊥. We interpret quantifiers as ranging over the domain A
or its subset if the logic is multisorted; the interpretation of
quantifiers are similarly the best regular approximations of
the corresponding two-valued interpretations.
These properties of Kleene’s three-valued logic have the
following important consequence. Suppose that we extend
the definition of all partial functions to make them total
functions on the domain A by assigning arbitrary values outside the original domain. Suppose that a formula φ evaluates

Term Algebra

We introduce the notion of term algebra [22, Page 14].
Let Nat be the set of natural numbers. Let the signature
Σ be a finite set of function symbols and constants and let
ar : Σ → Nat be a function specifying arity ar(f ) for every
function symbol or constant f ∈ Σ. Let FT(Σ) denote the
set of finite ground terms over signature Σ. We assume that
Σ contains at least one constant c ∈ Σ, ar(c) = 0, and at
least one function symbol f ∈ Σ, ar(f ) > 0. Therefore,
FT(Σ) is countably infinite.
3

to an element of b ∈ {false, true} in Kleene’s logic. Then φ
evaluates to the same truth-value b in the new logic of total
functions. This property of three-valued logic implies that
the algorithms that we use to transform formulas with partial functions will apply even for the logic that makes all
functions total by completing them with arbitrary elements
of A.
We say that a formula ψ is well-defined iff its truth value
is an element of {false, true}.


To enable the transformation of each well-defined formula into a disjunction of well-defined conjunctions of literals, we enrich the language of function and relation symbols
as follows. With each partial function symbol f ∈ Σ1 of
arity k = ar(f ) we associate a domain description Df =
hhx1 , . . . , xk i, φi specifying the domain of f . Here x1 , . . . , xk
are distinct variables and φ is an unnested conjunction of
literals such that FV(φ) ⊆ {x1 , . . . , xk }. We require every
interpretation of a first-order structure with partial function
symbols to satisfy the following property:

Example 1 Consider the domain of real numbers. The following formulas are not well-defined:
3 = 1/0

Jf K(a1 , . . . , ak ) 6= ⊥ ⇐⇒ JφK[x1 7→ a1 , . . . , xk 7→ ak ]

∀x. 1/x > 0 ∨ 1/x < 0 ∨ 1/x = 0

for all a1 , . . . , ak ∈ A. We henceforth assume that every
structure with partial functions is equipped with a domain
description Df for every partial function symbol f .
The Proposition 8 below gives an algorithm for transforming a given well-defined formula into a disjunction of
well-defined conjunctions. We first give some definitions and
lemmas.

The following formulas are well-defined:
∃x. 1/x = 3
∀x. 1/x 6= 3
x = 0 ∨ 1/x > 0

Definition 3 If ψ is a formula with free variables, a domain formula for ψ is a formula φ not containing partial
function symbols such that, for every valuation σ,


We say that a formula φ1 is equivalent to a formula φ2
and write φ1 ∼
= φ2 iff

JψKσ 6= undef ⇐⇒ JφKσ = true
From Definition 3 we obtain the following Lemma 4.

Jφ1 Kσ = Jφ2 Kσ

Lemma 4 Let ψ be a formula and φ a domain formula for
ψ. Then
ψ∼
= (ψ ∧ φ) ∨ (undef ∧ ¬φ)

for all valuations σ (including those for which Jφ1 Kσ =
undef).
Sections below perform equivalence-preserving transformations of formulas. This means that starting from a welldefined formula we obtain an equivalent well-defined formula.
When doing equivalence preserving transformations it is
useful to observe that ∧, ∨ still form a distributive lattice.
The partial order of this lattice is the chain false ≤ undef ≤
true. The element undef does not have a complement in
the lattice; unary operation ¬ does not denote the lattice
complement. However, the following laws still hold:

Proof. Let σ be arbitrary valuation. Let v = JψKσ. If
v ∈ {true, false} then JφKσ = true and
J(ψ ∧ φ) ∨ (undef ∧ ¬φ)Kσ =
(v ∧ true) ∨ (undef ∧ false) = v.
If v = undef then JφK = false, so
J(ψ ∧ φ) ∨ (undef ∧ ¬φ)Kσ =

¬(x ∧ y) ∼
= ¬x ∨ ¬y
∼ ¬x ∧ ¬y
¬(x ∨ y) =

(undef ∧ false) ∨ (undef ∧ true) = undef.

¬¬x ∼
=x

Observe that ψ ∧φ in Lemma 4 is a well-defined conjunction. We use this property to construct domain formulas
using partial function domain descriptions.
Let
Df = hhx1 , . . . , xk i, B1f ∧ . . . ∧ Blff i

The properties of ∧, ∨, ¬ are sufficient to transform any
quantifier-free formula into disjunction of conjunctions of literals using the well-known straightforward technique. However, this straightforward technique in some cases yields conjunctions that are not well-defined, even though the formula
as a whole is well-defined.

for each partial function symbol f ∈ Σ1 of arity k, where
B1f , . . . , Blff are unnested literals. If t1 , . . . , tk are terms,
we write Bif (t1 , . . . , tk ) for Bif [x1 := t1 , . . . , xk := tk ]. Let
subt(t) denote the set of all subterms of term t.
For any literal B(t1 , . . . , tn ) where B(t1 , . . . , tn ) ≡
R(t1 , . . . , tn ) or B(t1 , . . . , tn ) ≡ ¬R(t1 , . . . , tn ), define

Example 2 Transforming a negation of well-defined formula:
¬(x 6= 0 ∧ (y = 1/x ∨ z = x + 1))
may yield the following disjunction of conjunctions:

DomForm(B(t1 , . . . , tn )) =
V

x = 0 ∨ (y 6= 1/x ∧ z 6= x + 1)

f (s1 ,...,sk )∈∪1≤i≤n subt(ti )

where y 6= 1/x ∧ z 6= x + 1 is not a well-defined conjunction
for x = 0.

1≤j≤lf

4

Bjf (s1 , . . . , sk )

(1)

Lemma 5 Let B(t1 , . . . , tn ) be a literal containing partial
function symbols. Then DomForm(B(t1 , . . . , tn )) is a domain formula for B(t1 , . . . , tn ).

Proposition 8 Every well-defined quantifier-free formula
ψ can be transformed into an equivalent disjunction ψ ′ of
well-defined conjunctions of literals.

Proof.
Let σ be a valuation.
By strictness of interpretations of function and predicate symbols, JB(t1 , . . . , tn )Kσ 6= undef iff Jf (s1 , . . . , sk )Kσ 6=
⊥ for every subterm f (s1 , . . . , sk ) of every term ti , iff
JBjf (s1 , . . . , sk )Kσ = true for every 1 ≤ j ≤ lf and every
subterm f (s1 , . . . , sk ).

Proof. Using the standard procedure, convert ψ to disjunction of conjunctions
C1 ∨ . . . ∨ Cn
∧ Ci′

Let Ci = B
where B is a literal and let DomForm(B) =
F1 ∧ . . . ∧ Fm . Replace B ∧ Ci′ by
(B ∧ F1 ∧ . . . ∧ Fm ∧ Ci′ ) ∨
W
′
1≤i≤m (undef ∧ ¬Fi ∧ DomForm(Fi ) ∧ Ci )

Lemma 6 Let B be a literal and let
DomForm(B) = F1 ∧ . . . ∧ Fm .

By Lemma 6 and distributivity, the result is an equivalent
formula. Repeat this process for every literal in C1 ∨. . .∨Cn .
The result can be written in the form

Then
B∼
= (B ∧ F1 ∧ . . . ∧ Fm ) ∨
W
1≤i≤m (undef ∧ ¬Fi ∧ DomForm(Fi ))

(undef ∧ φ1 ) ∨ . . . ∨ (undef ∧ φp ) ∨ φp+1 ∨ . . . ∨ φp+q

where each φi for 1 ≤ i ≤ p + q is a well-defined conjunction.
Formula (2) is equivalent to

Proof.
If JBKσ 6= undef, then JFi Kσ = true for every
1 ≤ i ≤ m, and

(undef ∧ (φ1 ∨ . . . ∨ φp )) ∨ φp+1 ∨ . . . ∨ φp+q

Jundef ∧ ¬Fi ∧ DomForm(Fi )Kσ = false

(3)

and is equivalent to the well-defined formula ψ, so it is welldefined. Formulas φ1 ∨ . . . ∨ φp and φp+1 ∨ . . . ∨ φp+q are
also well-defined. By Lemma 7, we conclude that formula
(3) is equivalent to

so the right-hand side evaluates to JBKσ as well. Now
consider the case when JBKσ = undef. Then there exists
a term f (s1 , . . . , sk ) such that Jf (s1 , . . . , sk )Kσ = undef.
Because σ(x) 6= ⊥ for every variable x, there exists a
term f (s1 , . . . , sk ) such that Jf (s1 , . . . , sk )Kσ = undef and
Jsi Kσ 6= undef for 1 ≤ i ≤ k. Then there exists a formula Fp
of form Bjf (s1 , . . . , sk ) such that JBjf (s1 , . . . , sk )Kσ = false,
and
Jundef ∧ ¬Fp ∧ DomForm(Fp )Kσ = undef.

φp+1 ∨ . . . ∨ φp+q

(4)

Because (4) is a disjunction of well-defined formulas, (4) is
the desired result ψ ′ .
The following proposition presents transformation to
unnested form for the structures with equality and partial
function symbols, building on Proposition 8. For a similar
unnested form in the first-order logic containing only total
function symbols, see [22, Page 58].

Because
JB ∧ F1 ∧ . . . ∧ Fm Kσ = false,
and for every q,

Proposition 9 Every well-defined quantifier-free formula
ψ in a language with equality can be effectively transformed
into an equivalent formula ψ ′ where ψ ′ is a disjunction of
existentially quantified well-defined conjunctions of the following kinds of literals:

Jundef ∧ ¬Fq ∧ DomForm(Fq )Kσ ∈ {undef, false},
the right-hand side evaluates to undef.
Lemma 7 Let φ0 (ȳ) and φ1 (ȳ) be well-defined formulas
whose free variables are among ȳ and let

• R(x1 , . . . , xk ) where R is some relational symbol of arity k and x1 , . . . , xk are variables;

ψ(ȳ) ≡ (undef ∧ φ0 (ȳ)) ∨ φ1 (ȳ)

• ¬R(x1 , . . . , xk ) where R is some relational symbol of
arity k and x1 , . . . , xk are variables;

If ψ(ȳ) is well-defined for all values of variables ȳ, then

• x1 = x2 where x1 , x2 are variables;

ψ(ȳ) ∼
= φ1 (ȳ)

• x = f (x1 , . . . , xk ) where f is some partial or total function symbol of arity k and x, x1 , . . . , xk are variables;

Proof. Consider any valuation σ. Let

• x1 6= x2 where x1 and x2 are variables.

v = Jφ1 (ȳ)Kσ
and

(2)

Proof.
Transform the formula to disjunction of wellformed conjunctions of literals as in the proof of Proposition 8.
Then repeatedly perform the following transformation
on each well-defined conjunction φ. Let A(f (x1 , . . . , xk )) be
an atomic formula containing term f (x1 , . . . , xk ). Replace
φ ∧ A(f (x1 , . . . , xk )) with

′

v = Jψ(ȳ)Kσ
We need to show v = v ′ . Because φ(ȳ) and ψ(ȳ) are welldefined, v, v ′ ∈ {false, true}. We consider two cases.
Case 1. v = true. Then also v ′ = true.
Case 2. v = false. Then v ′ = undef ∧ φ0 (ȳ). Because
v ′ 6= undef, we conclude v ′ = false.

∃x0 . φ ∧ x0 = f (x1 , . . . , xk ) ∧ A(x0 )
5

Replace x 6= f (x1 , . . . , xk ) with

Proof. The following sequence of equivalences holds.
∀x. (undef ∧ φ0 (x, ȳ)) ∨ φ1 (x, ȳ) ∼
=

x0 = f (x1 , . . . , xk ) ∧ x0 6= x

¬∃x.¬(undef ∧ φ0 (x, ȳ)) ∨ φ1 (x, ȳ) ∼
=

Repeat this process until the resulting conjunction φ′ is in
unnested form. φ′ is clearly equivalent to the original conjunction φ when all partial functions are well-defined. When
some partial function is not well-defined, then both φ and φ′
evaluate to false, because by construction of φ in the proof
of Proposition 8, each conjunction contains conjuncts that
evaluate to false when some application of a function symbol
is not well-defined.

¬∃x. (undef ∨ ¬φ0 (x, ȳ)) ∧ ¬φ1 (x, ȳ) ∼
=
¬∃x. (undef ∧ ¬φ1 (x, ȳ)) ∨ (¬φ0 (x, ȳ) ∧ ¬φ1 (x, ȳ)) ∼
=
¬ ((undef ∧ ∃x.¬φ1 (x, ȳ)) ∨ (∃x. ¬φ0 (x, ȳ) ∧ ¬φ1 (x, ȳ))) ∼
=
∼
(undef ∨ ∀x.φ1 (x, ȳ)) ∨ (∀x. φ0 (x, ȳ) ∨ φ1 (x, ȳ)) =
(undef ∧ ∀x.φ0 (x, ȳ) ∨ φ1 (x, ȳ)) ∨ ∀x.φ1 (x, ȳ)

Let a left-strict conjunction in Kleene logic be denoted
by ∧′ and defined by
p ∧′ q = (p ∧ q) ∨ (p ∧ ¬p)

Proposition 13 Let φ0 (x̄, ȳ) and φ1 (x̄, ȳ) be well-defined
formulas whose free variables are among ȳ and let

The correctness of the transformation to unnested form
in Proposition 9 relies on the presence of conjuncts that ensure that the entire conjunction evaluates to false whenever
some term is undefined. The following Lemma 10 enables
transformation to unnested form in an arbitrary context, allowing the transformation to unnested form to be performed
independently from ensuring well-definedness of conjuncts.

ψ(ȳ) ≡ Q1 x1 . . . Qn xn . (undef ∧ φ0 (x̄, ȳ)) ∨ φ1 (x̄, ȳ)
where Q1 , . . . , Qn are quantifiers. If ψ(ȳ) is well-defined for
all values of variables ȳ, then
ψ(ȳ) ∼
= Q1 x1 . . . Qn xn . φ1 (x̄, ȳ)
Proof. Applying successively Lemmas 11 and 12 to quantifiers Qn , . . . , Q1 , we conclude

Lemma 10 Let φ(x) be a formula with free variable x and
let t be a term possibly containing partial function symbols.
Then
1.

φ(t) ∼
= (∃x. x = t ∧ φ(x)) ∨ (undef ∧ ∀x.¬φ(x)) ;

2.

φ(t) ∼
= ∃x. x = t ∧′ φ(x) ;

3.

φ(t) ∼
= (∃x. x = t ∧ φ(x)) ∨ (t 6= t) .

ψ(ȳ) ∼
= (undef ∧ φ2 (ȳ)) ∨ Q1 x1 . . . Qn xn . φ1 (x̄, ȳ)
for some formula φ2 (ȳ). Then by Lemma 7,
ψ(ȳ) ∼
= Q1 x1 . . . Qn xn . φ1 (x̄, ȳ).

Proof. Straightforward.
Proposition 13 below shows that a simplification similar
to one in Lemma 7 can be applied even within the scope
of quantifiers. To show Proposition 13 we first show two
lemmas.

3

Some Quantifier Elimination Procedures

∃x. (undef ∧ φ0 (x, ȳ)) ∨ φ1 (x, ȳ) ∼
=

As a preparation for the proof of the decidability of term
algebras of decidable theories, we present quantifier elimination procedures for some theories that are known to admit
quantifier elimination. We use the results and ideas from
this section to show the new results in Sections 4, 5, 6.

(undef ∧ ∃x.φ0 (x, ȳ)) ∨ ∃x.φ1 (x, ȳ)

3.1

Lemma 11 For all formulas φ0 (x, ȳ) and φ1 (x, ȳ),

Proof. By distributivity of quantifiers and propositional
connectives in Kleene logic we have:

Quantifier Elimination

Our technique for showing decidability of structural subtyping of recursive types is based on quantifier elimination.
This section gives some general remarks on quantifier elimination.
We follow [22] in describing quantifier elimination procedures. According to [22, Page 70, Lemma 2.7.4] it suffices
to eliminate ∃y from formulas of the form
^
ψi (x̄, y)
(5)
∃y.

∃x. (undef ∧ φ0 (x, ȳ)) ∨ φ1 (x, ȳ) ∼
=
(∃x.undef ∧ φ0 (x, ȳ)) ∨ ∃x.φ1 (x, ȳ) ∼
=
(undef ∧ ∃x.φ0 (x, ȳ)) ∨ ∃x.φ1 (x, ȳ)

0≤i<n

Lemma 12 For all formulas φ0 (x, ȳ) and φ1 (x, ȳ),

where x̄ is a tuple of variables and ψi (x̄, y) is a literal whose
all variables are among x̄, y. The reason why eliminating
formulas of the form (5) suffices is the following. Suppose
that the formula in prenex form and consider the innermost
quantifier of a formula. Let φ be the subformula containing
the quantifier and the subformula that is the scope of the
quantifier. If φ is of the form ∀x. φ0 we may replace φ
with ¬∃x.¬φ0 . Hence, we may assume that φ is of the form

∀x. (undef ∧ φ0 (x, ȳ)) ∨ φ1 (x, ȳ) ∼
=
(undef ∧ ∀x.φ0 (x, ȳ) ∨ φ1 (x, ȳ)) ∨ ∀x.φ1 (x, ȳ)

6

∃x. φ1 . We then transform φ1 into disjunctive normal form
and use the fact
∃x. (φ2 ∨ φ3 ) ⇐⇒ (∃x. φ2 ) ∨ (∃x. φ3 )

denoted by t has exactly k elements. These properties are
first-order definable as follows.
|t| ≥ 0

(6)

We conclude that elimination of quantifiers from formulas of
form (5) suffices to eliminate the innermost quantifier. By
repeatedly eliminating innermost quantifiers we can eliminate all quantifiers from a formula.
We may also assume that y occurs in every literal ψi ,
otherwise we would place the literal outside the existential
quantifier using the fact

for y not occurring in B.
To eliminate variables we often use the following identity
of a theory with equality:

|t| ≥ k+1 ≡

∃x. x ⊂ t ∧ |x| ≥ k

|t| = k

|t| ≥ k ∧ ¬|t| ≥ k+1

≡

|(t3 ∩ tc4 ) ∪ (t4 ∩ tc3 )| = 0
It is therefore sufficient to consider the first-order formulas
whose only atomic formulas are of the form |t| = 0. For
the purpose of quantifier elimination we will additionally
consider formulas that contain atomic formulas |t|=k for all
k ≥ 1, as well as |t|≥k for k ≥ 0.
Note that we can eliminate negative literals as follows:

(7)

Section 2.3 presents analogous identities for partial functions.
Quantifier elimination procedures we give imply the decidability of the underlying theories. In this paper the interpretations of function and relation symbols on some domain
A are effectively computable functions and relations on A.
Therefore, the truth-value of every formula without variables is computable. The quantifier elimination procedures
we present are all effective. To determine the truth value of
a closed formula φ it therefore suffices to apply the quantifier elimination procedure to φ, yielding a quantifier free
formula ψ, and then evaluate the truth value of ψ.
3.2

true

We call a language which contains terms |t| ≥ k and |t| = k
the language of boolean algebras with finite cardinality constraints. Because finite cardinality constraints are first-order
definable, the language with finite cardinality constraints is
equally expressive as the language of boolean algebras.
Every inequality t1 ⊆ t2 is equivalent to the equality
t1 ∩ t2 = t1 , and every equality t3 = t4 is equivalent to the
cardinality constraint

∃y. (A ∧ B) ⇐⇒ (∃y.A) ∧ B

∃x.x = t ∧ φ(x) ⇐⇒ φ(t)

≡

¬|t| = k

⇐⇒

|t| = 0 ∨ · · · ∨ |t| = k−1 ∨ |t| ≥ k+1

¬|t| ≥ k

⇐⇒

|t| = 0 ∨ · · · ∨ |t| = k−1

(8)
Every formula in the language of boolean algebras can therefore be written in prenex normal form where the matrix of
the formulas is a disjunction of conjunctions of atomic formulas of the form |t| = k and |t| ≥ k, with no negative
literals.
Note that if a term t contains at least one operation of
arity one or more, we may assume that the constants 0 and
1 do not appear in t, because 0 and 1 can be simplified away.
Furthermore, the expression |0| denotes the integer zero, so
all terms of form |0| = k or |0| ≥ k evaluate to true or false.
We can therefore simplify every nontrivial term t so that
it either t contains no occurrences of constants 0 and 1, or
t ≡ 1.
We next describe a quantifier elimination procedure for
finite boolean algebras.
We first transform the formula into prenex normal form
and then repeatedly eliminate the innermost quantifier. As
argued in Section 3.1, it suffices to show that we can eliminate an existential quantifier from any existentially quantified conjunction of literals. Consider therefore an arbitrary
existentially quantified conjunction of literals
^
ψi (x̄, y)
∃y.

Quantifier Elimination for Boolean Algebras

This section presents a quantifier elimination procedure for
finite boolean algebras. This result dates back at least to
[46], see also [51, 27, 32, 6, 49], [22, Section 2.7 Exercise 3].
Note that the operations union, intersection and complement are definable in the first-order language of the subset
relation. Therefore, quantifier elimination for the first-order
theory of the boolean algebra of sets is no harder than the
quantifier elimination for the first-order theory of the subset relation. However, the operations of boolean algebra are
useful in the process of quantifier elimination, so we give the
quantifier elimination procedure for the language containing
boolean algebra operations.
Instead of the first-order theory of the subtype relation
we could consider monadic second-order theory with no relation or function symbols. These two languages are equivalent because the first-order quantifiers can be eliminated
from monadic second-order theory using the subset relation
(see Section 7.1).
Finite boolean algebras are isomorphic to boolean algebras whose elements are all subsets of some finite set. We
therefore use the symbols for the set operations as the language of boolean algebras. t1 ∩t2 , t1 ∪t2 , tc1 , 0, 1, correspond
to set intersection, set union, set complement, empty set,
and full set, respectively. We write t1 ⊆ t2 for t1 ∩ t2 = t1 ,
we write t1 ⊂ t2 for the conjunction t1 ⊆ t2 ∧ t1 6= t2 .
For every nonnegative integer k we introduce formulas
|t| ≥ k expressing that the set denoted by t has at least
k elements, and formulas |t| = k expressing that the set

1≤i≤n

where ψi is of the form |t| = k or of the form |t| ≥ k. We
assume that y occurs in every formula ψi . It follows that no
ψi contains |0| or |1|.
Let x1 , . . . , xm , y be the set of variables occurring in formulas ψi for 1 ≤ i ≤ n.
First consider the more general case m ≥ 1. Let for
i1 , . . . , im ∈ {0, 1},
ti1 ...im = xi11 ∩ · · · ∩ ximm
where t0 = t and t1 = tc . The terms in the set
P = {ti1 ...im | i1 , . . . , im ∈ {0, 1}}
7

original formula
∃y. |s ∩ y| ≥ k ∧ |s ∩ y c | ≥ l

eliminated form
|s| ≥ k + l

∃y. |s ∩ y| = k ∧ |s ∩ y c | ≥ l

|s| ≥ k + l

c

∃y. |s ∩ y| ≥ k ∧ |s ∩ y | = l

|s| ≥ k + l

∃y. |s ∩ y| = k ∧ |s ∩ y c | = l

|s| = k + l

This completes the description of quantifier elimination
from an existentially quantified conjunction. By repeating
this process for all quantifiers we arrive at a quantifier-free
formula ψ. Hence we have the following theorem.
Theorem 14 For every first-order formula φ in the language of boolean algebras with finite cardinality constraints
there exists a quantifier-free formula ψ such that ψ is a disjunction of conjunctions of literals of form |t| ≥ k and |t| = k
where t are terms of boolean algebra, the free variables of ψ
are a subset of the free variables of φ, and ψ is equivalent to
φ on all algebras of finite sets.

Figure 1: Rules for Eliminating Quantifiers

Remark 15 Now consider the case when formula φ has no
free variables. By Theorem 14, φ is equivalent to ψ where ψ
contains only terms without variables. A term without variables in boolean algebra can always be simplified to 0 or 1.
Because |0| = 0, the literals with |0| reduce to true or false,
so we may simplify them away. The expression |1| evaluates
to the number of elements in the boolean algebra. We call
literals |1| = k and |1| ≥ k domain cardinality constraints. A
quantifier-free formula ψ can therefore be written as a propositional combination of domain cardinality constraints. We
can simplify ψ into a disjunction of conjunctions of domain
cardinality constraints and transform each conjunction so
that it contains at most one literal. The result ψ ′ is a single disjunction of domain cardinality constraints. We may
further assume that the disjunct of form |1| ≥ k occurs at
most once. Therefore, the truth value of each closed boolean
algebra formula is characterized by a set C of possible cardinalities of the domain. If ψ ′ does not contain any |1| ≥ k literals, the set C is finite. Otherwise, C = C0 ∪ {k, k + 1, . . .}
for some k where C0 is a finite subset of {1, . . . , k − 1}.

form a partition; moreover every boolean algebra expression
whose variables are among xi can be written as a disjoint
union of some elements of the partition P . Any boolean
algebra expression containing y can be written, for some
p, q ≥ 0 as
(s1 ∩ y) ∪ · · · ∪ (sp ∩ y)∪
(t1 ∩ y c ) ∪ · · · ∪ (tq ∩ y c )
where s1 , . . . , sp ∈ P are pairwise distinct elements from the
partition and t1 , . . . , tq ∈ P are pairwise distinct elements
from the partition. Because
|(s1 ∩ y) ∪ · · · ∪ (sp ∩ y) ∪ (t1 ∩ y c ) ∪ · · · ∪ (tq ∩ y c )| =
|s1 ∩ y| + · · · + |sp ∩ y| + |t1 ∩ y c | + · · · + |tq ∩ y c |
the constraint of form |t| = k can be written as
_
|s1 ∩ y| = k1 ∧ · · · ∧ |sp ∩ y| = kp ∧
k1 ,...,kp ,l1 ,...,lq

|t1 ∩ y c | = l1 ∧ · · · ∧ |tq ∩ y c | = lp

where the disjunction ranges over nonnegative integers
k1 , . . . , kp , l1 , . . . , lq ≥ 0 that satisfy

3.3

Feferman-Vaught Theorem
The Feferman-Vaught technique is a way of
discovering the first-order theories of complex structures by analyzing their components.
This description is a little vague, and in
fact the Feferman-Vaught technique itself has
something of a floating identity.
It works
for direct products, as we shall see.
Clever
people can make it work in other situations too.
— [22], page 458

k1 + · · · + kp + l 1 + · · · + l q = k
From (8) it follows that we can perform a similar transformation for constraints of form |t| ≥ k. After performing this
transformation, we bring the formula into disjunctive normal form and continue eliminating the existential quantifier
separately for each disjunct, as argued in Section 3.1. We
may therefore assume that all conjuncts ψi are of one of the
forms: |s ∩ y| = k, |s ∩ y c | = k, |s ∩ y| ≥ k, and |s ∩ y c | ≥ k
where s ∈ P .
If there are two conjuncts both of which contain |s∩y| for
the same s, then either they are contradictory or one implies
the other. We therefore assume that for any s ∈ P , there is
at most one conjunct ψi containing |s ∩ y|. For analogous
reasons we assume that for every s ∈ P there is at most one
conjunct ψi containing |s ∩ y c |. The result of eliminating
the variable y is then given in Figure 1. The case when a
literal containing |s ∩ y| does not occur is covered by the
case |s ∩ y| ≥ k for k = 0, similarly for a literal containing
|s ∩ y c |.
It remains to consider the case m = 0. Then y is the
only variable occurring in conjuncts ψi . Every cardinality
expression t containing only y reduces to one of |y| or |y c |.
If there are multiple literals containing |y|, they are either
contradictory or one implies the others. We may therefore
assume there is at most one literal containing |y| and at
most one literal containing |y c |. We eliminate quantifier by
applying rules in Figure 1 putting formally s = 1 where 1 is
the universal set.

We next review Feferman-Vaught theorem for direct
products [14] which implies that the products of structures
with decidable first-order theories have decidable first-order
theories.
The result was first obtained for strong and weak powers of theories in [35]; [35] also suggests the generalization
to products. Our sketch here mostly follows [14] and [35],
see also [31, Chapter 12] as well as [22, Section 9.6]. Somewhat specific to our presentation is the fact that we use a
multisorted logic and build into the language the correspondence between formulas interpreted over C and the cylindric
algebra of sets of positions.
Let LC be a relational language. Let further I be some
nonempty finite or countably infinite index set. For each
i ∈ I let Ci = hCi , J KCi i be a decidable structure interpreting
the language LC .
We define direct product of the family of structures Ci ,
i ∈ I, as the structure
P = Πi∈I Ci
8

where P = hP, J KP i. P is the set of all functions t such that
t(i) ∈ Ci for i ∈ I, and J KP is defined by
JrKP (t1 , . . . , tk ) = ∀i. JrKCi (t1 (i), . . . , tk (i))
for each relation symbol r ∈ LC .
inner formula relations for r ∈ LC
r

::

tuplek → indset

inner logical connectives
∧I , ∨I

::

indset × indset → indset

I

¬

::

indset → indset

trueI , falseI

::

indset

inner formula relations for r ∈ LC
JrKP2 (t1 , . . . , tk )

inner formula quantifiers
I

∃ ,∀

I

::

inner logical connectives

(tuple → indset) → indset

=

::

I P2

(A1 , A2 )

= A1 ∧ A2

I P2

(A1 , A2 )

= A1 ∪ A2

J∧ K

index set equality
I

J∨ K

indset × indset → bool

I P2

J¬ K

logical connectives
∧, ∨

::

bool × bool → bool

¬

::

bool → bool

true, false

::

bool

::

= I

JfalseI KP2

= ∅

inner formula quantifiers
S
J∃I KP2 f =
t∈P f (t)
T
I P2
J∀ K f =
t∈P f (t)

(indset → bool) → bool

index set equality

tuple quantifiers
∃, ∀ ::

(A) = I \ A

JtrueI KP2

index set quantifiers
∃L , ∀L

= { i | JrKCi (t1 (i), . . . , tk (i)) }

I P2

J= K

(A1 , A2 )

(tuple → bool) → bool

= (A1 = A2 )

logical connectives
(interpreted as usual)

Figure 2: Operations in product structure

index set quantifiers
S
J∃ K f =
A∈2I f (A)
T
L P2
J∀ K f =
A∈2I f (A)
L P2

For the purpose of quantifier elimination we consider a
richer language of statements about product structure P.
Figure 2 shows this richer language. The corresponding
structure P2 = hP2 , J KP2 i contains, in addition to the function space P , a copy of the boolean algebra 2I of subsets of
the index set I. We interpret a relation r ∈ LC by

tuple quantifiers

JrKP2 (t1 , . . . , tk ) = { i | JrKCi (t1 (i), . . . , tk (i)) }

J∃K

P2

f

= ∃t ∈ P. f (t)

J∀K

P2

f

= ∀t ∈ P. f (t)

We let JtrueI KP2 = I and write
Figure 3: Semantics of operations in product structure P2

r(t1 , . . . , tk ) =I trueI
to express JrKP (t1 , . . . , tk ). Hence P2 is at least as expressive
as P.
Note that Figure 2 does not contain an equality relation
between tuples. If we need to express the equality between
tuples, we assume that some binary relation r0 ∈ LC in the
base structure is interpreted as equality, and express the
equality between tuples t1 and t2 using the formula:
r0 (t1 , t2 ) =I trueI .
Figure 3 shows the semantics of the language in Figure 2.
(The logic has no partial functions, so we interpret the sort
bool over the set {true, false}.)
9

We let A1 ⊆I A2 stand for A1 ∧I A2 =I A2 .
Note that the interpretations of ∧I , ∨I , ¬I , trueI , falseI ,
=I , ∃L , ∀L form a first-order structure of boolean algebras of
subsets of the set I. We call formulas in this boolean algebra
sublanguage index-set algebra formulas.
On the other hand, relations r for r ∈ LC , together with
∧I , ∨I , ¬I , ∃I , ∀I form the signature of first-order logic with
relation symbols. We call formulas built only from these
operations inner formulas.
Let φ be a an inner formula with free tuple variables
t1 , . . . , tm and no free indset variables. Then φ specifies a
relation ρ ⊆ Dm . Consider the corresponding first-order
formula φ′ interpreted in the base structure C; formula φ′
specifies a relation ρ′ ⊆ C m . The following property follows
from the semantics in Figure 3:
ρ(t1 , . . . , tm ) = { i ∈ I | ρ′ (t1 (i), . . . , tm (i)) }

where partition(B1 , . . . , Bn ) denotes a boolean algebra expression expressing that sets B1 , . . . , Bn form the partition
of trueI .
It is easy to see that 11 and 12 are equivalent.
By repeating this construction we eliminate all term
quantifiers from a formula. We then eliminate all set quantifiers as in Section 3.2. For that purpose we extend the
language with cardinality constraints.
As the result we obtain cardinality constraints on inner
formulas. Closed inner formulas evaluate to trueI or falseI
depending on their truth value in base structure C. Hence,
if C is decidable, so is P2 .
Theorem 16 (Feferman-Vaught) Let C be a decidable
structure. Then every formula in the language of Figure 2 is
equivalent on the structure P2 to a propositional combination
of cardinality constraints of the index-set boolean algebra i.e.
formulas of form |φ| ≥ k and |φ| = k where φ is an inner
formula.

(9)

Sort constraints imply that quantifiers ∃I , ∀I are only applied
to inner formulas. Let φ be a formula of sort bool. By labelling subformulas of sort indset with variables A1 , . . . , An ,
we can write φ in form φ1 :

Example 17 Let r ∈ LC be a binary relation on structure
C. Let us eliminate quantifier ∃t from the formula φ(t1 , t2 ):
∃t.∃L A1 , A2 , A3 .

∃L A1 , . . . , An .
A 1 =I φ1 ∧ . . . ∧ A n =I φn ∧

A1 =I r(t, t1 ) ∧ A2 =I r(t1 , t) ∧ A3 =I r(t2 , t) ∧

ψ(A1 , . . . , An )

|¬I A1 | = 0 ∧ |¬I A2 | = 0 ∧ |¬I A3 | ≥ 1

where

We first introduce sets B0 , . . . , B7 that form partition of
trueI . The formula is then equivalent to φ1 :

φ = ψ(φ1 , . . . , φn )
Furthermore, by defining B1 , . . . , Bm to be the partition of
trueI consisting of terms of form

∃t.∃L B0 , B1 , B2 , B3 , B4 , B5 , B6 , B7 .
B0 =I r(t, t1 ) ∧I r(t1 , t) ∧I r(t2 , t) ∧

Ap11 ∧I . . . ∧I Apnn

B1 =I ¬I r(t, t1 ) ∧I r(t1 , t) ∧I r(t2 , t) ∧

′

for p1 , . . . , pn ∈ {0, 1}, we can find a formula ψ and formulas
φ′1 , . . . , φ′m such that φ1 is equivalent to φ2 :

B2 =I r(t, t1 ) ∧I ¬I r(t1 , t) ∧I r(t2 , t) ∧
B3 =I ¬I r(t, t1 ) ∧I ¬I r(t1 , t) ∧I r(t2 , t) ∧

∃L B1 , . . . , Bm .
B1 =I φ′1 ∧ . . . ∧ Bm =I φ′m ∧

B4 =I r(t, t1 ) ∧I r(t1 , t) ∧I ¬I r(t2 , t) ∧

(10)

B5 =I ¬I r(t, t1 ) ∧I r(t1 , t) ∧I ¬I r(t2 , t) ∧

ψ ′ (B1 , . . . , Bn )

B6 =I r(t, t1 ) ∧I ¬I r(t1 , t) ∧I ¬I r(t2 , t) ∧

φ′1 , . . . , φ′m

evaluate to sets that form partition of
and where
trueI for all values of free variables. (By partition of trueI we
here mean a family of pairwise disjoint sets whose union is
trueI , but we do not require the sets to be non-empty.)
Now consider a formula of form ∃t.φ where φ is without ∃, ∀ quantifiers (but possibly contains ∃I , ∀I and ∃L , ∀L
quantifiers). We transform φ into φ2 as described, and then
replace
∃t. ∃L B1 , . . . , Bm .
B1 =

I

φ′1

∧ . . . ∧ Bm =

I

φ′m

∧

B7 =I ¬I r(t, t1 ) ∧I ¬I r(t1 , t) ∧I ¬I r(t2 , t) ∧
φ0
where

φ0 ≡
|B1 | = 0 ∧ |B2 | = 0 ∧
|B3 | = 0 ∧ |B5 | = 0 ∧

(11)

|B6 | = 0 ∧ |B7 | = 0 ∧

′

ψ (B1 , . . . , Bn )

|B4 | ≥ 1

with

We now eliminate the quantifier ∃t from the formula φ1 ,
L

L

∃ D1 , . . . , Dm . ∃ B1 , . . . , Bm .
D1 =I (∃I t.φ′1 ) ∧ . . . ∧ Dm =I (∃I t.φ′m ) ∧
B1 ⊆I D1 ∧ . . . ∧ Bm ⊆I Dm ∧

(12)

partition(B1 , . . . , Bn ) ∧ ψ ′ (B1 , . . . , Bn )

10

B0 ⊆I D0 ∧ . . . ∧ B7 ⊆I D7 ∧

problems are special cases of decision problem for first-order
theory of term algebras, for a survey see e.g. [45, 9].
We believe that our proof provides some insight into
different variations of quantifier elimination procedures for
term algebras. Like [22] we use selector language symbols,
but retain the usual constructor symbols as well. The advantage of the selector language is that ∃y. z = f (x, y) is
equivalent to a quantifier-free formula x = f1 (z) ∧ Isf (z).
On the other hand, constructor symbols also increase the
set of relations on terms definable via quantifier-free formulas, which can slightly simplify quantifier-elimination procedure, as will be seen by comparing Proposition 34 and
Proposition 38. Compared to [22, Page 70], we find that the
termination of our procedure is more evident and the extension to the term-power algebra in Section 6 easier. Our
base formulas somewhat resemble formulas arising in other
quantifier elimination procedures [31, 11, 30]. Our terminology also borrows from congruence closure graphs like those
of [39, 38], although we are not primarily concerned with
efficiency of the algorithm described. Term algebra is an example of a theory of pairing functions, and [15] shows that
non-empty family of theories of pairing functions as nonelementary lower bound on time complexity.

φ0

3.4.1

obtaining formula φ2 :
∃L D0 , D1 , D2 , D3 , D4 , D5 , D6 , D7 .
D0 =I ∃I t. r(t, t1 ) ∧I r(t1 , t) ∧I r(t2 , t) ∧
D1 =I ∃I t. ¬I r(t, t1 ) ∧I r(t1 , t) ∧I r(t2 , t) ∧
D2 =I ∃I t. r(t, t1 ) ∧I ¬I r(t1 , t) ∧I r(t2 , t) ∧
D3 =I ∃I t. ¬I r(t, t1 ) ∧I ¬I r(t1 , t) ∧I r(t2 , t) ∧
D4 =I ∃I t. r(t, t1 ) ∧I r(t1 , t) ∧I ¬I r(t2 , t) ∧
D5 =I ∃I t. ¬I r(t, t1 ) ∧I r(t1 , t) ∧I ¬I r(t2 , t) ∧
D6 =I ∃I t. r(t, t1 ) ∧I ¬I r(t1 , t) ∧I ¬I r(t2 , t) ∧
D7 =I ∃I t. ¬I r(t, t1 ) ∧I ¬I r(t1 , t) ∧I ¬I r(t2 , t) ∧
φ3
where
φ3 ≡

∃L B0 , B1 , B2 , B3 , B4 , B5 , B6 , B7 .

To facilitate quantifier elimination we use a selector language Sel(Σ) for term algebra [22, Page 61]. We define term
algebra in selector language as a first-order structure with
partial functions.
The set Sel(Σ) contains, for every function symbol f ∈
Σ of arity ar(f ) = k, a unary predicate Isf ⊆ FT(Σ) and
functions f1 , . . . , fk : FT(Σ) → FT(Σ) such that

We next apply quantifier elimination for boolean algebras
to formula φ3 and obtain formula φ′3 :
φ′3 ≡ |D4 | ≥ 1 ∧ |¬I D0 ∧I ¬I D4 | = 0
Hence φ(t1 , t2 ) is equivalent to
∃L D0 , D4 .

Isf (t)
fi (f (t1 , . . . , tk ))
fi (t)

D0 =I ∃I t. r(t, t1 ) ∧I r(t1 , t) ∧I r(t2 , t) ∧
D4 =I ∃I t. r(t, t1 ) ∧I r(t1 , t) ∧I ¬I r(t2 , t) ∧
|D4 | ≥ 1 ∧ |¬I D0 ∧I ¬I D4 | = 0

⇐⇒
=
=

∃t1 , . . . , tk . t = f (t1 , . . . , tk ()13)
ti ,
1≤i≤k
(14)
⊥,
¬Isf (t)
(15)

For every f ∈ Σ and 1 ≤ i ≤ ar(f ), expression fi (t) defined
iff Isf (t) holds, so we let Df = hx, Isf (x)i.
As a special case, if d is a constant, then ar(d) = 0 and
Isd (t) ⇐⇒ t = d.

After substituting the definitions of D0 and D4 , formula
φ(t1 , t2 ) can be written without quantifiers ∃, ∀, ∃L , ∀L .

Proposition 18 For every formula φ1 in the language
Cons(Σ) there exists an equivalent formula φ2 in the selector
language.



3.4

Term Algebra in Selector Language

Term Algebras

Proof Sketch. Because of the presence of equality symbol, every formula in language Cons(Σ) can be written in
unnested form such that every atomic formula is of two
forms: x1 = x2 , or f (x1 , . . . , xk ) = y, where y and xi are
variables. We keep every formula x1 = x2 unchanged and
transform each formula

In this section we present a quantifier elimination procedure
for term algebras (see Section 2.1). A quantifier elimination
procedure for term algebras implies that the first-order theory of term algebras is decidable. In the sections below we
build on the procedure in this section to define quantifier
elimination procedures for structural subtyping.
The decidability of the first-order theory of term algebras follows from Mal’cev’s work on locally free algebras
[31, Chapter 23]. [39] also gives an argument for decidability of term algebra and presents a unification algorithm
based on congruence closure [38]. Infinite trees are studied
in [12]. [30] presents a complete axiomatization for algebra
of finite, infinite and rational trees. A proof in the style of
[22] for an extension of free algebra with queues is presented
in [43]. Decidability of an extension of term algebras with
membership tests is presented in [10] in the form of a terminating term rewriting system. Unification and disunification

f (x1 , . . . , xk ) = y
into the well-defined conjunction
x1 = f1 (y) ∧ · · · ∧ xk = fk (y) ∧ Isf (y)

Note that predicates Isf form a partition of the set of all
terms i.e. the following formulas are valid:
W
Isf (x)
∀x.
f ∈Σ
(16)
∀x. ¬(Isf (x) ∧ Isg (x)),
for f 6≡ g
11

¬, ∧, ∨

for some function j : {1, . . . , m} → {1, . . . , n}.
We require each semi-base formula to satisfy the following congruence closure property: there are no two distinct
variables ui and ui′ such that both ui = f (ul1 , . . . , ulk )
and ui′ = f (ul1 , . . . , ulk ) occur as conjuncts φj in formula
structure.
We denote by U the set of internal variables of a given
semi-base formula, U = {u1 , . . . , un }.

∃
Proposition 28

✲

quantifier-free
formula

✲
✛

disjunction of
base formulas

✛

Proposition 34

Definition 20 A semi-base formula in selector language is
obtained from the base formula in constructor language by
replacing every conjunct of form

Figure 4: Quantifier Elimination for Term Algebra

ui = f (ul1 , . . . , ulk )
A constructor-selector language contains both constructor symbols f ∈ Cons(Σ) and selector symbols fi ∈ Sel(Σ).

with the well-defined conjunction
Isf (ui ) ∧ ul1 = f1 (ui ) ∧ · · · ∧ ulk = fk (ui )

3.4.2

Quantifier Elimination

A semi-base formula in selector language is clearly a wellformed conjunction of literals. All atomic formulas in a semibase formula are unnested, in both constructor and selector
language.
We can represent a base formula as a labelled directed
graph with the set of nodes U ; we call this graph graph associated with a semi-base formula. Nodes of the graph are
in a bijection with internal variables of the semi-base formula. We call nodes corresponding to parameter variables
up+1 , . . . , up+q parameter nodes; nodes u1 , . . . , up are nonparameter nodes. Each non-parameter node is labelled by
a function symbol f ∈ Σ and has exactly ar(f ) successors,
with edge from uk to ul labelled by the positive integer i
iff fi (uk ) = ul occurs in the semi-base formula written in
selector language. A constant node is a node labelled by
some constant symbol c ∈ Σ, ar(c) = 0. A constant node
is a sink in the graph; every sink is either a constant or a
parameter node. In addition to the labelling by function
symbols, each node u ∈ U of the graph is labelled by zero
or more free variables x such that equation x = u occurs in
the semi-base formula.

We proceed to quantifier elimination for term algebra. A
schematic view of our proof is in Figure 4. The basic insight is that any quantifier-free formula can be written in a
particular unnested form, as a disjunction of base formulas.
Base formulas trivially permit elimination of an existential
quantifier, yet every base formula can be converted back to
a quantifier-free formula.
A semi-base formula is almost the base formula, except
that it may be cyclic. We introduce cyclicity after explaining
the graph representation of a semi-base formula.
Definition 19 (Semi-Base Formula) A semi-base formula β with
• free variables x1 , . . . , xm ,
• internal non-parameter variables u1 , . . . , up , and
• internal parameter variables up+1 , . . . , up+q
is a formula of form
∃u1 , . . . , un

Definition 21 (Base Formula) A semi-base formula φ is
a base formula iff the graph associated with φ is acyclic.

distinct(u1 , . . . , un ) ∧
structure(u1 , . . . , un ) ∧

A semi-base formula whose associated graph is cyclic is unsatisfiable in the term algebra of finite terms. Checking the
cyclicity of a base formula corresponds to occur-check in
unification algorithms (see e.g. [29, 11]).

labels(u1 , . . . , un ; x1 , . . . , xm )
distinct(u1 , . . . , un ) enforces that variables are distinct
^
ui 6= uj .
distinct(u1 , . . . , un ) ≡

Definition 22 By height H(u) of a node u in the acyclic
graph we mean the length of the longest path starting from
u.

1≤i<j≤n

structure(u1 , . . . , un ) specifies relationships between terms
denoted by variables:

A node u is sink iff H(u) = 0.

structure(u1 , . . . , un ) ≡
p
V

Definition 23 We say that an internal variable ul is a
source variable of a base formula β iff ul is represented by
a node that is source in the directed acyclic graph corresponding to β. Equivalently, if β is written in the selector
language, then ul is a source variable iff β contains no equations of form ul = fi (uk ).

ui = ti (u1 , . . . , un )

i=1

where each ti (u1 , . . . , un ) is a term of form f (ul1 , . . . , ulk )
for f ∈ Σ, k = ar(f ).
labels(u1 , . . . , un ; x1 , . . . , xm ) identifies some free variables with some parameter and non-parameter variables:
^
xi = uji
labels(u1 , . . . , un ; x1 , . . . , xm ) ≡

Definition 24 If ui and uj are internal variables, we write
ui ֌∗ uj if there is a path in the underlying graph from node
ui to node uj . Equivalently, ui ֌∗ uj iff there exists a term
t(ui ) in the selector language such that |= β ⇒ uj = t(ui ).

1≤i≤m

12

Relation ֌∗ is a partial order on internal variables of β.
The following Lemma 25 is similar to the Independence
of Disequations Lemma in e.g. [10, Page 178].

Proof. Consider a formula ∃x.β where β is a base formula.
The only place where x occurs in β is x = us1 in the subformula labels. By dropping the conjunct x = us1 from β we
obtain a base formula β1 where β1 is equivalent to ∃x.β.

Lemma 25 Let β be a base formula of the form
∃u1 , . . . , up , up+1 , . . . , up+q . β0

Proposition 28 (Quantifier-Free to Base) Every welldefined quantifier-free formula in constructor-selector language can be written as true, false, or a disjunction of base
formulas.

where up+1 , . . . , up+q are parameter variables of β, and β0 is
quantifier-free. Let Sp+1 , . . . , Sp+q be infinite sets of terms.
Then there exists a valuation σ such that Jβ0 Kσ = true and
Jui Kσ ∈ Si for p + 1 ≤ i ≤ p + q.

Proof Sketch.
Let φ be a well-defined quantifier-free
formula in constructor-selector language. By Proposition 8
we can transform φ into an equivalent formula in disjunctive
normal form
ψ1 ∨ · · · ∨ ψp

Proof. To construct σ assign first the values to parameter
variables, as follows. Let hG be the length of the longest
path in the graph associated with β. Pick σ(up+1 ) ∈ Sp+1 so
that h(σ(up+1 )) > hG , and for each i where p + 2 ≤ i ≤ p + q
pick σ(ui ) ∈ Si so that h(σ(ui )) > h(σ(ui−1 )) + hG . The
set of heights of an infinite set of terms is infinite, so it is
always possible to choose such σ(ui ).
Next consider internal nodes u1 , . . . , up+q in some topological order.
For each non-parameter node ui such
that ui = f (ul1 , . . . , ulk ) occurs in β0 , let σ(ui ) =
f (σ(uli ), . . . , σ(ulk )).
Finally assign the values to free variables by σ(x) = σ(u)
where x = u occurs in β0 .
By construction, JstructureKσ = true and JlabelsKσ =
true. It remains to show JdistinctKσ = true i.e. σ(ui ) 6= σ(uj )
for 1 ≤ i, j ≤ p + q, i 6= j. We show this property of σ
by induction on m = min(H(ui ), H(uj )). Without loss of
generality we assume H(ui ) ≤ H(uj ).
Consider first the case m = 0. Then ui is a parameter
or a constant node.
If ui is a constant and uj is a non-parameter variable
then ui and uj are labelled by different function symbols so
σ(ui ) 6= σ(uj ).
If ui is a constant and uj is a parameter variable then
h(σ(ui )) = 0 whereas h(σ(uj )) > hG ≥ 0.
Consider the case where ui is a parameter variable and
uj is a non-parameter variable. Let

where each ψi is a well-defined conjunction of literals. Consider an arbitrary ψi . There exists an unnested quantifierfree formula ψi′ with additional fresh free variables x1 , . . . , xq
such that ψi is equivalent to
∃x1 , . . . , xq . ψi′
By distributivity and (6) it suffices to transform each conjunction of unnested formulas into disjunction of base formulas. In the sequel we will assume transformations based
on distributivity and (6) are applied whenever we transform
conjunction of literals into a formula containing disjunction.
We also assume that every equation f (x1 , . . . , xn ) = y is
replaced by the equivalent one y = f (x1 , . . . , xn ) and every
equation fi (x) = y is replace by y = fi (x).
Because of our assumption that Σ is finite, we can eliminate every literal of form ¬Isf (x) using the equivalence
_
Isg (x)
(17)
¬Isf (x) ⇐⇒
g∈Σ\{f }

which follows from (16). We then transform formula back
into disjunctive normal form and propagate the existential
quantifiers to the conjunctions of literals. We may therefore
assume that there are no literals of form ¬Isf (x) in the conjunction. Furthermore, Isf (x) ∧ Isg (x) ⇐⇒ false for f 6≡ g,
so we may assume that for variable x there is at most one
literal Isf (x) for some f . If fi (x) occurs in the conjunction,
because the conjunction is well-defined, we may always add
the conjunct Isf (x). This way we ensure that exactly one
literal of form Isf (x) occurs in the conjunction.
We next ensure that every variable has either none or
all of its components named by variables. If the conjunction
contains literal Isf (x) but does not contain x = f (x1 , . . . , xn )
and does not contain an equation of form y = fi (x) for
every i, 1 ≤ i ≤ ar(f ), we introduce a fresh existentially
quantified variable for each i such that a term of form y =
fi (x) does not appear in the conjunction. At this point
we may transform the entire conjunction into constructor
language by replacing

J = {j1 | uj1 is a parameter variable s.t. uj ֌∗ uj1 }
If J = ∅, then β0 uniquely specifies σ(uj ), and
h(σ(uj )) = H(uj ) ≤ hG < h(σ(ui ))
Let J 6= ∅ and j0 = max J. If i ≤ j0 , then
h(σ(ui )) ≤ h(σ(uj0 )) < h(σ(uj ))
If j0 < i then
h(σ(uj )) ≤ h(σ(uj0 )) + hG < h(σ(uj0 +1 )) ≤ h(σ(ui ))
Now consider the case m > 0. ui and uj are nonparameter nodes, so let ui = f (ui1 , . . . , uik ) and uj =
g(uj1 , . . . , ujl ). If f 6= g then clearly σ(ui ) 6= σ(uj ). Otherwise, by congruence closure property of base formulas, there
exists d such that uid 6= ujd . Then by induction hypothesis
σ(uid ) 6= σ(ujd ), so σ(ui ) 6= σ(uj ).

Isf (ui ) ∧ vl1 = f1 (ui ) ∧ · · · ∧ vlk = fk (ui )
with ui = f (vl1 , . . . , vlk ) for k = ar(f ).
We next ensure that for every two variables x1 and x2
occurring in the conjunction exactly one of the conjunct
x1 = x2 or x1 6= x2 is present. Namely if both conjuncts
x1 = x2 and x1 6= x2 are present, the conjunction is false.
If none of the conjuncts is present, we insert the disjunction

Corollary 26 Every base formula is satisfiable.
Proposition 27 (Quantification of Base Formula) If
β is a base formula and x a free variable in β, then there
exists a base formula β1 equivalent to ∃x.β.
13

x1 = x2 ∨ x1 6= x2 as one of the conjuncts and transform
the result into disjunction of existentially quantified conjunctions.
We next perform congruence closure for finite terms [38]
on the resulting conjunction, using the fact that equality is
reflexive, symmetric, transitive and congruent with respect
to free operations f ∈ Cons(Σ) and that t(x) 6= x for every
term t 6≡ x. Syntactically, the result of congruence closure
can be viewed as adding new equations to the conjunction.
If the congruence closure procedure establishes that the formula is unsatisfiable, the result is false. Otherwise, all variables are grouped into equivalence classes. If a u1 = u2
occurs in the conjunction where both u1 and u2 are internal
variables, we replace u1 with u2 in the formula and eliminate the existential quantifier. If for some free variable x
there is no internal variable u such that conjunction x = u
occurs, we introduce a new existentially quantified variable
and a conjunct x = u. These transformations ensure that
for every equivalence class there exists exactly one internal
variable in the formula. It is now easy to pick representative
conjuncts from the conjunction to obtain conjunction of the
syntactic form in Definition 19 of semi-base formula. The
resulting formula is a base formula because congruence closure algorithm ensures that the associated graph is acyclic.

every variable u we obtain a quantifier-free formula equivalent to β.
Definition 31 Let β be a base formula. The set determined
of determined variables of β is the smallest set S that contains the set covered and satisfies the following condition:
if u is a non-parameter node and all successors u1 , . . . , uk
(k ≥ 0) of u in the associated graph are in S, then u is also
in S.
In particular, every constant node is determined. A parameter node w is determined iff w is covered.
Lemma 32 If a node u is not determined, then there exists
an uncovered parameter node v such that u ֌∗ v.
Proof. The proof is by induction on H(()u). If H(()u) = 0
then u has no successors, and u cannot be a constant node
because it is not determined. Therefore, u is a parameter
node, so we may let v ≡ u. Assume that the statement
holds for for every node u′ such that H(()u′ ) = k and let
H(()u) = k + 1. Because u is not determined, there exists
a successor u′ of u such that u′ is not determined, so by
induction hypothesis there exists an uncovered parameter
node v such that u′ ֌∗ v. Hence u ֌∗ u′ ֌∗ v.

We next turn to the problem of transforming a base formula into a quantifier-free formula. We will present two
constructions. The first construction yields a quantifier-free
formula in constructor-selector language and is sufficient for
the purpose of quantifier elimination. The second construction yields a quantifier-free formula in selector language and
is slightly more involved; we present it to provide additional
insight into the quantifier elimination approach to term algebras.
We first introduce notions of covered and determined
variables of a base formula β. The basic idea behind these
notions is that β implies a functional dependence from the
free variables of β to each of the determined variables.
In both constructions we use the notion of a a covered
variable, which denotes a component of a term denoted by
some free variable. In the first construction we also use the
notion of determined variable, which includes covered variables as well as variables constructed from covered variables
using constructor operations f ∈ Cons(Σ).

Lemma 33 Every base formula β is equivalent to a base
formula β ′ obtained from β by eliminating all nodes that are
not determined.
Proof.
Construct β ′ from β by eliminating all terms
containing a variable u ∈ U \ determined and eliminating
the corresponding existential quantifiers. Then all variables
in β ′ are determined. β ′ has fewer conjuncts than β, so
|= β ⇒ β ′ . To show |= β ′ ⇒ β, let σ be any assignment
of terms to determined variables of β such that β evaluate
to true under σ. As in the proof of Lemma 25, define the
extension σ ′ of σ as follows. Choose sufficiently large values
σ ′ (v) for every uncovered sink variable v, so that σ ′′ defined
as the unique extension of σ ′ to the remaining undetermined
variables assigns different terms to different variables. This
is possible because the term model is infinite. The resulting assignment σ ′′ satisfies the matrix of the base formula
β. Therefore, |= β ′ ⇒ β, so β and β ′ are equivalent base
formulas.

Definition 29 Consider an arbitrary base formula β. We
say that an internal variable u is covered by a free variable
x iff x = u′ occurs in β for some u′ such that u ֌∗ u′ . An
internal variable u is covered iff u is covered by x for some
free variable x (in particular, if x = u occurs in β then u
is covered). Let covered denote the set of covered internal
variables of base formula, and let uncovered = U \ covered
where U is the set of all internal variables of β.

First Construction
Proposition 34 (Base to Constructor-Selector)
Every base formula β is equivalent to a quantifier-free
formula φ in constructor-selector language.
Proof. By Lemma 33 we may assume that all variables
in β are determined. To every variable u we assign a term
τ (u). Term τ (u) is in constructor-selector language and the
variables of τ (u) are among the free variables of β. If u ∈
covered, we assign τ (u) as in the proof of Lemma 30. If
u1 , . . . , uk are the successors of a determined node u, we
put
τ (u) = f (τ (u1 ), . . . , τ (uk ))

Lemma 30 (Covered Base to Selector) Every
base
formula without uncovered variables is equivalent to a
quantifier free formula in selector language.
Proof. Consider a base formula β where every variable
is covered. Consider an arbitrary quantified variable u. Because u is covered, there exists variable x free in β such that
u = t(x) for some term t in the selector language. Replace
every occurrence of u in the matrix of β by t(x) and eliminate the quantification over u. Repeating this process for

where f is the label of node u. This definition uniquely
determines τ (u) for all u ∈ determined. We obtain the
quantifier-free formula φ by replacing every variable u with
τ (u) and eliminating all quantifiers.
14

For every u we have |= β ⇒ u = τ (u), so |= β ⇒ φ.
Conversely, if φ is satisfied then τ defines an assignment for
u variables which makes the matrix of β true. Therefore β
and φ are equivalent.

and determined, it is not a parameter node. We show how to
eliminate u0 without introducing new uncovered variables.
Our goal is to eliminate u0 from the associated graph.
We need to preserve information that u0 is distinct from
variables u ∈ U \ {u0 } in the graph. We consider two cases.
If u is not a parameter node, then by congruence closure
either u0 and u are labelled by different function symbols,
or they are labelled by the same function symbol f ∈ Σ
with ar(f ) = k and there exists i, 1 ≤ i ≤ k and variables
ui = fi (u0 ) and u′i = fi (u′ ) such that ui 6≡ u′i . Hence the
constraint u0 6= u is deducible from the inequalities of other
variables in β and we can eliminate u0 without changing the
truth value of β.
Next consider the case when u is a parameter node. By
assumption u is determined, and because it is parameter, it
is covered. We then perform parameter node expansion as
described above. The result of elimination of u0 in β is a
disjunction of base formulas β ′ , in each β ′ every parameter
node is expanded. If u is a parameter node in β then the
constraint u0 6= u is preserved in each β ′ because u is not a
parameter node in β ′ so the previous argument applies.
Because the parameter nodes being expanded are covered, so are their successor nodes introduced by parameter
expansion. Therefore, by repeatedly applying elimination
of uncovered variables for every uncovered variable u0 , we
obtain a disjunction ∆ of formulas β ′ where each β ′ has no
uncovered variables, and ∆ is equivalent to β.

Second Construction The reason for using constructor
symbols f ∈ Cons(Σ) in the first construction is to preserve the constraints of form u 6= v when eliminating node
u with successors u1 , . . . , uk . Using constructor symbols we
would obtain the constraint f (u1 , . . . , uk ) 6= v. Our second
construction avoids introducing constructor operations by
decomposing f (u1 , . . . , uk ) 6= v into disjunction of inequalities of form ui 6= fi (v). When v is a parameter node, the
presence of term fi (v) potentially requires introducing a new
node in the associated graph, we call this process parameter expansion. Parameter expansion may increase the total
number of nodes in the graph, but it decreases the number of uncovered nodes, so the process of converting a base
formula to a quantifier-free formula in the selector language
terminates.
Lemma 35 Let β be an arbitrary base formula.
1. If u is covered and u ֌∗ u′ then u′ is covered as well.
2. If u′ is uncovered and u′ is not a source, then there
exists u 6≡ u′ such that u ֌∗ u′ and u is also uncovered.
3. If β contains an uncovered variable then β contains an
uncovered variable that is a source.

Proposition 38 (Base to Selector) For every base formula β there exists an equivalent quantifier-free formula ψ
in selector language.

Proof. By definition.

Proof.
By Lemma 37, β is equivalent to a disjunction
β1 ∨ · · · ∨ βn where each βi has no uncovered variables. By
Lemma 30, each βi is equivalent to some quantifier free formula ψi , so β is equivalent to the quantifier-free formula
ψ1 ∨ · · · ∨ ψn .

Parameter Expansion We define the operation of expanding a parameter node in a base formula as follows. Let
β be an arbitrary base formula and w a parameter variable
in β. The result of expansion of w is a disjunction of base
formulas β ′ generated by applying (13) to w. In each of
the resulting formulas β ′ variable w is not a parameter any
more. Each β ′ contains Isf (w) for some f ∈ Σ and node w
has successors u1 , . . . , uk for k = ar(f ). Each successor ui is
either an existing internal variable or a fresh variable. For a
given β, sink expansion generates disjunction of formulas β ′
for every choice of f ∈ Σ and every choice of successors ui ,
subject to congruence closure so that β ′ is a base formula:
we discard the choices of successors of w that yield formulas
β ′ violating congruence of equality. (This process is similar to converting quantifier-free formulas into disjunction of
base formulas in the proof of Proposition 28.) The following
lemma shows the correctness of parameter expansion.

The final theorem in this section summarizes quantifier elimination for term algebra.
Theorem 39 (Term Algebra Quantifier Elimination)
There exist algorithms A, B, C such that for a given formula
φ in constructor-selector language of term algebras:
a) A produces a quantifier-free formula φ′ in constructorselector language
b) B produces a quantifier-free formula φ′ in selector language
c) C produces a disjunction φ′ of base formulas

Lemma 36 (Parameter expansion soundness) Let
∆ = β1′ ∨ · · · βk′ be the disjunction generated by parameter
expansion of a base formula β. Then ∆ is equivalent to β.

Proof. a): Transform formula φ into prenex form

Lemma 36 justifies the use of parameter expansion in the
following Lemma 37.

where φ∗ is quantifier free, as in Section 3.1. We eliminate
the innermost quantifier Qn as follows.
Suppose first that Qn is ∃. Transform the matrix φ∗ into
disjunctive normal form C1 ∨ · · · ∨ Cn . By Proposition 28,
transform C1 ∨ · · · ∨ Cn into disjunction β1 ∨ · · · ∨ βm of base
formulas. Then propagate ∃ into individual disjuncts, using

Q1 x1 . . . Qn−1 xn−1 Qn xn .φ∗

Lemma 37 Every base formula β can be written as a disjunction of base formulas without uncovered variables.
Proof Sketch. By Lemma 33 we may assume that all variables of β are determined. Suppose β contains an uncovered
variable. Then by Lemma 35, β contains an uncovered variable u0 such that u0 is a source. Because u0 is uncovered

∃xn . β1 ∨ · · · ∨ βm ⇐⇒ (∃xn .β1 ) ∨ · · · ∨ (∃xn .βm )

15

Consider a signature Σ = {a, b, g} where a and b are
constant symbols and g is a function symbol of arity 2. We
define a partial order ≤ on the set FT(Σ) of ground terms
over Σ as the least reflexive partial order relation ρ satisfying

By Proposition 27, an existentially quantified base formula
is again a base formula, so ∃xn .βi ⇐⇒ βi′ for some βi′ . We
thus obtain the
′
Q1 x1 . . . Qn−1 xn−1 . β1′ ∨ · · · ∨ βm

(18)

1. a ρ b;

By Proposition 34, every base formula is equivalent to a
quantifier-free formula in selector language, so 18 is equivalent to
Q1 x1 . . . Qn−1 xn−1 .ψ

2. (s1 ρ t1 ) ∧ (s2 ρ t2 ) ⇒ g(s1 , s2 ) ρ g(t1 , t2 ).
The structure with equality in the language {a, b, g, ≤},
where ≤ is interpreted as above and a, b, g are interpreted
as free operations on term algebra corresponds to the structural subtyping with two base types a and b and one binary
type constructor g, with g covariant in both arguments. We
denote this structure by BS. We proceed to show that BS
admits quantifier elimination and is therefore decidable.

where ψ is a quantifier free formula. Hence, we have eliminated the innermost existential quantifier.
Next consider the case when Qn is ∀. Then φ is equivalent to
Q1 x1 . . . Qn−1 xn−1 ¬∃xn .¬φ∗
Apply the procedure for eliminating xn to ¬φ∗ . The result
is formula of form
Q1 x1 . . . Qn−1 xn−1 . ¬ψ

4.1

Boolean Algebras on Equivalent Terms

In preparation for the quantifier elimination procedure we
define certain operations and relations on terms. We also
establish some fundamental properties of the structure BS.
Define a new signature Σ0 = {cs , g s } as an abstraction of
signature Σ = {a, b, g}. Define function shapified : Σ → Σ0
by
shapified(a) = cs

(19)

where ψ is quantifier free. But ¬ψ is also quantifier free, so
we have eliminated the innermost universal quantifier. By
repeating this process we eliminate all quantifiers, yielding
the desired formula φ′ .
The direct construction for showing b) is analogous to
a), but uses Proposition 38 in place of Proposition 34. To
show c), apply e.g. construction a) to obtain a quantifierfree formula ψ and then transform ψ into disjunction of base
formulas using Proposition 28.

shapified(b) = cs
shapified(g) = g s
Let ar(shapified(f )) = ar(f ) for each f ∈ Σ; in this case cs is
a constant and g s is a binary function symbol. Let FT(Σ0 )
be the set of ground terms over the signature Σ0 . Define
shape of a term t, as the function sh : FT(Σ) → FT(Σ0 ), by
letting
sh(f (t1 , . . . , tk )) =

This completes our description of quantifier elimination
for term algebras.
We remark that there are alternative ways to define base
formula. In particular the requirement on disequality of all
variables is not necessary. This requirement may lead to
unnecessary case analysis when converting a quantifier-free
formula to disjunction of base formulas, but we believe that
it simplifies the correctness argument.

shapified(f )(sh(t1 ), . . . , sh(tk ))
for k = ar(f ). In this case we have
sh(a) = cs

4

The Pair Constructor and Two Constants

sh(b) = cs

In this section we give a quantifier elimination procedure for
structural subtyping of non-recursive types with two constant symbols and one covariant binary constructor. Two
constants corresponds to two primitive types; one binary
covariant constructor corresponds to the pair constructor
for building products of types.
The construction in this section is an introduction to
the more general construction in Section 5, where we give a
quantifier elimination procedure for any number of constant
symbols and relations between them. The construction in
this section demonstrates the interaction between the term
and boolean algebra components of the structural subtyping.
We therefore believe the construction captures the essence
of the general result of Section 5.
The basic observation behind the quantifier elimination
procedure for two constant symbols is that the structure of
terms in this language is isomorphic to a disjoint union of
boolean algebras with some additional term structure connecting elements from different boolean algebras. As we argue below, the structural subtyping structure contains one
copy of boolean algebra for every equivalence class of terms
that have the same “shape” i.e. are same up to the constants
in the leaves.

sh(g(t1 , t2 ))

= g s (sh(t1 ), sh(t2 ))

Define t1 ∼ t2 iff sh(t1 ) = sh(t2 ). Then ∼ is the smallest
equivalence relation ρ such that
1. a ρ b;
2. (s1 ρ t1 ) ∧ (s2 ρ t2 ) ⇒ g(s1 , s2 ) ρ g(t1 , t2 ).
For every term t define the word tCont(t) ∈ {0, 1}∗ by letting
tCont(a) =

0

tCont(b) =

1

tCont(f (t1 , t2 )) =

tCont(t1 ) · tCont(t2 )

The set of all words w ∈ {0, 1}n is isomorphic the boolean
algebra of Bn of all subsets of some finite sets of cardinality
n, so we write w1 ∩w2 , w1 ∪w2 , wc for operations corresponding to intersection, union, and set complement in the set of
words w ∈ {0, 1}n . We write w1 ⊆ w2 for w1 ∩ w2 = w1 .
Define function δ by
δ(t) = hsh(t), tCont(t)i
16

For term t in any language containing constant symbols, let
tLen(t) denote the number of occurrences of constant symbols in t. If w is a sequence of elements of some set, let
sLen(w) denote the length of the sequence. Observe that
sLen(tCont(t)) = tLen(t) and tLen(sh(t)) = tLen(t). Moreover, t1 ∼ t2 implies sLen(tCont(t1 )) = sLen(tCont(t2 )). Define the set B by

a, b ::

term

g

::

term × term → term

Isg

::

term → bool

g1 , g2

::

term → term

B = {hs, wi | s ∈ FT(Σ0 ), w ∈ {0, 1}∗ , tLen(s) = sLen(w)}
Function δ is a bijection from the set FT(Σ) to the set B.
For b1 , b2 ∈ B define b1 ≤ b2 iff δ −1 (b1 ) ≤ δ −1 (b2 ). From
the definitions it follows

= ::

term × term → bool

≤ ::

term × term → bool

s

::

shape

s

::

shape × shape → shape

hs1 , w1 i ≤ hs2 , w2 i ⇐⇒ s1 = s2 ∧ w1 ⊆ w2

Isgs

::

shape → bool

If g is defined on B via isomorphism δ we also have

g1s , g2s

::

shape → shape

c
g

sh ::

s

g(hs1 , w1 i, hs2 , w2 i) = hg (s1 , s2 ), w1 · w2 i

=

For any fixed s ∈ FT(Σ0 ), the set
B(s0 ) = {hs, wi ∈ B | s = s0 }

∩ ,∪

(20)

c

is isomorphic to the boolean algebra Bn , where n = tLen(s).
Accordingly, we introduce on each B(s) the set operations
t1 ∩s t2 , t1 ∪s t2 , tc1s . Expressions t1 ∩s t2 and t1 ∪s t2 are
defined iff sh(t1 ) = s and sh(t2 ) = s, whereas expression tc1s
is defined iff sh(t1 ) = s.
We also introduce cardinality expressions as in Section 3.2. If t denotes a term, then the expression |t|s denotes the number of elements of the set corresponding to t.
Here we require s = sh(t). We use expressions |t|s = k and
|t|s ≥ k as atomic formulas for constant integer k ≥ 0. Note
that
t1 ≤ t2 ⇐⇒ sh(t1 ) = sh(t2 ) ∧ |t1 ∩ tc2 |sh(t1 ) = 0
t1 = t2 ⇐⇒

sh(t1 ) = sh(t2 ) ∧
|(t1 ∩ tc2 ) ∪ (tc1 ∩ t2 )|sh(t1 ) = 0

1 ,0
| | ≥ k, | | = k

4.2

= g(t1 ∩ t′1 , t2 ∩ t′2 )

g(t1 , t2 ) ∪ g(t′1 , t′2 )

= g(t1 ∪ t′1 , t2 ∪ t′2 )

g(t1 , t2 )c

(21)
(22)

(23)

= g(tc1 , tc2 )

If E(x1 , . . . , xn ) denotes an expression consisting only of operations of boolean algebra, then from (4.1) by induction
follows that
E(g(t11 , t21 ), . . . , g(t1n , t2n ))

=

::

shape × shape → bool

::

shape × term × term → term

::

shape × term → term

::

shape → term

::

shape × term → bool

A Multisorted Logic

To show the decidability of structure BS, we give a quantifier
elimination procedure for an extended structure, denoted
FT2 . We use a first-order two-sorted logic with sorts term
and shape interpreted over FT2 .
The domain of structure FT2 is FT(Σ) ∪ FT(Σ0 ) with elements FT(Σ) having sort term and elements FT(Σ0 ) having
sort shape. Variables in Var have term sort, variables in Vars
have shape sort. In general, if t denotes an element of FT2 ,
we write tS to indicate that the element has sort shape.
Figure 5 shows operations and relations in FT2 with their
sort declarations. The signature is infinite because operations |t|s ≥ k and |t|s = k are parameterized by a nonnegative integer k.
We require all terms to be well-sorted. Functions g1 and
g2 are interpreted as partial selector functions in the term
constructor-selector language, so Dg1 = Dg2 = hhxi, Isg (x)i.
Similarly, g1s and g2s are partial selector functions in the
shape constructor-selector language, so Dg1s = Dg2s =
hhxi, Isgs (x)i. The expressions t1 ∩s t2 and t1 ∪s t2 are defined
iff sh(t1 ) = sh(t2 ) = s, and tcs is defined iff sh(t) = s. We
therefore let

Equation 23 allows decomposing formulas of form
|g(t1 , t2 )|s ≥ k into propositional combinations of formulas
of form |t1 |s1 ≥ k and |t2 |s2 ≥ k.
Note further that the following equations hold:
g(t1 , t2 ) ∩ g(t′1 , t′2 )

term → shape

Figure 5: Operations and relations in structure FT2

Let sh(t1 ) = s1 , sh(t2 ) = s2 , and s = g s (s1 , s2 ). Then
|g(t1 , t2 )|s = |t1 |s1 + |t2 |s2

s

D∩s = D∪s =
hhy s , x1 , x2 i, sh(x1 ) = y s ∧ sh(x2 ) = y s i

g(E(t11 , . . . , t1n ), E(t21 , . . . , t2n ))

and

(24)

D c = hhy s , xi, sh(x) = y s i
For atomic formulas |t|s ≥ k and |t|s = k we require atomic
formula sh(t) = s to ensure well-definedness:

Equations (24) and (23) imply
|E(g(t11 , t21 ), . . . , g(t1n , t2n ))| = |E(t11 , . . . , t1n )| + |E(t21 , . . . , t2n )|
(25)
Boolean algebra B(g s (s1 , s2 )) is isomorphic to the product
of boolean algebras B(s1 ) and B(s2 ); the constructor g acts
as union of disjoint sets.

D|

| =k

= D|

| ≥k

= hhy s , xi, sh(x) = y s i

Note that the language of Figure 5 subsumes the language {a, b, g, ≤} for the structural subtyping structure. The
17

where each ti is a shape term of form f (usi1 , . . . , usik ) for
some f ∈ Σ0 , k = ar(f ), and j : {1, . . . , ms } → {1, . . . , ns } is
a function mapping indices of free shape variables to indices
of internal shape variables.

quantifier-elimination procedure we present in Section 4.3
is therefore sufficient for quantifier elimination in the firstorder logic interpreted over the structural subtyping structure FT2 .
4.3

termBase(u1 , . . . , un , x1 , . . . , xm ) =

Quantifier Elimination for Two Constants

p
V

We are now ready to present a quantifier elimination procedure for the structure FT2 . The quantifier elimination
procedure is based on the quantifier elimination for term algebras of Section 3.4 as well as the quantifier elimination for
boolean algebras of Section 3.2.
We first define an auxiliary notion of a us -term as a term
formed starting from shape us term variables and shape us
constants, using operations ∩us , ∪us , and cus .

i=1

cardin(up+1 , . . . , up+q , usps +1 , . . . , usps +qs ) = ψ1 ∧ · · · ∧ ψr

t ∩us t′ ∈ Term(us ),
t ∪us t′ ∈ Term(us ), and

where each ψi is of form

tcus ∈ Term(us )

|t(up+1 , . . . , up+q )|us = k

Similarly to base formulas of Section 3.4, we define structural base formulas for FT2 structure. A structural base formula contains a copy of a base formula for the shape sort
(shapeBase), a base formula for the term sort without term
disequalities (termBase), a formula expressing mapping of
term variables to shape variables (hom), and cardinality constraints on term parameter nodes of the term base formula
(cardin).

or
|t(up+1 , . . . , up+q )|us ≥ k
s

for some u -term t(up+1 , . . . , up+q ) that contains no variables other than some of the variables up+1 , . . . , up+q , and
the following condition holds:
If a variable up+j occurs in term
t(up+1 , . . . , up+q ), then sh(up+j ) = us
occurs in formula hom.

Definition 41 (Structural Base Formula)
A structural base formula with:
• internal non-parameter term variables u1 , . . . , up ;

P0) the graph associated with shape base formula

• internal parameter term variables up+1 , . . . , up+q ;

∃us1 , . . . , usns . shapeBase(us1 , . . . , usns , xs1 , . . . , xsms )

• free shape variables xs1 , . . . , xsms ;

is acyclic (compare to Definition 21);

• internal non-parameter shape variables us1 , . . . , usps ;

P1) congruence closure property for shapeBase subformula:
there are no two distinct variables usi and usj such that
both usi = f (usl1 , . . . , uslk ) and usj = f (usl1 , . . . , uslk ) occur
as conjuncts in formula shapeBase;

• internal parameter shape variables usps , . . . , usps +qs
is a formula of form:
∃u1 , . . . , un , us1 , . . . , usns .

P2) congruence closure property for termBase subformula:
there are no two distinct variables ui and uj such that
both ui = f (ul1 , . . . , ulk ) and uj = f (ul1 , . . . , ulk ) occur
as conjuncts in formula termBase;

shapeBase(us1 , . . . , usns , xs1 , . . . , xsms ) ∧
termBase(u1 , . . . , un , x1 , . . . , xm ) ∧
hom(u1 , . . . , un , us1 , . . . , usns ) ∧

P3) homomorphism property of sh: for every non-parameter
term variable u such that u = f (ui1 , . . . , uik ) occurs
in termBase, if the conjunct sh(u) = us occurs in
hom, then for some shape variables usj1 , . . . , usjk the
term us = f s (usj1 , . . . , usjk ) occurs in shapeBase where
f s = shapified(f ) and for every r where 1 ≤ r ≤ k,
conjunct sh(uir ) = usjr occurs in hom.

cardin(up+1 , . . . , un , usps +1 , . . . , usns )
where n = p + q, ns = ps + q s , and formulas shapeBase,
termBase, hom, and cardin are defined as follows.
shapeBase(us1 , . . . , usns , xs1 , . . . , xsms ) =
m
Vs

i=1

(26)

We require each structural base formula to satisfy the
following conditions:

• free term variables x1 , . . . , xm ;

∧ distinct(us1 , . . . , usn )

sh(ui ) = usji

where j : {1, . . . , n} → {1, . . . , ns } is some function such
that {j1 , . . . , jp } ⊆ {1, . . . , ps } and {jp+1 , . . . , jp+q } ⊆ {ps +
1, . . . , ps + q s } (a term variable is a parameter variable iff its
shape is a parameter shape variable).

3. if t, t′ ∈ Term(us ), then also

i=1

n
V

i=1

2. 0us , 1us ∈ Term(us )

usi = ti (us1 , . . . , usn ) ∧

xi = uji

i=1

hom(u1 , . . . , un , us1 , . . . , usns ) =

1. Var ⊆ Term(us )

s

m
V

where each ti is a term of form f (ui1 , . . . , uik ) for some
f ∈ Σ, k = ar(f ), and j : {1, . . . , m} → {1, . . . , n} is a
function mapping indices of free term variables to indices of
internal term variables.

Definition 40 (us -terms) Let us ∈ Vars be a shape variable. The set of us -terms Term(us ) is the least set such that:

p
V

ui = ti (u1 , . . . , un ) ∧

xsi = usji

18

u svz

u sw

v

u vz

uv

We next use (21) to eliminate atomic formulas t1 ≤ t2 and
replace them with cardinality constraints, resulting in formula φ2 equivalent to φ1 :

u zv

z

w

uz

φ2 ≡ φ2,1 ∧ φ2,2

uw

where
s
uw1

u v1

u z1

uw1

s
uw2

u v2

u z2

φ2,1 ≡ |g(v, z) ∩ g(z, v)c |sh(g(v,z)) = 0 ∧

uw2

sh(g(v, z)) = sh(g(z, v)) ∧

(30)

Isg (v) ∧ Isg (w)
Figure 6: One of the Base Formulas Resulting from (28)

and
φ2,2 ≡

According to Definition 41 a structural base formula contains no selector function symbols. Formulation using selector symbols is also possible, as in Definition 20. The
only partial function symbols occurring in a structural base
formula of Definition 41 are in cardin subformula. Condition (26) therefore ensures that functions in cardin and thus
the entire base formula are well-defined.
Note that acyclicity of shape base formula shapeBase
(condition P0) implies acyclicity of term base formula as
well. Namely, condition P3 ensures that any cycle in
termBase implies a cycle in shapeBase.
As in Section 3.4 we proceed to show that each quantifierfree formula can be written as a disjunction of base formulas
and each base formula can be written as a quantifier-free
formula.
We strongly encourage the reader to study the following
example because it illustrates the idea behind our quantifierelimination decision procedure.


¬ |g1 (w) ∩ g1 (v)c |sh(g1 (w)) = 0 ∧ sh(g1 (w)) = sh(g1 (v))
(31)
Here we have written e.g.
|g(v, z) ∩ g(z, v)c |sh(g(v,z)) = 0
as a shorthand for
|g(v, z) ∩sh(g(v,z)) g(z, v)csh(g(v,z)) |sh(g(v,z)) = 0
(In general, we omit term shape arguments for boolean algebra operations if the arguments are identical to the enclosing
term shape argument of the cardinality constraint.)
We next transform φ2 into disjunction of well-defined
conjunctions. Following the ideas in Proposition 8, we transform φ2,2 into φ3,1 ∨ φ3,2 where
φ3,1 ≡

Example 42 The following sentence is true in structure
FT2 .

|g1 (w) ∩ g1 (v)c |sh(g1 (w)) ≥ 1 ∧ sh(g1 (w)) = sh(g1 (v))
(32)
and
φ3,2 ≡ sh(g1 (w)) 6= sh(g1 (v))

∀x, y. x ≤ y ⇒
∃z. z ≤ x ∧ z ≤ y ∧

and then transform φ2,1 ∧ φ2,2 into

∀w. w ≤ x ∧ w ≤ y ⇒

(φ2,1 ∧ φ3,1 ) ∨ (φ2,1 ∧ φ3,2 )

∀v. g(v, z) ≤ g(z, v) ∧ Isg (v) ∧ Isg (w) ⇒ g1 (w) ≤ g1 (v)
(27)
An informal proof of sentence (27) is as follows. Suppose
that x ≤ y. Then sh(x) = sh(y) = xs . Let z = x ∩xs y.
Now consider some w such that w ≤ x and w ≤ y. Then
sh(w) = xs , so w ≤ z. Suppose that v is such that g(v, z) ≤
g(z, v). Then by covariance of g we have z ≤ v, so w ≤ v. If
we assume Isg (w) and Isg (v), then g1 (w) and g1 (v) are well
defined and by covariance of g we conclude g1 (w) ≤ g1 (v),
as desired.
We now give an alternative argument that shows that
sentence (27) is true. This alternative argument illustrates
the idea behind our quantifier-elimination decision procedure. For the sake of brevity we perform some additional
simplifications along the way that are not part of the procedure we present (although they could be incorporated to
improve efficiency), and we skip consideration of some uninteresting cases during the case analyses.
Let us first eliminate the quantifier from formula

For the sake of brevity we ignore the case φ2,1 ∧ φ3,2 ; it is
possible to show that φ2,1 ∧ φ3,2 is equivalent to false in the
context of the entire formula.
We transform φ2,1 ∧ φ3,1 into unnested form, introducing
fresh existentially quantified variables uvz ,uzv ,uw1 ,uv1 , usvz ,
usw1 that denote terms occurring in φ2,1 ∧ φ3,1 . The result
is formula φ4 where
φ4 ≡

∃uvz , uzv , uw1 , uv1 , usvz , usw1 .
uvz = g(v, z) ∧ uzv = g(z, v) ∧
uw1 = g1 (w) ∧ uv1 = g1 (v) ∧
usvz = sh(uvz ) ∧ usw1 = sh(uw1 ) ∧
sh(uzv ) = usvz ∧ sh(uv1 ) = usw1 ∧
Isg (v) ∧ Isg (w) ∧
|uvz ∩ uczv |usvz = 0 ∧ |uw1 ∩ ucv1 |usw1 ≥ 1

∀v. g(v, z) ≤ g(z, v) ∧ Isg (v) ∧ Isg (w) ⇒ g1 (w) ≤ g1 (v) (28)

(33)
To transform φ4 into disjunction of structural base formulas
we keep introducing new existentially quantified variables
and adding derived conjuncts to satisfy the invariants of
Definition 41.

Formula (28) is equivalent to ¬∃v.φ1 where
φ1 ≡ g(v, z) ≤ g(z, v) ∧ Isg (v) ∧ Isg (w) ∧ ¬(g1 (w) ≤ g1 (v))
(29)
19

Because Isg (v) and Isg (w) appear in the conjunct, we
give names to the remaining successors of v, w, by introducing uw2 = g2 (w), uv2 = g2 (v). We may now write
the constraints in constructor language, using e.g. conjunct
v = g(uv1 , uv2 ) instead of

v, z, w, respectively. The resulting structural base formula
is
∃uvz , uzv , uv , uz , uw , uv1 , uv2 , uz1 , uz2 , uw1 , uw2 ,
usvz , usw , usw1 , usw2 .

Isg (v) ∧ uv1 = g1 (v) ∧ uv2 = g2 (v)

shapeBase1 ∧ termBase1 ∧
hom1 ∧ cardin1

To ensure that every term variable has an associated shape
variable, we introduce fresh variables usv , usw , usz , usw2 , usv2
with conjuncts usv = sh(v), usw = sh(w), usz = sh(z), usw2 =
sh(uw2 ), usv2 = sh(uv2 ).
Note that base formula contains distinct(us1 , . . . , usn ) subformula. In the case when the current conjunction is not
strong enough to entail the disequality between shape variables usi and usj , we perform case analysis, considering the
case usi = usj (then usi can be replaced by usj ), and the case
usi 6= usj . This case analysis will lead to a disjunction of structural base formulas (unless some of the formulas is shown
contradictory in the transformation process). In contrast to
shape variables, we do not not perform case analysis for disequality of term variables, because termBase in Definition 41
does not contain a distinct subformula.
In this example we perform case analysis on whether
usw = usz and usw = usv should hold. For the sake of the example let us consider the case when usw = usz = usv , usv2 = usw2
and usvz , usw , usw1 , usw2 are all distinct. In that case shape
variables usw , usz , usv denote the same shape, so let us replace
e.g. usz and usv with usw . Similarly, we replace usv2 with usw2 .
We obtain conjuncts sh(v) = usw , sh(z) = usw , sh(uv2 ) = usw2 .
We next ensure homomorphism property P3 in Definition 41. From conjuncts uvz = g(v, z), sh(uvz ) = usvz , and
sh(v) = usw , we conclude

where
shapeBase1 = usvz = g s (usw , usw ) ∧ usw = g s (usw1 , usw2 ) ∧
distinct(usvz , usw , usw1 , usw2 )
termBase1 = uvz = g(uv , uz ) ∧ uzv = g(uz , uv ) ∧
uv = g(uv1 , uv2 ) ∧ uz = g(uz1 , uz2 ) ∧
uw = g(uw1 , uw2 ) ∧
v = uv ∧ z = uz ∧ w = uw
hom1 =
sh(uvz ) = usvz ∧ sh(uzv ) = usvz ∧
sh(uv ) = usw ∧ sh(uz ) = usw ∧ sh(uw ) = usw ∧
sh(uv1 ) = usw1 ∧ sh(uz1 ) = usw1 ∧ sh(uw1 ) = usw1 ∧
sh(uv2 ) = usw2 ∧ sh(uz2 ) = usw2 ∧ sh(uw2 ) = usw2
cardin1 = |uv1 ∩ ucz1 |usw1 = 0 ∧ |uz1 ∩ ucv1 |usw1 = 0 ∧
|uv2 ∩ ucz2 |usw2 = 0 ∧ |uz2 ∩ ucv2 |usw2 = 0 ∧
|uw1 ∩ ucv1 |usw1 ≥ 1

usvz = sh(uvz ) =

Figure 6 shows a graph representation of the subformulas
shapeBase1 , termBase1 , and hom1 of the resulting structural
base formula.
Recall that we are eliminating the quantification over v
from ¬∃v.φ1 . We can now existentially quantify over v. As
in Proposition 27, we simply remove the conjunct v = uv
from termBase and the quantifier ∃v.
As in Figure 4 of Section 3.4 the structural base formula form allows us to eliminate an existential quantifier,
whereas the quantifier-free form allows us to eliminate a
negation. We transform the structural base formula (35)
into a quantifier-free formula as follows.
We first use rule (7) to eliminate variable uvz , replacing
it with g(v, z). In the resulting formula g(v, z) occurs only
in hom1 in the form

sh(g(v, z)) =
g s (sh(v), sh(z)) =
g s (usw , usw )
so we add the conjunct usvz = g s (usw , usw ) to the formula.
Similarly, from w = g(uw1 , uw2 ), sh(w) = usw , sh(uw1 ) =
usw1 , sh(uw2 ) = usw2 we conclude usw = g(uw1 , uw2 ) and add
this conjunct to the formula. Adding these two conjuncts
makes property P3 hold. (Note that, had we decided to
consider the case where sh(v) 6= sh(z) we would have arrived
at a contradiction due to sh(usvz ) = sh(uszv ).)
We next apply rule (25) to reduce all cardinality constraints into cardinality constraints on parameter nodes
(nodes u for which there there is no conjunct of form
u = f (ui1 , . . . , uik )). We replace |uvz ∩ uczv |usvz = 0 with
|uv ∩

ucz |usw

= 0 ∧ |uz ∩

ucv |usw

=0

(35)

sh(g(uv , uz )) = usvz

(34)

(36)

But (36) is a consequence of conjuncts usvz = g s (usw , usw ),
sh(uv ) = usw and sh(uw ) = usw , so we omit (36) from the
formula. In analogous way we eliminate variable uzv and
the conjuncts that contain it. We also eliminate uv , analogously to uvz and uzv . In the resulting formula usvz occurs only in distinct subformula of shapeBase. Conjuncts
usvz 6= usw , usvz 6= usw1 , and usvz 6= usw2 follow from the remaining conjuncts in shapeBase by acyclicity. Hence we may
replace distinct(usvz , usw , usw1 , usw2 ) by distinct(usw , usw1 , usw2 ).
Now usvz does not occur in the matrix of the formula, so we
may eliminate ∃usvz altogether.

Variable v is a parameter variable, but z is not, which prevents application of (25). We therefore introduce uz1 and
uz2 such that z = g(uz1 , uz2 ). Because sh(z) = usw , we have
sh(uz1 ) = usw1 and sh(uz2 ) = usw2 by homomorphism property. We can now continue applying rule (25) to (34). The
result is:
|uv1 ∩ ucz1 |usw1 = 0 ∧ |uz1 ∩ ucv1 |usw1 = 0 ∧
|uv2 ∩ ucz2 |usw2 = 0 ∧ |uz2 ∩ ucv2 |usw2 = 0
To make the formula conform to Definition 41 we introduce
internal variables uv , uz , uw corresponding to free variables
20

variables are “covered”):

The resulting formula is:
φ5 ≡ ∃uz , uw , uv1 , uv2 , uz1 , uz2 , uw1 , uw2 , usw , usw1 , usw2 .
usw

=g

s

(usw1 , usw2 )

∧

distinct(usw , usw1 , usw2 )

uz = z

∧

uz = g(uz1 , uz2 ) ∧ uw = g(uw1 , uw2 ) ∧

sh(uz ) =

usw

∧ sh(uw ) =

usw

sh(uv2 ) =
|uv1 ∩

ucz1 |usw1

∧

∧ sh(uz2 ) =

usw2

= 0 ∧ |uz1 ∩

∧ sh(uw2 ) =

ucv1 |usw1

usw2

∧

uw2 = g2 (w)

φ7,2 ≡

sh(uv1 ) = usw1 ∧ sh(uz1 ) = usw1 ∧ sh(uw1 ) = usw1 ∧

|g1 (w) ∩ g1 (z)c |g1s (sh(w)) ≥ 1

|uw1 ∩ ucv1 |usw1 ≥ 1

(44)
Our quantifier elimination would also consider the case
sh(g2 (w)) 6= sh(g2 (z)). The procedure finds the case contradictory in a larger context, when eliminating ∃z, because
sh(z) = sh(x) = sh(w) follows from z ≤ x and w ≤ x. Ignoring this case, we observe that φ7,1 ∨ φ7,2 is equivalent to
the quantifier-free formula φ8 , where

(38)
Note that all variables from φ5,1 belong to B(s) where s
is the value of shape variable usw1 (see (20)). This means
that we can apply quantifier elimination for boolean algebra
(Section 3.2) to eliminate uv1 . The result is
(39)

Isgs (sh(w)) ∧ Isg (w) ∧ Isg (z) ∧

φ8 ≡

≥1

sh(z) = sh(w) ∧ |g1 (w) ∩ g1 (z)c |g1s (sh(w)) ≥ 1
(45)
Let us therefore assume that the result of quantifier elimination in (28) is ¬φ8 .
We proceed to eliminate the next quantifier, ∀w, from

Similarly, to eliminate uv2 we consider formula φ5,3 :
φ5,3 ≡ ∃uv2 .
sh(uv2 ) = usw2 ∧ sh(uz2 ) = usw2 ∧ sh(uw2 ) = usw2 ∧

∀w. w ≤ x ∧ w ≤ y ⇒ ¬φ8

|uv2 ∩ ucz2 |usw2 = 0 ∧ |uz2 ∩ ucv2 |usw2 = 0
(40)
The result of boolean algebra quantifier elimination on φ5,3
is true (indeed, one may let uv2 = uz2 ). The resulting base
formula with uv1 and uv2 eliminated is φ6 :

(46)

(46) is equivalent to
¬∃w. w ≤ x ∧ w ≤ y ∧ φ8
After eliminating ≤ we obtain

φ6 ≡ ∃uz , uw , uz1 , uz2 , uw1 , uw2 , usw , usw1 , usw2 .

¬∃w. |w ∩ xc |sh(w) = 0 ∧ sh(x) = sh(w) ∧

usw = g s (usw1 , usw2 ) ∧ distinct(usw , usw1 , usw2 ) ∧

|w ∩ y c |sh(w) = 0 ∧ sh(y) = sh(w) ∧

uz = g(uz1 , uz2 ) ∧ uw = g(uw1 , uw2 ) ∧
sh(uz ) = usw ∧ sh(uw ) = usw ∧

Isgs (sh(w)) ∧ Isg (w) ∧ Isg (z) ∧
sh(z) = sh(w) ∧ g1s (sh(w)) = g2s (sh(w)) ∧

|uv1 ∩ ucz1 |usw1 = 0 ∧ |uz1 ∩ ucv1 |usw1 = 0 ∧

z = uz ∧ w = uw ∧

= g1s (sh(w)) usw2 = g2s (sh(w))

sh(z) = sh(w) ∧ |g1 (w) ∩ g1 (z)c |g1s (sh(w)) ≥ 1
(43)
When transforming formula φ4 we chose the case usw1 6= usw1 .
If we choose the case usw1 = usw2 , we obtain quantifier-free
formula φ7,2 :

φ5,1 ≡ ∃uv1 .

ucz1 |usw1

= sh(w)

distinct(g1s (sh(w)), g2s (sh(w)))

(37)
We next eliminate uv1 . It suffices to eliminate it from conjuncts where it occurs, so we consider formula φ5,1 :

sh(uz1 ) = usw1 ∧ sh(uw1 ) = usw1 ∧

(42)

Isgs (sh(w)) ∧ Isg (w) ∧ Isg (z) ∧

φ7,1 ≡

=0∧

|uw1 ∩ ucv1 |usw1 ≥ 1

|uw1 ∩

uw1 = g1 (w)

Structural base formula φ6 is therefore equivalent to the
quantifier-free formula φ7,1 :

|uv2 ∩ ucz2 |usw2 = 0 ∧ |uz2 ∩ ucv2 |usw2 = 0 ∧

φ5,2 ≡

uz2 = g2 (z)

usw1

sh(uv1 ) = usw1 ∧ sh(uz1 ) = usw1 ∧ sh(uw1 ) = usw1 ∧
usw2

uz1 = g1 (z)
usw

z = uz ∧ w = uw ∧

uw = w

Isgs (sh(w)) ∧ Isg (w) ∧ Isg (z) ∧
sh(z) = sh(w) ∧ |g1 (w) ∩ g1 (z)c |g1s (sh(w)) ≥ 1

(41)

(47)
We now proceed similarly as in eliminating variable v. The
result is ¬φ9 where

sh(uz1 ) = usw1 ∧ sh(uw1 ) = usw1 ∧
sh(uz2 ) = usw2 ∧ sh(uw2 ) = usw2 ∧

φ9 ≡

|uw1 ∩ ucz1 |usw1 ≥ 1

sh(x) = sh(z) ∧ sh(y) = sh(z) ∧
Isg (x) ∧ Isg (y) ∧ Isg (z) ∧ Isgs (sh(z)) ∧

Observe that the equalities in φ6 are sufficient to express all
variables bound in φ6 in terms of free variables (all internal

(48)

c

|g1 (x) ∩ g1 (y) ∩ g1 (z) |g1s (sh(z)) ≥ 1
The remaining quantifiers that bind z, y, and x are eliminated similarly.
21

To eliminate the quantifier ∃z, we need to transform ¬φ9
into disjunction of base formulas. This transformation requires negation of φ9 and creates several disjuncts. We consider only the two cases, φ10 and φ11 , that are not contradictory in the enclosing context of conjuncts z ≤ x and z ≤ y:

unnested form
x = x1 ∩s x2

cardinality constraint
|x + (x1 ∩ x2 )|s = 0

x = x1 ∪s x2

|x + (x1 ∪ x2 )|s = 0

x=
φ10 ≡
φ11

sh(x) = sh(z) ∧ sh(y) = sh(z) ∧ ¬Isgs (sh(z))
(49)
≡ sh(x) = sh(z) ∧ sh(y) = sh(z) ∧
Isg (x) ∧ Isg (y) ∧ Isg (z) ∧ Isgs (sh(z)) ∧

|x + xc1 |s = 0

xc1s

Figure 7: Elimination of Boolean Algebra Unnested Formulas . Expression x + y is a shorthand for (x ∩ y c ) ∪ (y ∩ xc ).

(50)

c

|g1 (x) ∩ g1 (y) ∩ g1 (z) |g1s (sh(z)) = 0

In this case, formula φ6 ∧ψ1 is contradictory. Formula φ6 ∧ψ2
is equivalent to φ′′6 where

φ10 is equivalent to
sh(x) = cs ∧ sh(y) = cs ∧ sh(z) = cs

φ′′6 ≡ ∃uz , uw , uz1 , uz2 , uw1 , uw2 , usw , usw1 , usw2 .

(51)

usw = g s (usw1 , usw2 ) ∧ distinct(usw , usw1 , usw2 ) ∧

The result of eliminating ∃z from

uz = g(uz1 , uz2 ) ∧ uw = g(uw1 , uw2 ) ∧

∃z. |z ∩ xc |sh(z) = 0 ∧ |z ∩ y c |sh(z) = 0 ∧ φ10

z = uz ∧ w = uw ∧

is therefore

sh(uz ) = usw ∧ sh(uw ) = usw ∧

φ10,2 ≡

sh(x) = sh(y) ∧ ¬Isgs (sh(x))

(52)

The result of eliminating ∃z from
c

c

∃z. |z ∩ x |sh(z) = 0 ∧ |z ∩ y |sh(z) = 0 ∧ φ11
is
φ11,2 ≡ sh(x) = sh(y) ∧ Isgs (sh(x))

|x ∩ y |sh(x) = 0 ∧ sh(x) = sh(y) ⇒ sh(x) = sh(y)

∪

∧ sh(uw2 ) =

∧

≥1∧

(ucz

∩ uw )|usw ≥ 1


We proceed to sketch the general case of quantifier elimination. The following Proposition 44 is analogous to Proposition 27; the proof is again straightforward.


Formulas in the Example 42 do not contain disequalities between terms variables, only disequalities between shape variables. If a conjunction contains disequalities between term
variables, we eliminate the disequalities using rule (22) in
the process of converting formula to disjunction of structural base formulas. The following Example 43 illustrates
this process.

Proposition 44 (Quantification of Structural Base)
If β is a structural base formula and x a free term variable in β, then there exists a base structural formula β1
equivalent to ∃x.β.
The following Proposition 45 corresponds to Proposition 28.
Proposition 45 (Quantifier-Free to Structural Base)
Every well-defined quantifier-free formula φ in the language
of Figure 5 can be written as true, false, or a disjunction of
structural base formulas.

Example 43 Consider the formula
≡ φ6 ∧ uz 6= uw

Where φ6 is given by (41). By (22), literal uz 6= uw is
equivalent to ψ1 ∨ ψ2 where

Proof Sketch.
Let φ be a well-defined quantifier-free
formula in the language of Figure 5.
We first use rule (21) to eliminate occurrences of ≤ in
the formula replacing them with cardinality constraints.
We then convert formula into disjunction φ1 ∨ · · · ∨ φn of
well-formed conjunctions of literals. We next describe how
to transform each conjunction φi into a disjunction of base
formulas.
Let φi be a conjunction of literals. Using the technique
of Proposition 9, we convert the formula to unnested form,
adding existential quantifiers. We then eliminate unnested
conjuncts that contain boolean algebra operations, according to Figure 7. The only atomic formulas in the resulting

(53)

and
|(uz ∩ ucw ) ∪ (ucz ∩ uw )|sh(uz ) ≥ 1

|(uz ∩

ucw )

∧

usw2

and transform φ′′6 into a disjunction of base formulas.

to structural base formula yields true. We conclude that (27)
is a true sentence in the structure FT2 , which completes our
quantifier elimination procedure example.

ψ2 ≡ sh(uz ) = sh(uw ) ∧

|uw1 ∩

ucz1 |usw1

∧ sh(uw1 ) =

|(uz ∩ ucw ) ∪ (ucz ∩ uw )|usw ≥ 1

c

ψ1 ≡ sh(uz ) 6= sh(uw )

sh(uz2 ) =

usw2

(55)

usw1

As in Example 42, we now apply rule (25) to

φ10,2 ∨ φ11,2 is equivalent to sh(x) = sh(y). Converting

φ′6

sh(uz1 ) =

usw1

(54)

22

3. if hu, ti ∈ S and u = f (u1 , . . . , uk ) occurs in termBase
for some f ∈ Σ then {hu1 , f1 (t)i, . . . , huk , fk (t)i} ⊆ S;

existentially quantified conjunction are of form x = a, x = b,
x = g(x1 , x2 ), Isg (x), x1 = g1 (x), x2 = g2 (x), x1 = x2 ,
xs = cs , xs = g s (xs1 , xs2 ), Isgs (xs ), xs1 = g1s (xs ), xs2 = g2s (xs ),
xs1 = xs2 , xs = sh(x), as well as |t1 |xs ≥ k and |t2 |xs = k for
some xs -terms t1 and t2 . The only negated atomic formulas
are of form x1 6= x2 , xs1 6= xs2 , ¬Isg (x) and ¬Isgs (xs ). As in
the proof of Proposition 28, we use (17) to eliminate ¬Isg (x)
and ¬Isgs (xs ). This process leaves formulas of form x1 6= x2
and xs1 6= xs2 as the only negated atomic formulas.
In the sequel, whenever we perform case analysis and
generate a disjunction of conjunctions, existential quantifiers
propagate to the conjunctions, so we keep working with a
existentially quantified conjunction. The existentially quantified variables will become internal variables of a structural
base formula.
We next convert conjuncts that contain only term variables to a base formula, and convert shape part to base
formula, as in the proof of Proposition 28. We simultaneously make sure every term variable has an associated shape
variable, introducing new shape variables if needed. (This
process is interleaved with conversion to base formula, to ensure that there is always a conjunct stating that newly introduced shape variables are distinct.) We also ensure homomorphism requirement by replacing internal variables when
we entail their equality. Another condition we ensure is that
parameter term variables map to parameter shape variables,
and non-parameter term variables to non-parameter shape
variables; we do this by performing expansion of term and
shape variables. We perform expansion of shape variables as
in Section 3.2. Expansion of term variables is even simpler
because there is no need to do case analysis on equality of
term variable with other variables.
The resulting existentially quantified conjunction might
contain disequalities u 6= u′ between term variables. We
eliminate these disequalities as explained in Example 43,
by converting each disequality into a cardinality constraint
using (22). In general, we need to consider the case when
sh(u) 6= sh(u′ ) and generate another disjunct.
Elimination of disequalities might violate previously established homomorphism invariants, so we may need to
reestablish these invariants by repeating the previously described steps. The overall process terminates because we
never introduce new inequalities between term variables.
As a final step, we convert all cardinality constraints into
constraints on parameter term variables, using (25). In the
case when the shape of cardinality constraint is cs , we cannot apply (25). However, in that case the homomorphism
condition ensures that each of the participating variables is
equal to a or equal to b. This means that we can simply
evaluate the cardinality constraint in the boolean algebra
{a, b}. If the result is true we simply drop the constraint,
otherwise the entire base formula becomes false.
This completes our sketch of transforming a quantifierfree formula into disjunction of structural base formulas.

4. if hus , ts i ∈ S and us = f s (us1 , . . . , usk ) occurs in
shapeBase then {hus1 , f1s (ts )i, . . . , husk , fks (ts )i} ⊆ S;
5. if hu, ti ∈ S and sh(u) = us occurs in hom then
hus , sh(t)i ∈ S.
Definition 47 An internal term variable u is covered iff
there exists a term t such that hu, ti ∈ S. An internal shape
variable us is covered iff there exists a term ts such that
hus , ts i ∈ S.
Lemma 48 Let β be a structural base formula with matrix
β0 and let covering be the covering of β.
1. If hu, ti ∈ S then |= β0 ⇒ u = t.
2. If hus , ts i ∈ S then |= β0 ⇒ us = ts .
Proof. By induction, using Definition 46.
Corollary 49 Let β be a structural base formula such that
every internal variable is covered. Then β is equivalent to a
well-defined quantifier-free formula.
Proof. By Lemma 48 using (7).
Lemma 50 Let u be an uncovered non-parameter term
variable in a structural base formula β such that u is a source
i.e. no conjunct of form
u′ = f (u1 , . . . , u, . . . , uk )
occurs in termBase. Let β ′ be the result of dropping u from
β. Then β is equivalent to β ′ .
Proof. Let u occur in termBase in form
u = f (u1 , . . . , uk )
The only other occurrence of u in β is in hom and has the
form sh(u) = us . Because non-parameter term variables
are mapped to non-parameter shape variables, shapeBase
contains formula
us = shapified(f )(us1 , . . . , usk )

(56)

us1 , . . . , usk are such that, by
= usi occurs in hom. This
s

where
homomorphism property,
sh(ui )
means that the conjunct
sh(u) = u is a consequence of the remaining conjuncts, so it
may be omitted. After that, applying (7) yields a structural
base formula β ′ not containing u, where β ′ is equivalent to
β.
Corollary 51 Every base formula is equivalent to a base
formula without uncovered non-parameter term variables.
Proof.
If a structural base formula has an uncovered
non-parameter term variable, then it has an uncovered nonparameter term variable that is a source. By repeated application of Lemma (50) we eliminate all uncovered nonparameter term variables.

We introduce the notion of covered variables in structural
base formula by generalizing Definition 29.
Definition 46 The set covering of variable coverings of a
structural base formula β is the least set S of pairs hu, ti
where u is an internal (shape or term) variable and t is a
term over the free variables of β, such such that:

The next example illustrates how we deal with cardinality constraints |1s |s ≥ k and |1s | = k, which contain no
term variables. These constraints restrict the size of shape
s. Luckily, we can be translate them into shape base formula
constraints.

1. if x = u occurs in termBase then hu, xi ∈ S;
2. if xs = us occurs in shapeBase then hus , xs i ∈ S;

23

termBase, it occurs only in hom and cardin. Let sh(u) = us
occur in hom. Let ψ1 , . . . , ψp be all conjuncts of cardin that
contain u. Each ψi is of form |ti |us ≥ ki or |ti |us = ki for
some us -term ti . Let uj1 , . . . , ujq be all term variables appearing in ti terms other than u. Conjunct sh(ujr ) = us
occurs in hom for each r where 1 ≤ r ≤ q. The base formula
can therefore be written in form

Example 52 (Shape Term Size Constraints)
Let x < y denote conjunction x ≤ y∧x 6= y. Let us eliminate
quantifiers from formula ∃x.φ(x) where
φ(x) ≡ ¬(∃y.∃z. x < y ∧ y < z) ∧

(57)

¬(∃u. u < x)
Eliminating variables y, z from the first conjunct and variable u from the second conjunct yields

β1 ≡ ∃x1 , . . . , xe , xs1 , . . . , xsf . φ ∧ φ1
where

¬|xc |sh(x) ≥ 2 ∧ ¬|x|sh(x) ≥ 1

φ1 ≡ ∃u. sh(u) = us ∧

which is equivalent to
c

sh(uj1 ) = us ∧ . . . ∧ sh(ujq ) = us ∧

c

(|x |sh(x) = 0 ∨ |x |sh(x) = 1) ∧ |x|sh(x) = 0

ψ1 ∧ . . . ∧ ψp

and further to disjunction
c

(58)

All term variables in ψ1 , . . . , ψk range over terms of shape
us . Therefore, φ1 defines a relation in the boolean algebra
B(Jus K). This allows us to apply construction in Section 3.2.
We eliminate u from ψ1 ∧. . .∧ ψp and obtain a propositional
combination ψ0 of cardinality constraints with us -terms. φ0
does not contain variable u. We may assume that ψ0 is in
disjunctive normal form

c

(|x |sh(x) = 0 ∧ |x|sh(x) = 0) ∨ (|x |sh(x) = 1 ∧ |x|sh(x) = 0)
The first disjunct can be shown contradictory. Let us transform the second disjunct into a structural base formula. After introducing u = x and us = sh(u), we obtain
∃u, us . x = u ∧ sh(u) = us ∧ |u|us = 0 ∧ |uc |us = 1

ψ0 ≡ α1 ∨ . . . ∨ αw

Then ∃x.φ(x) is equivalent to

Let

∃u, us . sh(u) = us ∧ |u|us = 0 ∧ |uc |us = 1

φ1,i ≡ sh(uj1 ) = us ∧ . . . ∧ sh(ujq ) = us ∧ αi

Eliminating parameter term variable u yields

for 1 ≤ i ≤ w. Base formula β1 is equivalent to disjunction
of base formulas β1,i where

∃us . |1|us = 1

β1,i ≡ ∃x1 , . . . , xe , xs1 , . . . , xsf . φ ∧ φ1,i

Constraint |1|us = 1 means that the largest set in the
boolean algebra B(s) where s is the value of us has size
one. There exists exactly one boolean algebra of size one
in the structure FT2 , namely {a, b}. Therefore, |1|us = 1 is
equivalent to us = cs . We may now eliminate us by letting
us = cs . We conclude that the sentence ∃x.φ(x) is true.
Notice that we have also established that formula φ(x)
is equivalent to sh(x) = cs , as a consequence of

We have thus eliminated an uncovered parameter term variable u from β1 . By repeating this process we eliminate all
uncovered parameter term variables from a base formula.
The resulting formula contains no uncovered term variables.
It remains to eliminate uncovered shape variables. This
process is similar to term algebra quantifier elimination in
Section 3.4. An essential part of construction in Section 3.4
is Lemma 25, which relies on the fact that uncovered parameter variables may take on infinitely many values. We
therefore ensure that uncovered parameter shape variables
are not constrained by term variables through conjuncts outside shapeBase.
Suppose that us is an uncovered parameter shape variable in a base formula β. us does not occur in termBase.
us does not occur in hom either, because all term variables
are covered, and a conjunct sh(u) = us would imply that us
is covered. The only possible occurrence of us is in cardinality constraint ψ of subformula cardin, where ψ is of form
|t|us = k or of form |t|us ≥ k. Suppose there is some term
variable u occurring in t. Then sh(u) = us so us is covered,
which is a contradiction. Therefore, t has no variables. t
can thus be simplified to either 0us or 1us . In general, a constraint of form |1|us = k or |1|us ≥ k is a domain cardinality
constraint for boolean algebra B(Jus K) (see Remark 15 as
well as (20)). A constraint containing |0us | is equivalent to
true or false. A constraint |1|us = 0 is equivalent to false. A
constraint |1|us = k for k ≥ 1 is equivalent to

|1sh(x) |sh(x) = 1

The following Proposition 53 corresponds to Proposition 38.
Proposition 53 (Struct. Base to Quantifier-Free)
Every structural base formula β is equivalent to a quantifierfree formula φ in the language of Figure 5.
Proof Sketch. By Corollary 51 we may assume that β
has no uncovered non-parameter term variables. By Corollary 49 we are done if there are no uncovered variables, so
it suffices to eliminate uncovered parameter term variables
and uncovered shape variables.
Let u be an uncovered parameter term variable. Then u
does not occur in termBase. Indeed, suppose for the sake of
contradiction that u occurs in termBase in some formula
u′ = f (u1 , . . . , u, . . . , uk )

us = ts1 ∨ · · · ∨ us = tsp

Then u′ is an uncovered non-parameter variable in β, which
is a contradiction because we have assumed β has no uncovered non-parameter variables. Therefore, u does no occur in

where ts1 , . . . , tsp is the list of all ground terms in signature Σ0
that have exactly k occurrences of constant cs . We therefore
24

generate a disjunction of base formulas β1 , . . . , βp where βi
results from β by replacing |1|us = k with us = tsi . We convert each βi to a disjunction of base formulas by labelling
subterms of ti by internal shape variables and doing case
analysis on the equality between new internal shape variables to ensure the invariants of a base formula. The result
is a disjunction of base formulas where variable us occurs
only in shapeBase subformula.
Similarly, |1|us ≥ k + 1 is equivalent to ¬(|1|us = k) and
thus to
us 6= ts1 ∧ · · · ∧ us 6= tsq
(59)

Theorem 54 (Two Constants Quant. Elimination)
There exist algorithms A, B such that for a given formula
φ in the language of Figure 5:
a) A produces a quantifier-free formula φ′ in selector language
b) B produces a disjunction φ′ of structural base formulas
Proof. Analogous to proof of Theorem 39, using Proposition 45 in place of Proposition 28 and Proposition 53 in
place of Proposition 38.

where ts1 , . . . , tsq is the list of all ground terms in signature
Σ0 that have at most k occurrences of constant cs . We
replace |1|us ≥ k + 1 by (59) and again convert the result
to a disjunction of base formulas where us occurs only in
shapeBase subformula.
Each of the resulting base formulas β 1 are such that every
uncovered variable in β 1 is a shape variable that occurs only
in shapeBase. Let
β1 ≡

Corollary 55 The first-order theory of the structure FT2 is
decidable.
This completes description of our quantifier elimination
for the first-order theory of structure FT2 , which models
structural subtyping with two base types and one binary
constructor. It is straightforward to extend the construction of this section to any number of covariant constructors
if the base formula has only two constants. In Section 5 we
extend the result to any number of constants as well. Finally, in Section 6 we extend the result to allow arbitrary
decidable structures for primitive types, even if the number
of primitive types is infinite.

∃u1 , . . . , un , us1 , . . . , usps , usps +1 , . . . , usps +qs .
shapeBase(us1 , . . . , usns , xs1 , . . . , xsms ) ∧
termBase(u1 , . . . , un , x1 , . . . , xm ) ∧
hom(u1 , . . . , un , us1 , . . . , usn ) ∧
cardin(up+1 , . . . , up+q , usps +1 , . . . , usps +qs )

5
1

us1 , . . . , usps
2

where
are uncovered shape variables. Then β is
equivalent to β :
β2 ≡

A Finite Number of Constants

In this section we prove the decidability of structural subtyping of any finite number of constant symbols (primitive
types) and any number of function symbols (constructors).
We first show the result when all constructors are covariant,
we then show the result when some of the constructors are
contravariant.
We introduce the notion of Σ-term-power of some structure C as a generalization of the structure of structural subtyping.
We represent primitive types in structural subtyping as
a structure C with a finite carrier C. We call C the base
structure. Without loss of generality, we assume that C has
only relations; functions and constants are definable using
relations. Let LC be a set of relation symbols and let ≤ ∈ LC
be a distinguished binary relation symbol. ≤ represents the
subtype ordering between types. C is finite, so C is decidable
(see Section 6 for the case when C is infinite but decidable).
We represent type constructors as free operations in the
term algebra with signature Σ. To represent the variance
of constructors we define for each constructor f ∈ Σ of
arity ar(f ) = k and each argument 1 ≤ i ≤ k the value
variance(f, i) ∈ {−1, 1}. The constructor f is covariant in
argument i iff variance(f, i) = 1. For convenience we assume
ar(f ) ≥ 1 for each f ∈ Σ.
The Σ-term-power of C is a structure P defined as follows. Let Σ′ = Σ ∪ C. The domain of P is the set P of
finite ground Σ′ -terms. Elements of C are viewed as constants of arity 1. The structure P has signature Σ∪LC . The
constructors f ∈ Σ are interpreted in P as in a free term
algebra:
Jf KP (t1 , . . . , tk ) = f (t1 , . . . , tk )

∃u1 , . . . , un , usps +1 , . . . , usps +qs .
φ2 (usps +1 , . . . , usps +qs , xs1 , . . . , xsms )
termBase(u1 , . . . , un , x1 , . . . , xm ) ∧
hom(u1 , . . . , un , us1 , . . . , usn ) ∧
cardin(up+1 , . . . , up+q , usps +1 , . . . , usps +qs )

Here φ2 is a base formula (Definitions 19 and 21) whose free
variables are variables free in β 2 as well as all covered shape
variables:
φ2 (usps +1 , . . . , usps +qs , xs1 , . . . , xsms ) ≡ ∃us1 , . . . , usps .
shapeBase(us1 , . . . , usps , usps +1 , usps +qs , xs1 , . . . , xsms )
Applying Lemma 37 we conclude that φ2 is equivalent to
some disjunction
k
_
φ3,i
i=1

of base formulas without uncovered variables. Let β 3,i be the
result of replacing φ2 with φ3,i in β 2 . Then β 2 is equivalent
to
k
_
β 3,i
i=1

and each β 3,i has no uncovered variables either, because
every free variable of φ3,i is either free or covered in β 3,i .
By Corollary 49 each β 3,i can be written as a quantifier free
formula.

A relation r ∈ LC \{≤} is interpreted pointwise on the terms
of same “shape” as follows. JrKP is the least relation ρ such
that:

The following Theorem 54 corresponds to 39 of Section 3.4.

1. if JrKC (c1 , . . . , cn ) then ρ(c1 , . . . , cn )
25

2. if ρ(ti1 , . . . , tin ) for all i where 1 ≤ i ≤ k, then

8. cardinality constraint relations
J|φ(x1 , . . . , xk )|ts = kKPE (t1 , . . . , tk ) =

ρ(f (t11 , . . . , t1k ), . . . , f (tn1 , . . . , tnk ))

|Jφ(x1 , . . . , xk )KPE (t1 , . . . , tk )| = k

The relation ≤ ∈ LC is interpreted similarly, but taking into
account the variance. J≤KP is the least relation ρ such that

and
J|φ(x1 , . . . , xk )|ts ≥ kKPE (t1 , . . . , tk ) =

1. if J≤KC (c1 , c2 ) then ρ(c1 , c2 )
2. if
ρvariance(f,i) (ti1 , . . . , tin )

|Jφ(x1 , . . . , xk )KPE (t1 , . . . , tk )| ≥ k

ρ(f (t11 , . . . , t1k ), . . . , f (tn1 , . . . , tnk ))

It remains to complete the semantics of cardinality constraint relations,
by defining the set
Jφ(x1 , . . . , xk )KPE (t1 , . . . , tk ).
If s is a shape, we call
the set of positions of constant cs in s leaves of s, and
denote it by leaves(s). We represent a leaf as a sequence of
pairs hf, ii where f is a constructor of arity k and 1 ≤ i ≤ k.
If l ∈ leaves(s) and sh(t) = s, then t[l] denotes the element
c ∈ C at position l in term t i.e. if l = hf 1 , i1 i . . . hf n , in i
then
t[l] = finn (. . . fi22 (fi11 (t)) . . .)
(64)
We define:

Here we use the notation ρv for v ∈ {−1, 1} with the meaning: ρ1 = ρ and ρ−1 = {hy, xi | hx, yi ∈ ρ}.
We next sketch the decidability of structural subtyping
for any finite number of primitive types C. For now we assume that all constructors f ∈ Σ are covariant, the relation
≤ thus does not play a special role.
Extended Term-Power Structure

For the purpose of quantifier elimination we define the structure PE by extending the domain and the set of operations
of the term-power structure P.
The domain of PE is PE = P ∪ PS where PS is the set
of shapes defined as follows. Let Σs = {cs } ∪ {f s | f ∈ Σ}
be a set of function symbols such that cs is a fresh constant
symbol with ar(cs ) = 0 and f s are fresh distinct constant
symbols with ar(f s ) = ar(f ) for each f ∈ Σ. The set of
shapes PS is the set of ground Σs -terms. When referring to
elements of PE by term we mean an element of P ; by shape
we mean an element of PS . We write X s to denote an entity
pertaining to shapes as opposed to terms, so xs , us denote
variables ranging over shapes, and ts to denotes terms that
evaluate to shapes.
The extended structure PE contains term algebra operations on terms and shapes (including selector operations and
tests, [22, Page 61]), the homomorphism sh, and cardinality
constraint relations |φ|ts = k and |φ|ts ≥ k:

Jφ(x1 , . . . , xk )KPE (t1 , . . . , tk ) =
{l | Jφ(x1 , . . . , xk )KC (t1 [l], . . . , tk [l])}

shapified(f )(JshKPE (t1 ), . . . , JshKPE (tn ))

|Jφ(x1 , . . . , xk )KPE (c1 , . . . , ck )| =
(
1, Jφ(x1 , . . . , xk )KC (c1 , . . . , ck )
0,

shapified(f )

=

cs ,

if x ∈ C

s

if f ∈ Σ

f ,

(66)

C

¬Jφ(x1 , . . . , xk )K (c1 , . . . , ck )

|Jφ(x1 , . . . , xk )KPE (f (t11 , . . . , t1l ), . . . , f (tk1 , . . . , tkl ))|
= |Jφ(x1 , . . . , xk )KPE (t11 , . . . , tk1 )| + . . .
+ |Jφ(x1 , . . . , xk )KPE (t1l , . . . , tkl )|
(67)
Definition (65) generalizes [14, Definition 2.1, Page 63].
We write |φ(t1 , . . . , tk )|ts = k as a shorthand for the
atomic formula (|φ(x1 , . . . , xk )|ts = k)(t1 , . . . , tk ), similarly
for |φ(t1 , . . . , tk )|ts ≥ k. This is more than a notational convenience, see Section 6 for an approach which introduces sets
of leaves as elements of the domain of PE and defines a cylindric algebra interpreted over sets of leaves. The approach in
this section follows [35] in merging the quantifier elimination
for products and quantifier elimination for boolean algebras.
Some of the operations in PE are partial. We use the
definitions and results of Section 2.3 to deal with partial
functions. fi (t) is defined iff Isf (t) holds, fis (ts ) is defined
iff Isf s (ts ) holds. Cardinality constraints |φ(t1 , . . . , tk )|ts =
k and |φ(t1 , . . . , tk )|ts ≥ k are defined iff sh(t1 ) = . . . =
sh(tk ) = ts holds.
The structure PE is at least as expressive as P because
the only operations or relations present in P but not in PE
are JrKP for r ∈ LC , and we can express JrKP (t1 , . . . , tk ) as
|¬ r(t1 , . . . , tk )|sh(t1 ) = 0.
Our goal is to give a quantifier elimination for first-order
formulas of structure PE . By a quantifier-free formula we
mean a formula without quantifiers outside cardinality constraints, e.g. the formula |∀x.x ≤ t|xs = k is quantifier-free.

(60)

where
shapified(x) =

(65)

The following equations follow from (65) and can be used as
an equivalent alternative definition for cardinality relations:

1. constructors in the term algebra of terms, f ∈ Σ′
Jf KPE (t1 , . . . , tk ) = f (t1 , . . . , tk );
2. selectors in term the algebra of terms,
Jfi KPE (f (t1 , . . . , tk )) = ti ;
3. constructor tests in the term algebra of terms,
JIsf KPE (t) = ∃t1 , . . . , tk . t = f (t1 , . . . , tk );
4. constructors in the term algebra of shapes, f s ∈ Σs
Jf s KPE (ts1 , . . . , tsk ) = f s (ts1 , . . . , tsk );
5. selectors in the term algebra of shapes,
Jfis KPE (f s (ts1 , . . . , tsk )) = tsi ;
6. constructor tests in the term algebra of shapes,
JIsf s KPE (ts ) = ∃ts1 , . . . , tsk . ts = f s (ts1 , . . . , tsk );
7. the homomorphism mapping terms to shapes such
that:
JshKPE (f (t1 , . . . , tn )) =

(63)

where φ(x1 , . . . , xk ) is is a first-order formula over the
base-structure language LC with free variables
x1 , . . . , xk , term ts denotes a shape, and k is a
nonnegative integer constant.

for all i where 1 ≤ i ≤ k, then

5.1

(62)

(61)

26

5.2

Structural Base Formulas

a parameter variable iff its shape is a parameter shape
variable).

In this section we define the notion of structural base formulas for any base structure C with a finite carrier.
Definition 56 of structural base formula for quantifier
elimination in PE differs from Definition 41 in the conjuncts
of cardin subformula. Instead of cardinality constraints on
boolean algebra terms, Definition 56 contains cardinality
constraints on first-order formulas.
The notion of base formula and Lemma 25 apply to terms
P as well as shapes PS in the structure PE because shapes
are also terms over the alphabet Σs . For brevity we write u∗
for an internal shape or term variable, and similarly x∗ for
a free shape or term variable, t∗ for terms, f ∗ for term or
shape term algebra constructor and fi∗ for a term or shape
term algebra selector.

cardin(up+1 , . . . , un , usps +1 , . . . , usns ) = ψ1 ∧ · · · ∧ ψd
where each ψi is a cardinality constraint of the form
|φ(uj1 , . . . , ujl )|us = k
or
|φ(uj1 , . . . , ujl )|us ≥ k
where {j1 , . . . , jl } ⊆ {p + 1, . . . , n} and the conjunct
sh(ujd ) = us occurs in termHom for 1 ≤ d ≤ l. We require
each structural base formula to satisfy the following
conditions:
P0) the graph associated with shape base formula

Definition 56 (Structural Base Formula)
A structural base formula with:
•
•
•
•
•
•

∃us1 , . . . , usns . shapeBase(us1 , . . . , usns , xs1 , . . . , xsms )

free term variables x1 , . . . , xm ;
internal non-parameter term variables u1 , . . . , up ;
internal parameter term variables up+1 , . . . , up+q ;
free shape variables xs1 , . . . , xsms ;
internal non-parameter shape variables us1 , . . . , usps ;
internal parameter shape variables usps , . . . , usps +qs

is acyclic;
P1) congruence closure property for shapeBase subformula:
there are no two distinct variables usi and usj such that
both usi = f (usl1 , . . . , uslk ) and usj = f (usl1 , . . . , uslk )
occur as conjuncts in formula shapeBase;

is a formula of the form:

P2) congruence closure property for termBase subformula:
there are no two distinct variables ui and uj such that
both ui = f (ul1 , . . . , ulk ) and uj = f (ul1 , . . . , ulk )
occur as conjuncts in formula termBase;

∃u1 , . . . , un , us1 , . . . , usns .
shapeBase(us1 , . . . , usns , xs1 , . . . , xsms ) ∧
termBase(u1 , . . . , un , x1 , . . . , xm ) ∧
termHom(u1 , . . . , un , us1 , . . . , usns )

P3) homomorphism property of sh: for every
non-parameter term variable u such that
u = f (ui1 , . . . , uik ) occurs in termBase, if conjunct
sh(u) = us occurs in termHom, then for some shape
variables usj1 , . . . , usjk term us = f s (usj1 , . . . , usjk )
occurs in shapeBase where f s = shapified(f ) and for
every r where 1 ≤ r ≤ k, conjunct sh(uir ) = usjr
occurs in termHom.

∧

cardin(up+1 , . . . , un , usps +1 , . . . , usns )
where n = p + q, ns = ps + q s , and formulas shapeBase,
termBase, termHom, cardin are defined as follows.
shapeBase(us1 , . . . , usns , xs1 , . . . , xsms ) =
s

p
V

usi = ti (us1 , . . . , usns ) ∧

i=1

∧ distinct(us1 , . . . , usn )

m
Vs

Note that the validity of the occur check for term variables
follows from P0) and P3). Another immediate consequence
of Definition 56 is the following Proposition 57.

xsi = usji

i=1

Proposition 57 (Quantification of Str. Base Form.)
If β is a structural base formula and x a free shape or term
variable in β, then there exists a base structural formula β1
equivalent to ∃x.β.

where each ti is a shape term of the form f s (usi1 , . . . , usik )
for some f ∈ Σ0 , k = ar(f ), and
j : {1, . . . , ms } → {1, . . . , ns } is a function mapping indices
of free shape variables to indices of internal shape variables.

We proceed to show that a quantifier-free formula can be
written as a disjunction of base formulas, and a base formula
can be written as a quantifier-free formula.

termBase(u1 , . . . , un , x1 , . . . , xm ) =
p
V

ui = ti (u1 , . . . , un ) ∧

i=1

m
V

xi = uji

i=1

5.3

where each ti is a term of the form f (ui1 , . . . , uik ) for
some f ∈ Σ, k = ar(f ), and j : {1, . . . , m} → {1, . . . , n} is
a function mapping indices of free term variables to indices
of internal term variables.
termHom(u1 , . . . , un , us1 , . . . , usns ) =

n
V

i=1

Conversion to Base Formulas

Conversion from a quantifier-free formula to the structural
base formula is given by Proposition 57. The proof of Proposition 58 is analogous to the proof of Proposition 45 but uses
of (67) instead of (25).
Proposition 58 (Quantifier-Free to Structural Base)
Every well-defined quantifier-free formula φ is equivalent
on PE to true, false, or some disjunction of structural base
formulas.

sh(ui ) = usji

where j : {1, . . . , n} → {1, . . . , ns } is some function such
that {j1 , . . . , jp } ⊆ {1, . . . , ps } and
{jp+1 , . . . , jp+q } ⊆ {ps + 1, . . . , ps + q s } (a term variable is
27

5.4

Conversion to Quantifier-Free Formulas

Lemma 65 Let
α ≡ ∃u. sh(u) = us ∧

The conversion from structural base formulas to quantifierfree formulas is similar to the case of two constant symbols
in Section 4.3, but requires the use of Feferman-Vaught technique.

sh(u1 ) = us ∧ . . . ∧ sh(uk ) = us ∧

(69)

ψ1 ∧ . . . ∧ ψp

Definition 59 The set dets of variable determinations of a
structural base formula β is the least set S of pairs hu∗ , t∗ i
where u∗ is an internal term or shape variable and t∗ is a
term over the free variables of β, such such that:

where each ψi is a cardinality constraint of the form |φ|us =
k or |φ|us ≥ k where all free variables of φ are among
u, u1 , . . . , uk . Then there exists formula ψ such that ψ
is a disjunction of conjunctions of cardinality constraints
|φ′ | = k and |φ′ | ≥ k where the free variables in each φ′ are
among u1 , . . . , uk and formula α is equivalent on PE to α′
where

1. if x∗ = u∗ occurs in termBase or shapeBase, then
hu∗ , x∗ i ∈ S;
2. if hu∗ , t∗ i ∈ S and u∗ = f ∗ (u∗1 , . . . , u∗k ) occurs in
shapeBase or termBase then
{hu∗1 , f1∗ (t∗ )i, . . . , hu∗k , fk∗ (t∗ )i} ⊆ S;

α′ ≡ sh(u1 ) = us ∧ . . . ∧ sh(uk ) = us ∧ ψ

(70)

3. if {hu∗1 , f1∗ (t∗ )i, . . . , hu∗k , fk∗ (t∗ )i} ⊆ S and
u∗ = f ∗ (u∗1 , . . . , u∗k ) occurs in shapeBase or termBase
then hu∗ , t∗ i ∈ S;

Proposition 66 (Struct. Base to Quantifier-Free)
Every structural base formula β is equivalent on PE to
some well-defined quantifier-free formula φ.

4. if hu, ti ∈ S and sh(u) = us occurs in termHom then
hus , sh(t)i ∈ S.

Proof Sketch. By Corollary 64 we may assume that β has
no undetermined non-parameter term variables. By Corollary 62 we are done if there are no undetermined variables,
so it suffices to eliminate undetermined parameter term variables and undetermined shape variables.
Let u be an undetermined parameter term variable. u
does not occur in termBase because it cannot have a successor or a predecessors in the graph associated with term base
formula. Therefore, u′ occurs only in termHom and cardin.
Let us be the shape variable such that us = sh(u) occurs
in termHom. Let ψ1 , . . . , ψp be all conjuncts of cardin that
contain u.
Each ψi is of the form |φ|us ≥ ki or |φ|us = ki and for
each variable u′ free in φ the conjunct sh(u) = us occurs
in termHom. The base formula can therefore be written in
form
β1 ≡ ∃x1 , . . . , xe , xs1 , . . . , xsf . φ ∧ α

Definition 60 An internal variable u∗ is determined if
hu∗ , t∗ i ∈ dets for some term ts . An internal variable is
undetermined if it is not determined.
Lemma 61 Let β be a structural base formula with matrix
β0 and let dets be the determinations of β. If hu∗ , t∗ i ∈ S
then |= β0 ⇒ u∗ = t∗ .
Corollary 62 Let β be a structural base formula such that
every internal variable is determined. Then β is equivalent
to a well-defined quantifier-free formula.
Proof. By Lemma 61 using
∃x.x = t ∧ φ(x) ⇐⇒ φ(t)

(68)

where α has the form as in Lemma
W 65. Applying Lemma 65
we eliminate u and obtain ψ = w
i=1 αi where and each αi is
a conjunction of cardinality constraints.
Base formula β1 is
W
β
thus equivalent to the disjunction w
i=1 1,i where each β1,i
is a base formula

Lemma 63 Let u be an undetermined non-parameter term
variable in a structural base formula β such that u is a source
i.e. no conjunct of the form
u′ = f (u1 , . . . , u, . . . , uk )

β1,i ≡ ∃x1 , . . . , xe , xs1 , . . . , xsf . φ ∧ φ1,i

′

occurs in termBase. Let β be the result of removing u and
conjuncts containing u from β. Then β is equivalent to β ′ .

By repeating this process we eliminate all undetermined parameter term variables from a base formula. Each of the
resulting base formulas contains no undetermined term variables.
It remains to eliminate undetermined shape variables.
This process is similar to term algebra quantifier elimination; the key ingredient is Lemma 25, which relies on
the fact that undetermined parameter variables may take
on infinitely many values. We therefore ensure that undetermined parameter shape variables are not constrained
by term and parameter variables through conjuncts outside
shapeBase.
Consider an undetermined parameter shape variable us .
us does not occur in termHom, because all term variables
are determined and a conjunct us = sh(u) would imply that
us is determined as well. us can thus occur only in cardin
within some cardinality constraint |φ|us = k or |φ|us ≥ k.
Moreover, formula φ in each such cardinality constraint is
closed: otherwise φ would contain some free variable u, by

Proof. The conjunct containing u in termHom is a consequence of the remaining conjuncts, so we drop it. We then
apply (68).
Corollary 64 Every base formula is equivalent to a base
formula without undetermined non-parameter term variables.
Proof.
If a structural base formula has an undetermined non-parameter term variable, then it has an undetermined non-parameter term variable that is a source. Repeatedly apply Lemma 63 to eliminate all undetermined
non-parameter term variables.
The following Lemma 65 is a consequence of the fact that
terms of a fixed shape s form a substructure of P isomorphic
to the finite power C m where m = |leaves(s)| and follows
from Feferman-Vaught theorem in Section 3.3.
28

definition of base formula u would have to be a parameter variable, all parameter term variables are determined,
so us would be determined as well. Let us denote some
shape s. Because φ is a closed formula, |φ| is equal to
0 if JφKC = false and to the shape size m = |leaves(s)| if
JφKC = true. (The fact that closed formulas reduce to the
constraints on domain size appears in [35, Theorem 3.36,
Page 13].) After eliminating constraints equivalent to 0 = k
and 0 ≥ k, we obtain a conjunction of simple linear constraints of the form m = k and m ≥ k. These constraints
specify a finite or infinite set S ⊆ {0, 1, . . .} of possible sizes
m. Let A = {s | |leaves(s)| ∈ S}. If the set S is infinite
then it contains an infinite interval of form {m0 , m0 + 1, . . .}
so the set A is infinite. If Σ contains a unary constructor and S is nonempty, then A is infinite. If Σ contains
no unary constructors and S is finite then A is finite and
the cardinality constraints containing us are equivalent to
W
p
s
s
s
s
i=1 u = ti where A = {t1 , . . . , tp }. We therefore generate a disjunction of base formulas β1 , . . . , βp where βi results from β by replacing cardinality constraints containing
us with with us = tsi . We convert each βi to a disjunction
of base formulas by labelling subterms of ti with internal
shape variables and doing case analysis on the equality between new internal shape variables to ensure the invariants
of a base formula, as in the proof of 58. By repeating this
process for all shape variables us where the set S is finite,
we obtain base formulas where the set A is infinite for every
undetermined parameter shape variable us . We may then
eliminate all undetermined parameter and non-parameter
shape variables along with the conjuncts that contain them.
The result is an equivalent formula by Lemma 25.
All variables in each of the resulting base formulas are
determined. By Corollary 62 each formula can be written
as a quantifier-free formula, and the resulting disjunction is
a quantifier-free formula.
5.5

We clearly have for every formula φ and every valuation σ:
Jφ(−1) KC = JφKC

n
Y

Jφ(x1 , . . . , xk )KPE (t1 , . . . , tk ) =
′

{l | Jφ(x1 , . . . , xk )KC (t1 [l], . . . , tk [l])}

= t2 ≤ t1

(φ1 ∧ φ2 )

= φ1 (−1) ∧ φ2 (−1)

(φ1 ∨ φ2 )(−1)

= φ1 (−1) ∧ φ2 (−1)

(¬φ)(−1)

= ¬φ(−1)

(∃t.φ)(−1)

= ∃t.φ(−1)

(∀t.φ)(−1)

= ∀t.φ(−1)

= (J≤KC )−1

|{l ∈ leaves(s) | variance(l) = 1}|

N (s)

|{l ∈ leaves(s) | variance(l) = −1}|

=

(76)

|Jφ(x1 , . . . , xk )KPE (f (t11 , . . . , t1l ), . . . , f (tk1 , . . . , tkl ))|
P
= li=1 |Jφ(variance(f,l)) (x1 , . . . , xk )KPE (t1i , . . . , tki )|
(77)
The only change in the proof of Proposition 58 is the use
of (77) instead of (67). Most of the proof of Proposition 66
remains unchanged as well; the only additional difficulty is
eliminating constraints of the form |φ|us = k and |φ|us ≥ k
where us is a parameter shape variable and φ is a closed
formula. Lemma 68 below addresses this problem.
We say that an algorithm g finitely computes some function f : A → 2B where B is an infinite set iff g is a function
from A to the set Fin(B) ∪ {∞} where Fin(B) is the set of
finite subsets of set B, ∞ is a fresh symbol, and
(
f (a), if f (a) ∈ Fin(B)
(78)
g(a) =
∞, if f (a) ∈
/ Fin(B)
Lemma 68 There exists an algorithm
V that, given a shape
variable us and a conjunction ψ ≡ n
i=1 ψi of cardinality
constraints where each ψi is of form |φi |us = ki or |φi |us ≥ ki
for some closed formula φi , finitely computes the set
A = {s | JψKP [us 7→ s]}

(79)

of shapes which satisfy ψ in P.
Proof Sketch. Let φ be a closed formula in language LC .
Compute JφKC and Jφ(−1) KC and then replace |φ|s with one
of the expressions P (s) + N (s), P (s), N (s), 0 according to
the following table.

Define C −1 to have the same domain and same interpretation
of operations and relations r ∈ LC \ {≤} but where
−1

P (s) =

Because of this isomorphism, Lemma 65 still holds and we
may still use Feferman-Vaught theorem from Section 3.3.
Equation (67) generalizes to:

(71)

J≤KC

(75)

where C ′ denotes C for variancel = 1 and C −1 for variancel −
1. Hence, isomorhism between terms of some fixed shape
s with |leaves(s)| = m and C m breaks, but there is still an
isomorphism with C P (s) × (C −1 )N(s) where

= r(t1 , . . . , tk ), if r ∈ LC \ {≤}

(−1)

(74)

We generalize (65) to

Definition 67 If φ is a first-order formula in the language
LC the contravariant version of φ, denoted φ(−1) , is defined
by induction on the structure of formula by:

(t1 ≤ t2 )

variance(f j , ij )

j=1

So far we have assumed that all constructors are covariant.
In this section we describe the changes needed to extend
the result to the case when the constructors have arbitrary
variance with respect to some distinguished binary relation
denoted ≤.

(−1)

(73)

If l ∈ leaves(s) is a leaf l = hf 1 , i1 i . . . hf n , in i, define
variance(l) as the product of integers

One-Relation-Symbol Variance

(r(t1 , . . . , tk ))(−1)

−1

(72)
29

JφKC
true

Jφ(−1) KC
true

|φ|s =
P (s) + N (s)

true

false

P (s)

false

true

N (s)

false

false

0

(80)

Let

The constraints of the form N (s) + P (s) = k and N (s) +
P (s) = k can be expressed as propositional combinations of
constraints of the form N (s) = k, P (s) = k, P (s) ≥ k and
N (s) ≥ k. Therefore, ψ can be written as a propositional
combination of these four kinds of constraints and each conjunction C(s) can further be assumed to have one of the
forms:
F2) CkP ,k+ (s) ≡ P (s) = kP ∧ N (s) ≥ kN ;
N

F3) Ck+ ,kN (s) ≡ P (s) ≥ kP ∧ N (s) = kN ;
P

Ti

= {hp, ni ∈ U | n = i}

p1 + · · · + pl + nl+1 + . . . + nk = i

F4) Ck+ ,k+ (s) ≡ P (s) ≥ kP ∧ N (s) ≥ kN .
N

(85)

(86)

for nonnegative integers p1 , . . . , pl , nl+1 , . . . , nk . First consider solution solutions where no variable is equal to i. If for
one of the solutions, one of the sets Sp1 , . . . , Spl is infinite,
then Si is infinite, otherwise add to Si all elements hi, ni
where
n = n1 + · · · + nl + pl+1 + . . . + pk
(87)
If n ≤ kP then also add the same elements hi, ni to Tn .
Next, proceed analogously with Ti , considering solutions of

Let A = {s ∈ PS | C(s)}. To compute A when Σ contains
unary constructors, we first restrict Σ to the language Σ′
with no unary constructors, and compute the set A′ ⊆ A
using language Σ′ . If A′ is empty, so is A, otherwise A is
infinite. Assume that Σ contains no unary constructors. Assume further Σ contains at least one binary constructor and
at lest one constructor is contravariant in some argument.
Let
S = {hP (s), N (s)i | s ∈ A}

n1 + · · · + nl + pl+1 + . . . + pk = i

Because P (s) + N (s) = |leaves(s)| and there are only finitely
many shapes of any given size (every constructor is of arity
at least two), it suffices to finitely compute S. S can be
given an alternative characterization as follows. If f ∈ Σ,
ar(f ) = k, f is covariant in l arguments and contravariant
in k−l arguments define
Jf KS (hp1 , n1 i, . . . , hpk , nk i) =
P
P
P
P
h li=1 pi + ki=l+1 ni , li=1 ni + ki=l+1 pi i

= {hp, ni ∈ U | p = i}

To finitely compute S, finitely compute the sets Si and Ti
for 0 ≤ i ≤ kP . The algorithm starts with all sets Si and Ti
empty and keeps adding elements according to operations
Jf KS .
Assume that S0 , T0 , . . . , Si−1 , Ti−1 are finitely computed.
The computation of Si and Ti proceeds as follows. Let f ∈ Σ
be a constructor of arity k with l covariant arguments. For
Si we consider all solutions of the equation

F1) CkP ,kN (s) ≡ P (s) = kP ∧ N (s) = kN ;

P

Si

(88)

If at this point Si is not infinite and not empty, then also
consider the solutions of (87) where pj = i for some j. If
such solution exists, then mark Si as infinite. Proceed analogously with Ti . Finally, if both Si and Ti are still finite
but there exists a solution for Si where nl+j = i for some j
and exists a solution for Tj where pl+d = i for some d, then
mark both Si and Ti as infinite. This completes the sketch
of one step of the computation. (This step also applies to
S0 and T0 ; we initially assume that h1, 0i ∈ T0 .)

(81)

Let U be the subset of {hp, ni | p, n ≥ 0} generated from
element h1, 0i using operations Jf KS for f ∈ Σ. Then

Example 69 Let us apply this algorithm to the special case
where Σ = {f, g} and

S = {hp, ni ∈ U | c(p, n)}

variance(g) = h1, 1i

(82)

variance(f ) = h−1, 1i
Let us see what the set S looks like. If hx, yi ∈ S define
khx, yi = hkx, kyi as in a vector space.
First, h1, 0i ∈ S because of cs . Next h1, 1i ∈ S because
of f s and h2, 0i ∈ S because of g s .
More generally, we have the following composition rule:
If hp1 , n1 i, hp2 , n2 i then

where c(p, n) is the linear constraint corresponding to the
constraint C(s).
Let C(s) = CkP ,kN (s). Then S ⊆ {hp, ni | p + n =
kP + kN }. S is therefore a subset of a finite set and is easily
computable, which solves case F1).
Let C(s) = Ck+ ,k+ (s). Because Σ contains a binary conN
P
structor, S contains pairs hp, ni with arbitrarily large p+n,
so either the p components or n component of elements of
S grows unboundedly. Because Σ contains a constructor f
contravariant in some argument, we can define using f an
operation o acting as a constructor covariant in at least one
argument and contravariant in at least one argument. Using
operation on tuples whose one component grows unboundedly yields tuples whose both components grow unboundedly. Therefore, S is infinite, which solves case F4).
Finally, consider the case C(s) = CkP ,k+ (s) (this will
N
solve the case C(s) = Ck+ ,kN (s) as well). Observe that

hp1 + p2 , n1 + n2 i ∈ S
s

because of g , and
hn1 + p2 , p1 + n2 i ∈ S
s

because of f .
Using g s we obtain all pairs hp, 0i for p ≥ 1. Using f s
once on those we obtain h1, ni for n ≥ 0. Adding these we
additionally obtain hp, ni for p ≥ 2 and n ≥ 0. Hence we
have all pairs hp, ni for p ≥ 1 and n ≥ 0 and those are the
only ones that can be obtained. Thus,

P

kP −1

CkP ,k+ (s) = CkP ,0+ (s) ∧
N

^

¬CkP ,i (s)

S = {hp, ni | p ≥ 1 ∧ n ≥ 0}

(83)

i=0

As expected, the case F1) yields a finite and the case F4)
an infinite set. The case F2) for kP = 0 is an empty set,
otherwise it is an infinite set. The case F3) always yields
an infinite set. This solves the problem for two constructors
f, g.

Because the set S for each CkP ,i (s) is finite, it suffices to
finitely compute S for CkP ,0+ (s). In that case
S = {hp, ni ∈ U | p = kP }

(84)
30

we obtain the theory in Section 4. When R = {r} where r is
a partial order on types, we obtain the theory of structural
subtyping of non-recursive covariant types. For arbitrary
relational structure C, if f ∈ Σ for ar(f ) = k we obtain a
structure that properly contains the k-th strong power of
structure C, in the terminology of [35].
The structure of this section follows Sections 4. We also
associate a boolean algebra of sets with each term t. However, in this case, the elements of the associated boolean
algebra are sets of occurrences of the constants that satisfy the given first-order formula interpreted over C. The
occurrences of constants within the terms of a given shape
correspond to the indices of the product structure in Section 3.3. We call these occurrences leaves, because they can
be represented as leaves of the tree corresponding to a term.

lifted relations r ′ for r ∈ LC
r′

::

termk → bool

term algebra on terms
constructors, f ∈ Σ:
f

::

termk → term

constructor test, f ∈ Σ:
Isf

::

term → bool

selectors, f ∈ Σ:
fi

::

term → term

6.1

Figure 8: Basic Operations of Σ-term-power Structure

In this section we define the notions shape and leafset, and
state some properties that we use in the sequel.
Let
Σ0 = {cs } ∪ {f s | f ∈ Σ}


Lemma 68 allows to carry our the proof of Proposition 66
so we obtain our main result for finite C.

be a set of function symbols such that cs is a fresh constant
symbol with ar(cs ) = 0 and f s are fresh distinct constant
symbols with ar(f s ) = ar(f ) for each f ∈ Σ. Let shapified :
Σ′ → Σ0 be defined by

Theorem 70 (Term Power Quant. Elimination)
There exists an algorithm that for a given well-defined
formula φ produces a quantifier-free formula φ′ that is
equivalent to φ on PE .

shapified(x) = cs ,

if x ∈ C

s

if f ∈ Σ

shapified(f )

Corollary 71 (Decidability of Structural Subtyping)
Let C be a structure with a finite carrier and P a Σ-termpower of C. Then the first-order theory of P is decidable.
6

Product Theory of Terms of a Given Shape

= f ,

Let FT(Σ0 ) be the set of ground terms with signature Σ0
and FT(Σ′ ) the set of ground terms of signature Σ′ .
Define function sh :: FT(Σ′ ) → FT(Σ0 ) mapping each
term to its shape by

Term-Powers of Decidable Theories

In this section we extend the result of Section 5 on decidability of term-powers of a base structure C to allow C to be an
arbitrary decidable theory, even if the carrier C is infinite.
To keep a finite language in the case when C is infinite,
we introduce a predicate IsPRI that allows testing whether
t ∈ C for a term t ∈ P .
In structural base formulas, we now distinguish between
1) composed variables, denoting elements t ∈ P for which
Isf (t) holds for some constructor f ∈ Σ, and 2) primitive
variables, denoting elements t ∈ P for which IsPRI (t) holds.
Another generalization compared to Section 5 is the use
of a syntactically richer language for term power algebras; to
some extent this richer language can be viewed as syntactic
sugar and can be simplified away.
The generalization to infinitely many primitive types and
the generalization to a richer language are orthogonal.
For most of the section we focus on covariant constructors, Section 6.5 discusses a generalized notion of variance.
As in Section 3.3 let C = hC, Ri be a decidable structure
where C is a non-empty set and R is a set of relations interpreting some relational language LC , such that each r ∈ R
is a relation of arity ar(r) on set C, i.e. r ⊆ C ar(r) . We
assume that R contains a binary relation symbol r = ∈ R,
interpreted as equality on the set C.
Operations and relations of the Σ-term-power structure
are summarized in Figure 8. We will show the decidability of
the first-order theory of the structure with these operations.
In the special case when C = {a, b} and

sh(f (t1 , . . . , tn )) = shapified(f )(sh(t1 ), . . . , sh(tn ))
for each f ∈ Σ′ . Define t1 ∼ t2 iff sh(t1 ) = sh(t2 ).
Let t be a term or shape and t′ the tree representing t as
in Section 2.2. If p is a path such that t′ (p) is defined and
denotes a constant, we write t[p] to denote t′ (p) and call p a
leaf. Note that t[p] is defined iff sh(t)[p] is defined. On the
set of equivalent terms leaves act as indices of Section 3.3. If
s is a shape, let leaves(s) denote the set of all leaves defined
on shape s.
Generalizing tCont of Section 4.1, define function tCont :
FT(Σ′ ) → C ∗ by:
tCont(c)

= cs , if c ∈ C

tCont(f (t1 , . . . , tk )) = tCont(t1 ) · . . . · tCont(tk )
Define δ(t) = hsh(t), tCont(t)i and
B = {hs, wi | s ∈ FT(Σ0 ), w ∈ C ∗ , tLen(s) = sLen(w)}
If all constructors f ∈ Σ are covariant then δ is a bijection
between FT(Σ′ ) and B. Let
B(s0 ) = {hs, wi ∈ B | s = s0 }
For a fixed s0 , the set B(s0 ) is isomorphic to the power
structure C n where n = tLen(s).
For each shape s we introduce operations from Section 3.3. To distinguish the sets of positions belonging to
different shapes, we tag each set of positions L with a shape

r = {ha, ai, ha, bi, hb, bi}
31

s. We call the pair hs, Li a leafset. The interpretation of
each relation r ∈ LC is the leafset:

6.2

To show the decidability of the first-order theory of the
structure FT∗ with operations in Figure 8, we show decidability for a richer structure. Figure 9 shows the operations
and relations of this richer structure.
The structure has four sorts: bool representing truth values, term representing terms, shape representing shapes, and
leafset representing sets of leaves within a given shape. The
structure can be seen as as a combination of the operations
of Figure 5 and Figure 2.
For each relation symbol r ∈ R we define a relation symbol r ∗ of sort shape × termk → bool acting on terms of the
same shape. While in Section 4.2 we associate a boolean
algebra with the terms of same shape, in this section we
associate a cylindric algebra [21] with terms of the same
shape. This is a particularly simple cylindric algebra resulting from lifting first-order logic on the base structure
C so that elements are replaced by terms of a given shape
(which are isomorphic to functions from leaves to elements),
and boolean values are replaced by sets of leaves (isomorphic to functions from leaves to booleans). In both cases,
operations on the set X are lifted to operations on the set
leaves(s) → X. Syntactically, we introduce a copy of all
propositional connectives and quantifiers: ∧I , ∨I , ¬I , trueI ,
falseI . Like boolean algebra operations in Figure 5, these
syntactic constructs in Figure 9 take an additional shape
argument, because term-power algebra contains one copy of
a strong power C n of base structure for each shape. We call
formulas built using the operations of the cylindric algebra
inner formulas.
For each operation in Figure 2 there is an operation in
Figure 9, potentially taking a shape as an additional argument (for operations used to build inner formulas). The logic
further contains term algebra operations on terms, leafsets,
and shapes.
We use undecorated identifiers (e.g. u) to denote variables of term sort, variables with superscript S to denote
shape variables (e.g. us ) and variables with superscript L to
denote leafset variables (e.g. uL ).
Figures 10 and 11 show the semantics of logic in Figure 9. The first row specifies semantics of operations in the
case when all arguments are defined and are in the domain
of the operation. The domain of each operation is in the
second column, it is omitted if it is equal to the entire domain resulting from interpreting the sort of the operation.
All operations except for plain logical operations and quantifiers over the bool domain are strict. Logical operations
and quantifiers over the bool domain are defined as in the
three-valued logic of Section 2.3.
We remark that values of leafset act as terms with two
constants in Figure 5. In fact, if the base structure C has
only two constants then the formula x = a and its propositional combinations are sufficient to express all facts about
C, so in that case there is no need to distinguish between
terms and leafsets.

Jrs K(t1 , . . . , tk ) = hs, {p | JrKC (t1 [p], . . . , tk [p])}i
We let ∧Is , ∨Is , ¬Is , trueIs , falseIs stand for intersection, union,
complement, full set and empty set in the algebra of subsets
of the set leaves(s). We also introduce ∃Is as the union of a
family of subsets indexed by a term of shape s and ∀Is as the
intersection of a family of subsets indexed by a term.
We use constructor-selector language for the term algebra on terms. We introduce constructor-selector language
on shapes by generalizing operations in Section 4.1 in a natural way. In addition, we introduce a constructor-selector
language on leafsets. For each f ∈ Σ we introduce a constructor symbol f L on leafsets and define
leafified(f ) = f L
Constructors f L act on leafsets as follows. If Li ⊆ leaves(si )
for 1 ≤ i ≤ k define
f L (hs1 , L1 i, . . . , hsk , Lk i) = hs, Li
where s = f s (s1 , . . . , sk ), and L ⊆ leaves(s) is given by
L = ({1} · L1 ) ∪ · · · ∪ ({k} · Lk )
(Here we define A · B = {a · b | a ∈ A ∧ b ∈ B}.)
We define selector functions on leafsets as follows. If s =
f s (s1 , . . . , sk ) and L ⊆ leaves(s), then fiL (hs, Li) = hsi , Li i
where Li ⊆ leaves(si ) is defined by
Li = {w | w · i ∈ A}
Equivalently, we require that
fiL (f L (hs1 , L1 i, . . . , hsn , Ln i)) = hsi , Li i
We can now express relations r ′ in Figure 8 using the fact:
r ′ (t1 , . . . , tk ) ⇐⇒
sh(t2 ) = sh(t1 ) ∧ . . . ∧ sh(tk ) = sh(t1 ) ∧
rsh(t1 ) (t1 , . . . , tk ) =

(89)

trueIsh(t1 )

To handle an infinite number of elements of the base
structure C, we do not introduce into the language constants
for every element of C as in Section 5. Instead, we introduce
the predicate IsPRI :: term → bool called primitive-term test
that checks whether a term is a constant:
IsPRI (x) = (x ∈ C)
and the predicate IsPRIL :: leafset → bool called primitiveleafset test:
IsPRIL (hs, Li) = (s = cs )
Instead of the rule (16), we have for f, g ∈ Σ ∪ {PRI}:
W
∀x.
Isf (x)
f ∈Σ∪{PRI}

∀x. ¬(Isf (x) ∧ Isg (x)),

(90)

for f 6≡ g

Analogous rules hold for term algebra of leafsets:
W
∀x.
Isf L (x)
f ∈Σ∪{PRI}

∀x. ¬(Isf L (x) ∧ IsgL (x)),

A Logic for Term-Power Algebras

6.3

Some Properties of Term-Power Structure

In this section we establish some further properties of the
term-power structure, including the homomorphism properties between the term algebra of terms and the term algebra
of leafsets. We also argue that it suffices to consider a restricted class of formulas called simple formulas.

(91)

for f 6≡ g

Term algebra of shapes satisfies the original rules (16) of
term algebra.
32

term algebra on terms
constructors, f ∈ Σ:
per-shape product structure
inner formula relations for r ∈ LC :
r

::

::

shape × leafset × leafset → leafset

¬I

::

leafset → leafset

trueI , falseI

::

leafset

:: term → bool

IsPRI

:: term → bool

selectors, f ∈ Σ:
fi

inner formula quantifiers:
∃ ,∀

Isf

primitive-term test:

∧I , ∨I

I

:: termk → term

constructor test, f ∈ Σ:

shape × termk → leafset

inner logical connectives:

I

f

:: term → term

term shape:

::

shape × (term → leafset) → leafset

::

leafset × leafset → bool

sh

:: term → shape

leafset equality:
=L

constructors, f ∈ Σ:

leafset cardinality constraints, k ≥ 0:
| | ≥ k, | | = k

::

shape × leafset → bool

fL

:: leafsetk → leafset

constructor test, f ∈ Σ:

leafset quantifiers:
∃L , ∀L

term algebra on leafsets

::

(leafset → bool) → bool

Isf L

:: leafset → bool

primitive-leafset test:

term equality:
= ::

IsPRIL

term × term → bool

selectors, f ∈ Σ:

term quantifiers:
∃, ∀ ::

(term → bool) → bool

fiL

:: leafset → leafset

leafset shape:

shape equality:
=s

:: leafset → bool

::

shape × shape → bool

::

(shape → bool) → bool

lssh

:: leafset → shape

shape quantifiers:
∃s , ∀s

term algebra on shapes
constructors, f ∈ Σ0 :

logical connectives:
∧, ∨

::

bool × bool → bool

¬

::

bool → bool

true, false, undef

::

bool

fs

:: shapek → shape

constructor test, f ∈ Σ0 :
Isf s

:: shape → bool

selectors, f ∈ Σ:
fis

:: shape → shape

Figure 9: Operations and relations in structure P

33

interpretation of sorts
JtermK

= FT(Σ′ )

JshapeK

= FT(Σ0 )

JleafsetK
JboolK

= {hs, Li | L ⊆ leaves(s)}
= {true, false, undef}

semantics
inner formula relations for r ∈ LC :
JrK(s, t1 , . . . , tk )

well-definedness

= hs, {l | JrKC (t1 [l], . . . , tk [l])}i

sh(t1 ) = s ∧ . . . ∧ sh(tk ) = s

= hs, L1 ∩ L2 i

s1 = s ∧ s2 = s

= hs, L1 ∪ L2 i

s1 = s ∧ s2 = s

= hs, leaves(s) \ L1 i

s1 = s

inner logical connectives:
J∧I K(s, hs1 , L1 i, hs2 , L2 i)
I

J∨ K(s, hs1 , L1 i, hs2 , L2 i)
I

J¬ K(s, hs1 , L1 i)
I

= hs, leaves(s)i

I

= hs, ∅i

Jtrue K(s)
Jfalse K(s)

inner formula quantifiers, for h : JtermK → JleafsetK:
S
J∃I K(s, h) = hs, {L | ∃t ∈ JtermK. sh(t) = s ∧ h(t) = hs, Li}i
T
J∀I K(s, h) = h {L | ∃t ∈ JtermK. sh(t) = s ∧ h(t) = hs, Li}, i

∀t ∈ JtermK. lssh(h(t)) = s
∀t ∈ JtermK. lssh(h(t)) = s

leafset equality:

J=L K(hs1 , L1 i, hs2 , L2 i)

= s1 = s2 ∧ L1 = L2

leafset cardinality constraints:
J|hs1 , L1 i|s ≥ kK

= (|L1 | ≥ k)

s1 = s

J|hs1 , L1 i|s = kK

= (|L1 | = k)

s1 = s

leafset quantifiers, for h : JleafsetK → JboolK:
J∃L Kh

= ∃hs, ti ∈ JleafsetK. h(hs, ti)

L

= ∀hs, ti ∈ JleafsetK. h(hs, ti)

J∀ Kh
term equality:
J=K(t1 , t2 )

= (t1 = t2 )

term quantifiers, for h : JtermK → JboolK:
J∃Kh

= ∃t ∈ JtermK. h(t)

J∀Kh

= ∀t ∈ JtermK. h(t)

shape equality:
J=s K(ts1 , ts2 )

= (ts1 = ts2 )

shape quantifiers, for h : JshapeK → JboolK:
J∃s Kh

= ∃t ∈ JshapeK. h(t)

s

= ∀t ∈ JshapeK. h(t)

J∀ Kh

Figure 10: Semantics for Logic of Term-Power Algebra (Part I)

34

semantics
term algebra on terms

well-definedness

constructors, f ∈ Σ:
Jf K(t1 , . . . , tk ) =

f (t1 , . . . , tk )

constructor test, f ∈ Σ:
JIsf K(t) =

∃t1 , . . . , tk . t = f (t1 , . . . , tk )

primitive-term test:
JIsPRI K(t) =

(t ∈ C)

selectors, f ∈ Σ:
Jfi K(t) =

ǫti . t = f (t1 , . . . , ti , . . . , tk )

JIsf K(t)

term shape:
Jsh(f (t1 , . . . , tn ))K =

shapified(f )(sh(t1 ), . . . , sh(tn ))
term algebra on leafsets

constructors, f ∈ Σ:
Jf L K(hs1 , L1 i, . . . , hsk , Lk i) =

hf (s1 , . . . , sk ), ({1} · L1 ) ∪ · · · ∪ ({k} · Lk )i

constructor test, f ∈ Σ:
JIsf L K(hs, Li) =

∃s1 , L1 , . . . , sk , Lk . hs, Li = Jf L K(hs1 , L1 i, . . . , hsk , Lk i)

primive-leafset test:
JIsPRIL K(hs, Li) =

(s = cs )

selectors, f ∈ Σ:
JfiL K(hs, Li) =

ǫhsi , Li i. hs, Li = Jf L K(hs1 , L1 i, . . . , hsi , Li i, . . . , hsk , Lk i) JIsf L K(hs, Li)

leafset shape:
JlsshK(hs, Li) =

s
term algebra on shapes

constructors, f ∈ Σ:
Jf s K(s1 , . . . , sk ) =

f s (s1 , . . . , sk )

constructor test, f ∈ Σ0 :
JIsf s K(s) =

∃s1 , . . . , sk . s = f s (s1 , . . . , sk )

Jfis K(s) =

ǫsi . s = f s (s1 , . . . , si , . . . , sk )

selectors, f ∈ Σ:

Figure 11: Semantics for Logic of Term-Power Algebra (Part II)

35

JIsf s K(s)

Recall that r = ∈ R is the equality relation on C. Given
r = , we can express the equality between terms by:
t1 = t2

⇐⇒

According to the semantics in Figure 10, sh is a homomorphism from the term algebra of terms to the term algebra of shapes. In addition, lssh is a homomorphism from the
term algebra of leafsets to the term algebra of shapes.
We also have the following important property. Let r ∈
LC be a relation symbol of arity n, let f ∈ Σ be a function
symbol of arity k, and let

r =′ (t1 , t2 )

sh(t2 ) = sh(t1 ) ∧ r = (t1 , t2 ) = trueIsh(t1 )
(92)
We define the notion of a us -term as in Definition 40
except that we use different symbols for boolean algebra
operations.
⇐⇒

sh(t1j ) = . . . = sh(tnj ) = sj

Definition 72 (us -terms) Let us ∈ Vars be a shape variable. The set of us -terms Term(us ) is the least set such that:

for 1 ≤ j ≤ k. If f s = shapified(f ), f L = leafified(f ), and
s = f s (s1 , . . . , sk ) then

1. uL ∈ Term(us ) for every leafset variable uL ;
2.

falseIus , trueIus

rs (f (t11 , . . . , t1k ), . . . , f (tn1 , . . . , tnk )) =

s

∈ Term(u );

f L (rs1 (t11 , . . . , tn1 ), . . . , rsk (t1k , . . . , tnk ))

3. if tL1 , tL2 ∈ Term(us ), then also

(93)

Furthermore, if lssh(lj ) = lssh(lj′ ) = sj for 1 ≤ j ≤ k and
s = f s (s1 , . . . , sk ) then

tL1 ∧Ius tL2 ∈ Term(us ),
tL1 ∨Ius tL2 ∈ Term(us ), and

f L (l1 , . . . , lk ) ∧Is f L (l1′ , . . . , lk′ ) =L

¬Ius tL1 ∈ Term(us )

f L (l1 ∧Is1 l1′ , . . . , lk ∧Isk lk′ )
f L (l1 , . . . , lk ) ∨Is f L (l1′ , . . . , lk′ ) =L

If ts is a term of shape sort, the notion of ts -inner formula
is defined as follows.

f L (l1 ∧Is1 l1′ , . . . , lk ∧Isk lk′ )

Definition 73 (us -inner formula) Let us ∈ Vars be a
shape variable. The set of us -inner formulas Inner(us ) is
the least set such that:

¬Is f L (l1 , . . . , lk ) =L
f L (¬Is1 l1 , . . . , ¬Isk lk )

1. if u1 , . . . , uk are term variables and r ∈ LC such that
ar(r) = k, then

(94)

∃Is t.f L (h1 (t), . . . , hk (t)) =L
f L (∃Is1 t.h1 (t), . . . , ∃Isk t.hk (t))

rus (u1 , . . . , uk ) ∈ Inner(us )

∀Is t.f L (h1 (t), . . . , hk (t)) =L

2. falseIus , trueIus ∈ Inner(us )

f L (∀Is1 t.h1 (t), . . . , ∀Isk t.hk (t))

3. if φ1 , φ2 ∈ Inner(us ) then also

From these properties by induction we conclude that if
φ(us , u1 , . . . , un ) is an inner formula, then

φ1 ∧Ius φ2 ∈ Inner(us )
φ1 ∨Ius φ2 ∈ Inner(us )

φ(s, f (t11 , . . . , t1k ), . . . , f (tn1 , . . . , tnk )) =

¬Ius φ1 ∈ Inner(us )

f L (φ(s1 , t11 , . . . , tn1 ), . . . , φ(sk , t1k , . . . , tnk ))

4. if φ ∈ Inner(us ) and u is a term variable that does not
occur in us , then also

(95)

Let φ(us , u1 , . . . , un ) be an inner formula and let
φ′ (u1 , . . . , un ) be a first-order formula that results from replacing operations ∧Is , ∨Is , ¬Is , ∀Is , ∃Is by ∧, ∨, ¬, ∀, ∃. Interpreting φ′ (u1 , . . . , un ) over the structure C yields a relation
ρ′ ⊆ C n . If
sh(t1 ) = . . . = sh(tk ) = s

∃Ius u.φ ∈ Inner(us )
∀Ius u.φ ∈ Inner(us )
If φ ∈ Inner(us ) and u1 , . . . , un is the set of free term variables of φ, we write φ(us , u1 , . . . , un ) for φ. Furthermore, if
ts is a term of shape sort and t1 , . . . , tn terms of term sort,
we write φ(ts , t1 , . . . , tn ) for

then
JφK(s, t1 , . . . , tk ) = hs, {l | ρ′ (t1 [l], . . . , tk [l])}i

φ[us := ts , u1 := t1 , . . . , un := tn ]

The following Definition 75 introduces a more restricted
set of formulas than the set of formulas permitted by sort
declarations in Figure 9. We call this restricted set of formulas simple formulas. One of the main properties of simple
formulas compared to arbitrary formulas is that simple formulas allow the use of operations ∃I , ∀I , and relations r ,
r ∈ LC only within instances of us -inner formulas.

where we assume that variables bound by ∃I and ∀I are
renamed to avoid the capture of variables that are free in
ts , t1 , . . . , tn .
We call φ(ts , t1 , . . . , tn ) an instance of the us -inner formula φ(us , u1 , . . . , un ).
If φ(us , u1 , . . . , un ) is an inner formula, we abbreviate it by writing [φ′ (u1 , . . . , un )]us where φ′ results from
φ(us , u1 , . . . , un ) by omitting the shape argument us from
the operations occurring in φ(us , u1 , . . . , un ). Similarly, we
write [φ′ (t1 , . . . , tn )]ts for φ(ts , t1 , . . . , tn ).

Definition 74 A simple operation is any operation or relation in Figure 9 except for operations ∃I , ∀I , and relations
r for r ∈ LC .

36

Because the top-level sort of a formula is bool, every
term tL0 of sort leafset occurs within some formula tL1 =L tL2
or Isf L (tL ), |tL |ts = k, |tL |ts ≥ k or as part of some term
lssh(tL ). We can replace Isf L (tL ) with

Definition 75 (Simple Formulas) The set of simple formulas is the least set that satisfies the following.
1. if φ(us , u1 , . . . , un ) is a an inner formula, ts a term of
shape sort, t1 , . . . , tn terms of term sort and uL is a
leafset variable, then
L

L

∃uL . uL =L tL ∧′ Isf L (uL )

s

u = φ(t , t1 , . . . , tn )

according to Lemma 10, so we need not consider that case.
We can similarly eliminate non-variable leafset terms from
cardinality constraints. If a leafset term tL occurs in an
expression lssh(tL ), we consider the smallest atomic formula
ψ(lssh(tL )) enclosing lssh(tL ), and replace ψ(tL ) with

is a simple formula.
2. applying simple operations to simple formulas yields
simple formulas.

∃uL . uL =L tL ∧′ ψ(uL )

Example 76 A formula
(96)

This transformation is valid by Lemma 10 because ψ and
lssh are strict.
We further assume that in every atomic formula tL1 =L tL2 ,
the term tL1 is a leafset variable.
Suppose that a term tL in a formula uL =L tL is not an
instance of an inner formula. Then there are two possibilities.

is a simple formula equivalent to formula (96). We abbreviate ∃Ius1 u. rus1 (u, u) as [∃I u. r(u, u)]us1 .

1. There are some occurrences of leafset term algebra operations f L , fiL or leafset variables uL1 in tL . Here by
“occurrence” in tL we mean occurrence that is reachable
without going through a shape argument or a relation,
but only through operations ∀I , ∃I , ∧I , ∨I , ¬I . For example, we ignore the occurrences of f L , fiL within terms
ts that occur in ∧Its .

uL =L ∃Ius1 u. rus2 (u, u)
is not a simple formula for us1 6≡ us2 . Formula
(us1 = us2 ∧ uL =L ∃Ius1 u. rus1 (u, u)) ∨
(us1 6= us2 ∧ undef)


Lemma 77 shows that for every formula in the logic of
Figure 9 there exists an equivalent simple formula. Note
that even simple formulas are sufficient to express the relations of structural subtyping. A reader not interested in
the decidability of the more general logic of Figure 9 may
therefore ignore Lemma 77.

2. not all shape arguments in ∀I , ∃I , ∧I , ∨I , ¬I ,
trueI , falseI , r occurring in tL are syntactically identical.
We eliminate the first possibility by propagating leafset
term algebra operations f L , fiL inwards until they reach expressions of form Lts (t1 , . . . , tn ), applying the equations (94)
from left to right. We then convert f L , fiL operations of
term algebra of leafsets into operations of the term algebra
of terms applying (93) from right to left.
To eliminate the second possibility, let ts1 , . . . , tsn be the
occurrences (reachable through trueI , falseI , ∧I , ∨I , ¬I ,
∀I , ∃I ) in term tL of the shape arguments of operations
trueI , falseI , ∧I , ∨I , ¬I , ∀I , ∃I . Then replace

Lemma 77 (Formula Simplification) For every welldefined formula in the logic of Figure 9 there exists an equivalent well-defined simple formula.
Proof Sketch. According to the definition of simple formula, we need to ensure that every occurrence of quantifiers
∀I , ∃I and relations r is an occurrence in some inner-formula
instance φ(ts , t1 , . . . , tn ). Each occurrence rts (t1 , . . . , tn ) is
an inner formula instance by itself, so the main difficulty is
fitting the quantifiers ∀I and ∃I into inner formulas.
Let us examine the syntactic structure of formulas of
logic in Figure 9. This syntactic structure is determined
by sort declarations. Each expression of leafset is formed
starting from

uL = tL (ts1 , . . . tsn )
with
s
s s
′
′ CL
s
s s
′
(∃s us . ∀CL
1 (u = t1 ) ∧ . . . ∧ ∀n (u = tn )∧

1. relations r ∈ LC ;

uL =WL tL (us , . . . , us )) ∨
(undef ∧ 1≤i<j≤n tsi 6= tsj )

2. leafset variables;
3. trueI , falseI
I

I

I

I

I

L

Here ∀CL
denotes universal quantification ∀ui,1 , . . . , ui,ni
i
where ui,1 , . . . , ui,ni is a list of those term variables occurring in tsi that are bound by some quantifier ∃I , ∀I within tL .

fiL .

using operations ∧ , ∨ , ¬ , ∀ , ∃ , as well as f and
The
leafset expressions can be used in a formula in the following
ways (in addition to constructing new leafset expressions):
1. to compare for equality using =L ;

6.4

2. to test for the top-level constructor using Isf L ;

Quantifier Elimination

In this section we give a quantifier elimination procedure for
the term-power structure. The procedure of this section is
applicable whenever C is a structure with a decidable firstorder theory.

3. to form leafset cardinality constraints;
4. to form a shape using lssh.
37

where n = p + q, nL = pL + q L , ns = ps + q s , and formulas shapeBase, leafsetBase, termBase, leafsetHom, termHom,
cardin, innerMap are defined as follows.

Definition 78 below generalizes the notion of structural
base formula of Definition 41, Section 4.3. There are two
main differences between Definition 41 and the present Definition 78.
The first difference is the presence of three (instead of
two) base formulas: shape base, leafset base, and term base.
This difference is a consequence of the distinction between
leafsets and terms and is needed whenever base structure
C has more than two elements. There is a homomorphism
formula relating leafset base formula to shape base formula
and a homomorphism formula relating term base formula to
shape base formula. Furthermore, some of the leafset variables are determined by term variables using inner formula
maps, which establishes the relationship between term base
formula and leafset base formula. Cardinality constraints
now apply to leafset variables.
The second difference is the distinction between composed and primitive non-parameter leafset and term variables. A composed non-parameter variable denotes a leafset
or a term whose shape s has property Isf s (s) for some f ∈ Σ.
A primitive non-parameter variable denotes a leafset or a
term whose shape is cs and has property IsPRI or IsPRIL . The
purpose of this distinction is to allow cardinality constraints
and inner formula maps not only on parameter variables,
but also on primitive non-parameter variables, which is useful when the base structure C is decidable but infinite.

shapeBase(us1 , . . . , usns , xs1 , . . . , xsms ) =
s

p
V

usi = ti (us1 , . . . , usns ) ∧

i=1

∧ distinct(us1 , . . . , usn )

• internal primitive
ur+1 , . . . , up ;

non-parameter

term
term

rL
V

i=1
pL
V

uLi = ti (uL1 , . . . , uLnL ) ∧
IsPRIL (uLi ) ∧

i=r L +1
m
VL

i=1

xLi = uLji

where each ti is a term of form f (ui1 , . . . , uik ) for some
f ∈ Σ, k = ar(f ), and j : {1, . . . , mL } → {1, . . . , nL } is a
function mapping indices of free leafset variables to indices
of internal leafset variables.
leafsetHom(uL1 , . . . , uLnL , us1 , . . . , usns ) =

variables

n
VL

i=1

lssh(uLi ) = usji

where j : {1, . . . , nL } → {1, . . . , ns } is some function such
that {j1 , . . . , jp } ⊆ {1, . . . , ps } and {jpL +1 , . . . , jpL +qL } ⊆
{ps +1, . . . , ps +q s } (a leafset variable is a parameter variable
iff its shape is a parameter shape variable).

variables

• internal parameter term variables up+1 , . . . , up+q ;
• free leafset variables xL1 , . . . , xLmL ;

termBase(u1 , . . . , un , x1 , . . . , xm ) =

• internal composed non-parameter leafset variables
uL1 , . . . , uLrL ;

r
V

i=1
p
V

• internal primitive non-parameter leafset variables
uLrL +1 , . . . , uLpL ;

i=r+1
m
V

• internal parameter leafset variables upL +1 , . . . , upL +qL ;
• free shape variables

xsi = usji

leafsetBase(uL1 , . . . , uLnL , xL1 , . . . , xLmL ) =

• free term variables x1 , . . . , xm ;
non-parameter

i=1

where each ti is a shape term of form f s (usi1 , . . . , usik ) for
some f ∈ Σ0 , k = ar(f ), and j : {1, . . . , ms } → {1, . . . , ns } is
a function mapping indices of free shape variables to indices
of internal shape variables.

Definition 78 (Structural Base Formula)
A structural base formula with:
• internal composed
u1 , . . . , ur ;

m
Vs

ui = ti (u1 , . . . , un ) ∧
IsPRI (ui ) ∧
xi = uji

i=1

xs1 , . . . , xsms ;

where each ti is a term of form f (ui1 , . . . , uik ) for some
f ∈ Σ, k = ar(f ), and j : {1, . . . , m} → {1, . . . , n} is a
function mapping indices of free term variables to indices of
internal term variables.

• internal non-parameter shape variables us1 , . . . , usps ;
• internal parameter shape variables usps , . . . , usps +qs
is a formula of form:

termHom(u1 , . . . , un , us1 , . . . , usns ) =

∃u1 , . . . , un , uL1 , . . . , uLnL , us1 , . . . , usns .

n
V

i=1

shapeBase(us1 , . . . , usns , xs1 , . . . , xsms ) ∧
leafsetBase(uL1 , . . . , uLnL , xL1 , . . . , xLmL )

∧

leafsetHom(uL1 , . . . , uLnL , us1 , . . . , usns )

∧

sh(ui ) = usji

where j : {1, . . . , n} → {1, . . . , ns } is some function such
that {j1 , . . . , jp } ⊆ {1, . . . , ps } and {jp+1 , . . . , jp+q } ⊆ {ps +
1, . . . , ps + q s } (a term variable is a parameter variable iff its
shape is a parameter shape variable).

termBase(u1 , . . . , un , x1 , . . . , xm ) ∧

cardin(uLrL +1 , . . . , uLnL , usps +1 , . . . , usns ) = ψ1 ∧ · · · ∧ ψd

termHom(u1 , . . . , un , us1 , . . . , usns ) ∧

where each ψi is of form

cardin(uLrL +1 , . . . , uLnL , usps +1 , . . . , usns ) ∧

|tL (uLrL +1 , . . . , uLnL )|us = k

innerMap(ur+1 , . . . , un , uLrL +1 , . . . , uLnL , usps +1 , . . . , usns )
38

or

As in Section 3.4 and Section 4.3 we proceed to show that
each quantifier-free formula can be written as a disjunction
of base formulas and each base formula can be written as
a quantifier-free formula. We first give a small example to
illustrate how the techniques of Section 4.3 extend to the
more general case of Σ-term-power.

|tL (uLrL +1 , . . . , uLnL )|us ≥ k

for some us -term tL (uLrL +1 , . . . , uLnL ) that contains no variables other than some of the variables uLrL +1 , . . . , uLnL , and
the following condition holds:
If a variable uLj for r L + 1 ≤ j ≤ nL occurs in
the term tL (uLrL +1 , . . . , uLnL ), then lssh(uLj ) =
us occurs in formula leafsetHom.

Example 79 We solve one subproblem from Example 42
using the language of term-power algebras.
Consider the formula

(97)

∃v. g(v, z) ≤ g(z, v) ∧ Isg (v) ∧ Isg (w) ∧

innerMap(ur+1 , . . . , un , uLrL +1 , . . . , uLnL , usps +1 , . . . , usns ) =

¬(g1 (w) ≤ g1 (v))

η1 ∧ · · · ∧ ηe

Formula (99) is in the language of Figure 8, with ≤ a binary
lifted relation. After converting (99) into the language of
Figure 9 we obtain as one of the possible cases formula:

where each ηi is of form
uLj

I

s

= φ (u , ui1 , . . . , uik )

for some inner formula φI (us , ui1 , . . . , uik ) ∈ Inner(us )
where L + 1 ≤ j ≤ nL i.e. uLj is a primitive
non-parameter leafset variable or parameter leafset variable, {ui1 , . . . , uik } ⊆ {ur+1 , . . . , un } are primitive nonparameter term variables and parameter variables, the conjunct lssh(uL ) = us occurs in leafsetHom, and the following
condition holds:
sh(uij ) = us occurs in formula termHom for
every j where 1 ≤ j ≤ k.

(99)

∃v. [g(v, z)  g(z, v)]sh(g(z,v)) =L trueIsh(g(z,v)) ∧
sh(g(z, v)) =s sh(g(z, v)) ∧
Isg (v) ∧ Isg (w) ∧
[g1 (w)  g1 (v)]sh(g1 (w)) 6=

(100)
L

trueIsh(g1 (w))

∧

s

sh(g1 (v)) = sh(g1 (w))

(98)

where  is the subtyping relation on the base structure C so
that ≤ = ′ . We next transform the formula into unnested
form, obtaining:

We require each structural base formula to satisfy the following conditions:
P0) the graph associated with shape base formula

∃v, uvz , uzv , uw1 , uv1 . ∃L uLvz , uLw1 . ∃s usvz , usw1 .

∃us1 , . . . , usns . shapeBase(us1 , . . . , usns , xs1 , . . . , xsms )

uvz = g(v, z) ∧ uzv = g(z, v) ∧

is acyclic (compare to Definition 21);

uw1 = g1 (w) ∧ uv1 = g1 (v) ∧

P1) congruence closure property for shapeBase subformula:
there are no two distinct variables usi and usj such that
both usi = f (usl1 , . . . , uslk ) and usj = f (usl1 , . . . , uslk ) occur
as conjuncts in formula shapeBase;

usvz =s sh(uvz ) ∧ usw1 =s sh(uw1 ) ∧

P2) congruence closure property for leafsetBase subformula:
there are no two distinct variables uLi and uLj such that
both uLi = f L (uLl1 , . . . , uLlk ) and uLj = f L (uLl1 , . . . , uLlk )
occur as conjuncts in formula leafsetBase;

uLvz =L [uvz  uzv ]usvz

sh(uzv ) =s usvz ∧ sh(uv1 ) =s usw1 ∧
Isg (v) ∧ Isg (w) ∧

(101)

|¬uLvz |usvz = 0 ∧
uLw1 =L [uw1  uv1 ]usw1 ∧

P3) congruence closure property for termBase subformula:
there are no two distinct variables ui and uj such that
both ui = f (ul1 , . . . , ulk ) and uj = f (ul1 , . . . , ulk ) occur
as conjuncts in formula termBase;

|¬uLw1 | ≥ 1
We next transform (101) into disjunction of base formulas.
A typical base formula is:

P4) homomorphism property of lssh: for every nonparameter leafset variable uL such that uL =
f L (uLi1 , . . . , uLik ) occurs in leafsetBase, if conjunct
lssh(uL ) = us occurs in leafsetHom, then for some shape
variables usj1 , . . . , usjk term us = f s (usj1 , . . . , usjk ) occurs
in shapeBase where f s = shapified(f ) and for every r
where 1 ≤ r ≤ k, conjunct lssh(uir ) = usjr occurs in
leafsetHom.

∃uvz , uzv , uv , uz , uw , uv1 , uv2 , uz1 , uz2 , uw1 , uw2 .
∃L uLvz , uLv , uLz , uLv1 , uLv2 , uLz1 , uLz2 , uLw1 .
∃s usvz , usw , usw1 , usw2 .
shapeBase1 ∧

(102)

leafsetBase1 ∧ leafsetHom1 ∧
termBase1 ∧ termHom1 ∧

P5) homomorphism property of sh: for every non-parameter
term variable u such that u = f (ui1 , . . . , uik ) occurs in termBase, if conjunct sh(u) = us occurs in
termHom, then for some shape variables usj1 , . . . , usjk
term us = f s (usj1 , . . . , usjk ) occurs in shapeBase where
f s = shapified(f ) and for every r where 1 ≤ r ≤ k,
conjunct sh(uir ) = usjr occurs in termHom.

cardin1 ∧ innerMap1
shapeBase1 = usvz = g s (usw , usw ) ∧ usw = g s (usw1 , usw2 ) ∧
distinct(usvz , usw , usw1 , usw2 )

39

leafsetBase1 = uLvz = g L (uLv , uLz ) ∧
uLv

=g

L

(uLv1 , uLv2 )

∧

and
uLz

=g

L

(uLz1 , uLz2 )

ψ2 ≡
∃uv2 .∃L uLv2 , uLz2 .

leafsetHom1 = lssh(uLvz ) = usvz ∧
lssh(uLv ) = usw ∧ lssh(uLz ) = usw ∧

sh(uv2 ) =s usw2 ∧ sh(uz2 ) =s usw2 ∧

lssh(uLv1 ) = usw1 ∧ lssh(uLv2 ) = usw2 ∧

sh(uLv2 ) =s usw2 ∧ sh(uLz2 ) =s usw2 ∧

lssh(uLz1 ) = usw1 ∧ lssh(uLz2 ) = usw2 ∧

uLv2 =L [uv2  uz2 ]usw2 ∧ uLz2 =L [uz2  uv2 ]usw2 ∧

lssh(uLw1 ) = usw1

|¬uLv2 |usw2 = 0 ∧ |¬uLz2 |usw2 = 0
Formula ψ1 expresses a fact in a structure isomorphic to
the power C n where n is the number of leaves in the shape
denoted by usw1 . Similarly, ψ2 expresses a fact in a product structure C m where m is the number of leaves in the
shape denoted by usw2 . We can therefore use the technique
of Feferman-Vaught technique (Section 3.3) to eliminate the
quantifiers from formulas ψ1 and ψ2 . According to Example 17, ψ1 is equivalent to:

termBase1 = uvz = g(uv , uz ) ∧ uzv = g(uz , uv ) ∧
uv = g(uv1 , uv2 ) ∧ uz = g(uz1 , uz2 ) ∧
uw = g(uw1 , uw2 ) ∧
z = uz ∧ w = uw
termHom1 =
sh(uvz ) = usvz ∧ sh(uzv ) = usvz ∧

∃L uL0 , uL4 .

sh(uv ) = usw ∧ sh(uz ) = usw ∧ sh(uw ) = usw ∧
sh(uv1 ) =

usw1

sh(uv2 ) =

usw2

∧ sh(uz1 ) =

usw1

∧ sh(uz2 ) =

usw2

∧ sh(uw1 ) =

usw1

∧ sh(uw2 ) =

usw2

uL0 =L [∃I t. t  uz1 ∧I uz1  t ∧I uw1  t]usw1 ∧
∧

uL4 =L [∃I t. t  uz1 ∧I uz1  t ∧I ¬I uw1  t]usw1 ∧
|uL4 |usw1 ≥ 1 ∧ |¬I uL0 ∧I ¬I uL4 |usw1 = 0

innerMap1 =

We similarly apply Feferman-Vaught construction to ψ2 and
obtain the result true. We may now substitute the results of
quantifier elimination in ψ1 and ψ2 . The resulting formula
is:

uLv1 =L [uv1  uz1 ]usw1 ∧ uLz1 =L [uz1  uv1 ]usw1 ∧
uLv2 =L [uv2  uz2 ]usw2 ∧ uLz2 =L [uz2  uv2 ]usw2 ∧
uLw1 =L [uw1  uv1 ]usw1

∃uvz , uzv , uv , uz , uw , uv1 , uv2 , uz1 , uz2 , uw1 , uw2 .

cardin1 = |¬uLv1 |usw1 = 0 ∧ |¬uLz1 |usw1 = 0 ∧

∃L uLvz , uLv , uLz , uLv1 , uLv2 , uLz1 , uLz2 , uLw1 .
∃s usvz , usw , usw1 , usw2 .

|¬uLv2 |usw2 = 0 ∧ |¬uLz2 |usw2 = 0 ∧
|¬uLw1 |usw1 | ≥ 1

shapeBase1 ∧
leafsetHom2 ∧

We next show how to transform the base formula (102) into
quantifier-free form.
We substitute away non-parameter term variables
uvz , uzv , uv and non-parameter leafset variables uLvz , uLv , uLz ,
because the homomorphism constraints they participate in
may be derived from the remaining conjuncts. We next eliminate parameter term variables uv1 , uv2 and parameter leafset variables uLv1 , uLv2 , uLz1 , uLz2 , uLw1 . Grouping the conjuncts
in cardin1 and innerMap1 by their shape, we may extract the
subformulas ψ1 and ψ2 of (102).

termBase2 ∧ termHom2 ∧
cardin1 ∧ innerMap1
where
leafsetHom2 = lssh(uL0 ) = usw1 ∧ lssh(uL4 ) = usw1
termBase2 = uz = g(uz1 , uz2 ) ∧ uw = g(uw1 , uw2 ) ∧
z = uz ∧ w = uw

ψ1 ≡
innerMap2 =

∃uv1 .∃L uLv1 , uLz1 , uLw1 .
sh(uv1 ) =s usw1 ∧ sh(uz1 ) =s usw1 ∧ sh(uw1 ) =s usw1 ∧

uL0 =L [∃I t. t  uz1 ∧I uz1  t ∧I uw1  t]usw1 ∧

lssh(uLv1 ) =s usw1 ∧ lssh(uLz1 ) =s usw1 ∧

uL4 =L [∃I t. t  uz1 ∧I uz1  t ∧I ¬I uw1  t]usw1 ∧

lssh(uLw1 ) =s usw1 ∧

cardin2 = |uL4 |usw1 ≥ 1 ∧ |¬I uL0 ∧I ¬I uL4 |usw1 = 0

uLw1 =L [uw1  uv1 ]usw1 ∧

In the resulting formula all variables are expressible in terms
of free variables, so we can write the formula without quantifiers ∃, ∀, ∃L , ∀L .

|¬uLv1 |usw1 = 0 ∧ |¬uLz1 |usw1 = 0 ∧



uLv1 =L [uv1  uz1 ]usw1 ∧ uLz1 =L [uz1  uv1 ]usw1 ∧

|¬uLw1 |usw1 |

≥1

The following Proposition 80 is analogous to Proposition 44; the proof is straightforward.
40

5. formulas of term algebra of shapes:

Proposition 80 (Quantification of Struct. Base) If β
is a structural base formula and x a free shape, leafset, or
term variable in β, then there exists a base structural formula β1 equivalent to ∃x.β.

us1 =s us2 , us1 6=s us2
us0 =s f s (us1 , . . . , usn )

The following Proposition 81 corresponds to Proposition 45.

us =s fis (us0 )

Proposition 81 (Quantifier-Free to Structural Base)
Let φ be a well-defined simple formula without quantifiers
∃L , ∀L , ∃, ∀, ∃s , ∀s . Then φ can be written as true, false, or
a disjunction of structural base formulas.

Isf s (us0 ), ¬Isf s (us0 )
We next describe transformation of each existentially
quantified conjunction. In the sequel, whenever we perform
case analysis and generate a disjunction of conjunctions, existential quantifiers propagate to the conjunctions, so we
keep working with a existentially quantified conjunction.
The existentially quantified variables will become internal
variables of a structural base formula.
Analogously to the proof of Proposition 28, we use
(90), (91), (16) to eliminate literals ¬Isf (u0 ), ¬Isf L f L (uL0 ),
¬Isgs (us0 ).
As in the proof of Proposition 45, we replace formulas of
leafset boolean algebra by cardinality constraints, similarly
to Figure 7.
We next convert formulas of term algebra of terms into
a base formula, formulas of term algebra of leafsets into a
base formula, and formulas of term algebra of shapes into a
base formula.
We simultaneously make sure that every term or leafset
variable has an associated associated shape variable, introducing new shape variables if needed.
We also ensure homomorphism requirements by replacing internal variables when we entail their equality.
Another condition we ensure is that parameter term variables map to parameter shape variables, and non-parameter
term variables to non-parameter shape variables; we do this
by performing expansion of term and shape variables.
We perform expansion of shape variables as in Section 3.2. Expansion of term and variables is even simpler
because there is no need to do case analysis on equality of
term variable with other variables.
We eliminate disequality between term variables using (92). We eliminate disequalities between leafset variables as in Example 43, by converting each disequality into
a cardinality constraint. Elimination of disequalities might
violate previously established homomorphism invariants, so
we may need to reestablish these invariants by repeating the
previously described steps. The overall process terminates
because we never introduce new inequalities between term
or leafset variables.
As a final step, we convert all cardinality constraints into
constraints on parameter term variables, using (95).
In the case when the shape of cardinality constraint is cs ,
we cannot apply (95). However, in this case, unlike Proposition 45, we do not do case analysis on all possible constant
leafsets (this is not even possible in general). This is because
Definition 78, unlike Definition 41 implies no need to further
decompose cardinality constraints in that case, because we
allow primitive non-parameter leafset variables.
This completes our sketch of transforming a quantifierfree formula into disjunction of structural base formulas.

Proof Sketch. The overall idea of the transformation to
base formula is similar to the transformation in the proof of
Proposition 45. Additional complexity is due to inner formulas. However, note that an inner formula φ(us , u1 , . . . , un )
is well-defined iff δ(us , u1 , . . . , un ) holds where
δ(us , u1 , . . . , un ) ≡ sh(u1 ) = us ∧ . . . ∧ sh(un ) = us
Hence, each formula φ(us , u1 , . . . , un ) can be treated as a
partial operation p of sort
shape × termn → leafset
and the domain given by
Dp = hhus , u1 , . . . , un i, δ(us , u1 , . . . , un )i
This means that we may apply Proposition 9 and convert
formula to disjunction existentially quantified well-defined
conjunctions of literals in one of the following forms:
1. equality with inner formulas: uL0 =L φ(us , u1 , . . . , un )
where φ(us , u1 , . . . , un ) is a us -inner formula;
2. formulas of leafset boolean algebra:
uL0 =L uL1 ∧Ius uL2
uL0 =L uL1 ∨Ius uL2
uL0 =L ¬Ius uL1
uL0 =L trueIus
uL0 =L falseIus
3. formulas of term algebra of terms:
u1 = u2 , u1 6= u2
u0 = f (u1 , . . . , un )
u = fi (u0 )
Isf (u0 ), ¬Isf (u0 )
sh(u) = us
4. formulas of term algebra of leafsets:
uL1 =L uL2 , uL1 6=L uL2
uL0 =L f L (uL1 , . . . , uLn )

We introduce the notion of determined variables in structural base formula generalizing Definition 29 and Definition 46.
For brevity, we write u∗ for internal shape, term, or leafset variables, similarly x∗ for a free variable, t∗ for a term

uL =L fiL (uL0 )
Isf L (uL0 ), ¬Isf L (uL0 )
lssh(uL ) =L us

41

and f ∗ for a shape, term, or leafset term algebra constructor
and fi∗ for a shape, term, or leafset term algebra selector.

Lemma 87 Let uL be an undetermined composed nonparameter leafset variable in a structural base formula β such
that uL is a source i.e. no conjunct of form

Definition 82 The set dets of variable determinations of a
structural base formula β is the least set S of pairs hu∗ , t∗ i
where u∗ is an internal term, leafset, or shape variable and
t∗ is a term over the free variables of β, such such that:
∗

′

uL = f L (uL1 , . . . , uL , . . . , uLk )
occurs in leafsetBase. Let β ′ be the result of dropping uL
from β. Then β is equivalent to β ′ .

∗

1. if x = u occurs in termBase, leafsetBase, or
shapeBase, then hu∗ , x∗ i ∈ S;
∗

∗

∗

∗

Proof.
Because uL is a composed non-parameter term
variable, it does not occur in innerMap or cardin, so it only
occurs in leafsetBase and leafsetHom. The conjunct containing uL in leafsetHom is a consequence of the remaining
conjuncts, so it may be dropped. After that, applying (7)
yields a structural base formula β ′ not containing uL , where
β ′ is equivalent to β.

(u∗1 , . . . , u∗k )

2. if hu , t i ∈ S and u
= f
occurs in shapeBase, termBase, or leafsetBase then
{hu∗1 , f1∗ (t∗ )i, . . . , hu∗k , fk∗ (t∗ )i} ⊆ S;
3. if {hu∗1 , f1∗ (t∗ )i, . . . , hu∗k , fk∗ (t∗ )i} ⊆ S and u∗ =
f ∗ (u∗1 , . . . , u∗k ) occurs in shapeBase, termBase, or
leafsetBase then hu∗ , t∗ i ∈ S;
4. if hu, ti ∈ S and sh(u) = us occurs in termHom then
hus , sh(t)i ∈ S;

Corollary 88 Every base formula is equivalent to a base
formula without undetermined composed non-parameter
term variables and without undetermined composed nonparameter leafset variables.

5. if huL , tL i ∈ S and lssh(uL ) = us occurs in leafsetHom
then hus , lssh(tL )i ∈ S;

Proof. If a structural base formula has an undetermined
composed non-parameter term variable, then it has an undetermined composed non-parameter term variable that is
a source, similarly for leafset variables. By repeated application of Lemma 86 and Lemma 87 we eliminate all undetermined non-parameter term and leafset variables.

6. if uL
= φ(us , u1 , . . . , un ) occurs in innerMap
where φ(us , u1 , . . . , un ) is an inner formula
and {hus , ts i, hu1 , t1 i, . . . , hun , tn i}
⊆
S, then
huL , φ(ts , t1 , . . . , tn )i ∈ S.
(In the special case
when φ contains no free term variables, if hus , ts i ∈ S
then huL , φ(us )i ∈ S.

The following Proposition 89 corresponds to Proposition 53 and Proposition 66.

∗

Definition 83 An internal variable u is determined if
hu∗ , t∗ i ∈ dets for some term ts . An internal variable is
undetermined if it is not determined.

Proposition 89 (Struct. Base to Quantifier-Free)
Every structural base formula β is equivalent to a welldefined simple formula φ without quantifiers ∃L , ∀L , ∃, ∀,
∃s , ∀s .

Lemma 84 Let β be a structural base formula with matrix
β0 and let dets be the determinations of β. If hu∗ , t∗ i ∈ S
then |= β0 ⇒ u∗ = t∗ .

Proof Sketch.
By Corollary 88 we may assume that
β has no undetermined composed non-parameter term and
leafset variables. By Corollary 85 we are done if there are
no undetermined variables, so it suffices to eliminate:

Proof. By induction, using Definition 82.
Corollary 85 Let β be a structural base formula such that
every internal variable is determined. Then β is equivalent to a well-defined formula without quantifiers ∃L , ∀L , ∃, ∀,
∃s , ∀s .

1. undetermined parameter term variables,
2. undetermined primitive non-parameter term variables,
3. undetermined parameter leafset variables,

Proof. By Lemma 84 using (7).

4. undetermined primitive non-parameter leafset variables, and

Lemma 86 Let u be an undetermined composed nonparameter term variable in a structural base formula β such
that u is a source i.e. no conjunct of form

5. undetermined shape variables.
If u is an undetermined parameter term variable or a primitive non-parameter term variable, then u does not occur in
termBase, so it occurs only in termHom and innerMap. If
uL is an undetermined parameter leafset variable or a primitive non-parameter leafset variable then uL does not occur
in leafsetBase, so it occurs only in leafsetHom, innerMap, and
cardin.
For a undetermined term or leafset variable of shape us
such that there is an uncovered parameter or primitive nonparameter term or leafset variable with shape us , consider
all conjuncts γi in innerMap of form

′

u = f (u1 , . . . , u, . . . , uk )
occurs in termBase. Let β ′ be the result of dropping u from
β. Then β is equivalent to β ′ .
Proof.
Because u is a composed non-parameter term
variable, it does not occur in innerMap, so it only occurs
in termBase and termHom. The conjunct containing u in
termHom is a consequence of the remaining conjuncts, so it
may be dropped. After that, applying (7) yields a structural
base formula β ′ not containing u, where β ′ is equivalent to
β.

uLj = φ(us , ui1 , . . . , uik )

42

and all conjuncts δi from cardin of form:

6.5

In this section we discuss the decidability of the Σ-termpower structure for a decidable theory C when some of the
function symbols f ∈ Σ are contravariant. We then suggest a generalization of the notion of variance to multiple
relations and to relations with arity greater than two.
The modifications needed to accommodate contravariance with respect to some distinguished relation symbol
≤∈ R for the case of infinite C are analogous to the modifications in Section 5.5. We this obtain a quantifier elimination procedure for any decidable theory C in the presence of
contravariant constructors.

|tL (uLrL +1 , . . . , uLnL )|us = k
or

Handling Contravariant Constructors

|tL (uLrL +1 , . . . , uLnL )|us ≥ k

Together with formulas from termHom and leafsetHom that
contain term and leafset variables free in formulas γi and δi ,
these conjuncts form a formula η which expresses a relation
in the substructure of term-power algebra which (because
constructors are covariant) is isomorphic to a term-power
of C. We therefore use Feferman-Vaught theorem from Section 3.3 to eliminate all term and parameter variables from
η. By repeating this process we eliminate all undetermined
parameter and leafset variables.
It remains to eliminate undetermined shape variables.
This process is similar to term algebra quantifier elimination in Section 3.4. An essential part of construction in
Section 3.4 is Lemma 25, which relies on the fact that undetermined parameter variables may take on infinitely many
values. We therefore ensure that undetermined parameter
shape variables are not constrained by term and parameter variables through conjuncts outside shapeBase. An undetermined parameter shape variable us does not occur in
termHom or leafsetHom because there are no parameter term
and leafset variables, so us can occur only in innerMap and
cardin.
However, because undetermined parameter and leafset
variables are eliminated from the formula, if us is a parameter shape variable then exactly one of these two cases holds:

Theorem 92 (Decidability of Structural Subtyping)
Let C be a decidable structure and P a Σ-term-power of C.
Then the first-order theory of P is decidable.
In the rest of this section we consider a generalization
that allows defining variance for every relation symbol r ∈ R
of any arity, and not just the relation symbol ≤∈ R.
For a given relation symbol r ∈ R, function symbol
f ∈ Σ, with k = ar(f ), and integer i where 1 ≤ i ≤ k,
let Pr (f, i) denote a permutation of the set {1, . . . , k} that
specifies the variance of the i-th argument of f with respect
to the relation r. For example, if r is a binary relation then
Pr (f, i) is the identity permutation {h1, 1ih2, 2i} if i-th argument of f is covariant, or a the transpose permutation
{h1, 2i, h2, 1i} if i-th argument of f is contravariant.
If l ∈ leaves(s) is a leaf l = hf 1 , i1 i . . . hf n , in i, define the
permutation variance(l) as the composition of permutations:

1. there are some conjuncts in innerMap and cardin that
contain us and contain some determined term and leafset variables, in this case us is determined, or

variance(l) = Pr (f n , in ) ◦ · · · ◦ Pr (f 1 , i1 )
Then define JrK by

2. there are no conjuncts in innerMap containing us and
cardin contains only domain cardinality constraints of
form |1|us = k and |1|us ≥ k.

JrK(s, t1 , . . . , tk ) =
hs, {l | JrKC (tp1 [l], . . . , tpk [l]) ∧

Hence, if us is a shape variable it remains to eliminate the
constraints of form |1|us = k and |1|us ≥ k. We eliminate
these constraints as in the proof of Proposition 66.
In the resulting formula all variables are determined. By
Corollary 85 the formula can be written as a formula without
quantifiers ∃L , ∀L , ∃, ∀, ∃s , ∀s .

hp1 , . . . , pk i = variance(l)
}i
We generalize (76) by defining
Nπ (s) = |{l ∈ leaves(s) | variance(l) = π}|

The following is the main result of this paper.

As in Section 5.5, we can transform the constraints
|1|us = k and |1|us ≥ k on each parameter shape variable
into a conjunction of constraints of form:

Theorem 90 (Term Power Quant. Elimination)
There exist algorithms A, B such that for a given formula
φ in the language of Figure 9:

Nπ (us ) = k

a) A produces a quantifier-free formula φ′ in selector language

or

b) B produces a disjunction φ′ of structural base formulas

A problem on nonnegative integers. To solve the
problem of variance with any number of relation symbols of
any arity, it suffices to solve the following problem on sets
of tuples of non-negative integers.
Let Nat = {0, 1, 2, . . .}. Consider the structure St =
Natd for some d ≥ 2 and let D = {1, 2, . . . , d}. If p is a
permutation on D, let Mp denote an operation St → St
defined by

We also explicitly state the following corollary.
Corollary 91 Let C be a structure with decidable first-order
theory. Then the set of true sentences in the logic of Figure 9
interpreted in the structure P according to Figures 10 and
11 is decidable.

Nπ (us ) ≥ k

Mp (x1 , . . . , xd ) = (xp1 , . . . , xpd )

43

If hx1 , . . . , xd i, hy1 , . . . , yd i ∈ St define

The resulting language is at least as expressive as the language in Figure 5. This language is interesting because it
allows reasoning about updates to leaves of a tree of fixed
shape, thus generalizing the theory of updatable arrays [33]
to the theory of trees with update operations, which would
be useful for program verification. We did not choose this
more expressive language in this report for the following
reason.
If the base structure C has a finite domain C, then for
certain reasonable choice of the relations interpreting LC it
is possible to express statements of this extended language
in the logic of Figure 9. The idea is to assume a partial order
on the elements of C with a minimal element, and use terms
t with exactly one leaf non-minimal to model the leaves.
On the other hand, in the more interesting case when C
is infinite, we can easily obtain undecidable theories in the
presence of selection operation. Namely, the selection operation allows terms to be used as finite sets of elements of C.
The term-power therefore increases the expressiveness from
the first-order theory to the weak monadic second-order theory, which allows quantification over finite sets of objects.
Weak monadic theory allows in particular inductive definitions. If theory of structure C is decidable, weak monadic
theory might therefore still be undecidable, as an example
we might take the term algebra itself, whose weak monadic
theory would allow defining subterm relation, yielding an
undecidable theory [55, Page 508].

hx1 , . . . , xd i + hy1 , . . . , yd i = hx1 + y1 , . . . , xd + yd i
Consider a finite set of operations f : Stk → St where each
operation f is determined by k permutations pf1 , . . . , pfk in
the following way:
f (t1 , . . . , tk ) = Mpf (t1 ) + . . . + Mpf (tk )
1

k

Hence, each operation f of arity k is given by a permutation
which specifies how to exchange the order of arguments in
the tuple. After permuting the arguments the tuples are
summed up.
Given a finite set F of operations f , let S be the set
generated by operations in F starting from the element
(1, 0, . . . , 0) ∈ St. Let C(n1 , . . . , nd ) be a conjunction of
simple linear constraints of the forms
ni = ai
and
ni ≥ ai
Consider the set
AC = {(n1 , . . . , nd ) ∈ S|C(n1 , . . . , nd )}
The problem is: For given set of operations F , is there an
algorithm that given C(n1 , . . . , nd ) finitely computes the set
AC .
End of a problem on nonnegative integers.
We conjecture that the technique of Lemma 68 can be
generalized to yield a solution to the problem on nonnegative
integers and thus establish the decidability for the notion of
variance with respect to any number of relations with any
number of arguments.
6.6

7

Some Connections with MSOL

This section explores some relationships between the theory of structural subtyping and monadic second-order logic
(MSOL) interpreted over tree-like structures. We present
it as a series of remarks that are potentially useful for understanding the first-order theory of structural subtyping of
recursive types, see [36, 37] for similar results in the context
of the theory of feature trees.
In Section 7.1 we exhibit an embedding of MSOL of infinite binary tree into the first-order theory of structural
subtyping of recursive types with two constant symbols a,b
and one covariant binary function symbol f . MSOL of infinite binary tree is decidable. Although the embedding does
not give an answer to the decidability of the structural subtyping of recursive types, it does show that the problem is at
least as difficult as decidability of MSOL over infinite trees.
We therefore expect that, if the theory of structural subtyping of recursive types is decidable, the decidability proof will
likely either use decidability of MSOL over infinite trees, or
use directly techniques similar to those of [18, 56].
In Section 7.2 we use the embedding in Section 7.1 to
argue the decidability of formulas of the first-order theory
of structural subtyping of recursive types where variables
range over terms of certain fixed infinite shape se .
In Section 7.3 we present an encoding of all terms using
terms of shape se . We argue that the main obstacle in using this encoding to show the decidability of the first-order
theory of structural subtyping recursive types is inability to
define the set of all prefix-closed terms of the shape se .
In Section 7.4 we generalize the decidability result of Section 7.2 by allowing different variables to range over different
constant shapes.
In Section 7.5 we illustrate some of the difficulties in
reducing first-order theory of structural subtyping to MSOL
over tree-like structures. We show that if we use a certain

A Note on Element Selection

We make a brief note related to the choice of the language
for making statements in term-power algebras. In Section 5
we avoided the use of leafset variables by substituting them
into cardinality constraints. In this section we use a cylindric
algebra of leafsets.
An apparently even more flexible alternative is to allow
the element selection operation
select :: term × leaf → elem
where elem is a new sort, interpreted over the set C, and
leaf is a sort interpreted over the set of pairs of a shape and
a leaf. Instead of the formula
rus (t1 , . . . , tn ) =L trueIus
we would then write
∀l. rus (select(t1 , l), . . . , select(tn , l)) =L trueIus
Using select operation we can define update relation:
update(t1 , l0 , e, t2 ) ≡
∀l. ((l = l0 ∧ select(t2 , l) = e) ∨
(l 6= l0 ∧ select(t2 , l) = select(t1 , l)))

44

form of infinite feature trees instead of infinite terms, the
decidability follows.
In Section 7.6 we point out that monadic second-order
logic with prefix-closed sets is undecidable, which follows
from [48]. This fact indicates that if we hope to show the
decidability of structural subtyping of recursive types, it is
essential to maintain the incomparability of types of different
shape.
7.1

and Succ1 (Y1 , Y2 ) as
∀x.Y2 (x) ⇐⇒ ∃y.y = succ1 (x).
The statement follows by induction on the structure of formulas.
∗

Let R ⊆ (2{0,1} )k × ({0, 1}∗ )n be relation of arity k + n.
∗
∗
Define R∗ ⊆ (2{0,1} )k × (2{0,1} )n by

Structural Subtyping Recursive Types

R∗ (Y1 , . . . , Yk , X1 , . . . , Xn ) ≡

In this section we define the problem of structural subtyping of recursive types. We then give an embedding of
MSOL of the infinite binary tree into the first-order theory
of structural subtyping of infinite terms over the signature
Σ = {a, b, g} with the partial order ≤.
We define MSOL over infinite binary tree [6, Page 317]
as the structure MSOL(2) = h{0, 1}∗ , succ0 , succ1 i. The domain of the structure is the set {0, 1}∗ of all finite strings
over the alphabet {0, 1}. We denote first-order variables by
lowercase letters such as x, y, z. First-order variables range
over finite words w ∈ {0, 1}∗ . We denote second-order variables by uppercase letters such as X, Y, Z. Second-order
variables range over finite and infinite subsets S ⊆ {0, 1}∗ .
The only relational symbol is equality, with the standard interpretation. There are two function symbols, denoting the
appending of the symbol 0 and the appending of the symbol
1 to a word:
succ0 w = w · 0
succ1 w

=

∃x1 , . . . , xn . X1 = {x1 } ∧ · · · ∧ Xn = {xn } ∧
R(Y1 , . . . , Yk , x1 , . . . , xn )
Lemma 94 (MSOL(1) expresses MSOL(2) ) If R is definable in MSOL(2) , then R∗ is definable in MSOL(1) .
Proof Sketch. Property of being an empty set is definable
in MSOL(1) by the formula
φ0 (Y1 ) ≡ ∀Y2 .Y1 j Y2
The relation ⊂ of being a proper subset is definable in
MSOL(1) by formula
φ1 (Y1 , Y2 ) ≡ Y1 j Y2 ∧ Y1 6= Y2
and the relation ⊂1 of having one element more is definable
by formula

w·1

φ2 (Y1 , Y2 ) ≡ Y1 ⊂ Y2 ∧ ¬∃Z. Y1 ⊂ Z ∧ Z ⊂ Y2

For the purpose of embedding into the first-order theory
of structural subtyping, we consider a structure MSOL(1) =
h{0, 1}∗ , j, Succ0 , Succ1 i equivalent to MSOL(2) . We use the
language of MSOL without first-order variables to make
statements within MSOL(1) . j is a binary relation on sets
denoting the subset relation:

The property of being a singleton set can then be expressed
by formula
φ3 (Y1 ) ≡ ∃Y0 . φ0 (Y0 ) ∧ Y0 ⊂1 Y1
We define the relation on singletons corresponding to succ0
by

Y1 j Y2 ⇐⇒ ∀x. x ∈ Y1 ⇒ x ∈ Y2

φ4 (Y1 , Y2 ) ≡ φ3 (Y1 ) ∧ φ3 (Y2 ) ∧ Succ0 (Y1 , Y2 )

Succ0 and Succ1 are binary relations on sets, Succ0 , Succ1 ⊆
∗
∗
2{0,1} × 2{0,1} , defined as follows:
Succ0 (Y1 , Y2 )

⇐⇒

Y2 = {w · 0 | w ∈ Y1 }

Succ1 (Y1 , Y2 )

⇐⇒

Y2 = {w · 1 | w ∈ Y1 }

Similarly, the relation corresponding to succ1 is defined by
φ5 (Y1 , Y2 ) ≡ φ3 (Y1 ) ∧ φ3 (Y2 ) ∧ Succ1 (Y1 , Y2 )
If R is expressible by some formula ψ in MSOL(2) , then R is
expressible by a formula in prenex normal form, so suppose
ψ is of form
Q1 V1 . . . Qn Vn .ψ0

The structure MSOL(1) is similar to one in [18]; the difference is that relations Succ0 and Succ1 are true even for
non-singleton sets.
Lemmas 93 and 94 show the expected equivalence of
MSOL(2) and MSOL(1) .

where ψ0 is quantifier free. We construct a formula ψ ′ expressing R∗ in MSOL(1) . We obtain the matrix ψ0′ of ψ ′
by translating ψ0 as follows. If x is a first-order variable in
ψ0 , we represent it with a second-order variable X denoting a singleton set. We replace membership relation Y (x)
with subset relation X ⊂ Y . We replace succ0 with φ4 and
succ1 with φ5 . We construct ψ ′ by adding quantifiers to
ψ0′ as follows. Second-order quantifiers remain the same.
First-order quantifiers are relativized to range over singleton sets: ∀x.ψi becomes ∀X.φ3 (X) ⇒ ψi′ and ∃x.ψi becomes
∃X. φ3 (X) ∧ ψi′ (X).

Lemma 93 (MSOL(2) expresses MSOL(1) ) Every relation on sets definable in MSOL(1) is definable in MSOL(2) .
Proof. We express relations ⊆, Succ0 , Succ1 as formulas
in MSOL(2) , as follows. We express Y1 ⊆ Y2 as
∀x. Y1 (x) ⇒ Y2 (x),
Succ0 (Y1 , Y2 ) as

We can view
MSOL(1) as a first-order structure with the
∗
domain 2{0,1} . We show how to embed MSOL(1) into the
first-order theory of structural subtyping.

∀x.Y2 (x) ⇐⇒ ∃y.y = succ0 (x),

45

If w = a1 . . . an is a word, then wR denotes the reverse of
the word, wR = an . . . a1 .
We define the embedding ι to map a set Y ⊆ {0, 1}∗ into
the unique tree t such that t ∼ te and for every w ∈ {0, 1}∗ ,

We define the first-order structure of structural subtyping of recursive types similarly to the corresponding structure for non-recursive types in Section 4; the only difference
is that the domain contains both finite and infinite terms.
Infinite terms correspond to infinite trees [12, 30].
We define infinite trees as follows. We use alphabet {l, r}
to denote paths in the tree. A tree domain D is a finite or
infinite subset of the set {l, r}∗ such that:

w ∈ Y ⇐⇒ T (h(wR ) · r) = b

Observe that ι(∅) = te . Define formulas TSucc0 (t1 , t2 ) and
TSucc1 (t1 , t2 ) as follows:

∗

1. D is prefix-closed: if w ∈ {l, r} , x ∈ {l, r} then
w · x ∈ D implies w ∈ D;
2. if w ∈ D then exactly one of the following two properties hold:
(a) w is an interior node: {w · l, w · r} ⊆ D
(b) w is a leaf: {w · l, w · r} ∩ D = ∅.

7.2

T (r · w) = T2 (w),

if w ∈ T2

the term g(x1 , x2 ) denotes a term of the shape g s (se , se ).
First we show that all atomic formulas are of one of the
following forms:
1. x0 = g(g(x1, x2 ), a);
2. x0 = g(g(x1, x2 ), b);
3. x1 = x2 ;
4. x1 ≤ x2 .
Consider an atomic formula t1 = t2 . The key idea is that if
sh(t1 ) 6= sh(t2 ) then the formula t1 = t2 is false.
If none of the term t1 and t2 is a variable then one of them
is a constant or a constructor application. If t1 ≡ g(t11 , t12 )
then either t1 = t2 is false or t2 ≡ g(t21 , t22 ) for some t21 , t22 .
We may therefore decompose t1 = t2 into t11 = t21 and
t12 = t22 . By repeating this decomposition we arrive at
terms of form t1 = t2 where both t1 and t2 are constants or
at the equality of form x0 = t(x1 , . . . , xn ). The equalities
between the constants can be trivially evaluated. This leaves
only terms of form x0 = t(x1 , . . . , xn ). Let ts (xs1 , . . . , xsn ) be
a shape term that results from replacing a and b with cs and
replacing g with g s in t. Because all variables range over Te ,
we conclude that x0 = t(x1 , . . . , xn ) can be true only if

te = g(g(te, te ), a)
Trees in the ∼-equivalence class of te have the tree domain
D = TDom(te ) given by the regular context-free grammar
D → ǫ | r | l | lrD | llD
whereas the leaves L of D are given by the context-free grammar
L → ǫ | r | lrL | llL
or the regular expression (lr|ll)∗ r. Let h be the homomorphism of words from {0, 1}∗ to {l, r}∗ such that

h(1)

=

lr

A Decidable Substructure

g(x1 , x2 ) ≤ g(x3 , g(g(x4 , x5 ), b))

Observe that t1 ∼ t2 iff TDom(t1 ) = TDom(t2 ).
We next present an embedding ι of MSOL(1) into SIT.
The image of the embedding ι are the infinite trees that are
in the same ∼-equivalence-class with the tree te . We define
te as the unique solution of the equation:

ll

≡ t2 = g(g(te, t1 ), te )

We show that the set of closed formulas from BF that are
true in SIT is decidable.
Although the quantifiers are bounded, terms in this logic
can still denote elements of shape other than se . For example, the in the atomic formula

t1 ∼ t2 ≡ ∃t0 . t0 ≤ t1 ∧ t0 ≤ t2

=

TSucc1 (t1 , t2 )

Te = {t | sh(t) = se }

Let IT denote the set of all infinite trees. The structural
subtyping structure is the structure SIT = hIT, g, a, b, ≤i.
SIT is an infinite-term counterpart to the structure BS from
Section 4.
Similarly to the case of finite terms, define the relation
∼ of “being of the same shape” in SIT by

h(0)

≡ t2 = g(g(t1, te ), te )

Section 7.1 shows that terms of shape se form a substructure
within SIT that is isomorphic to MSOL(1) . In this section
we consider the following converse problem.
Consider the formulas BF that, instead of quantifiers
∃, ∀, contain bounded quantifiers ∃e , ∀e that range over the
elements of the set

TDom(T ) = {l · w | w ∈ T1 } ∪ {r · w | w ∈ T2 }
if w ∈ T1

TSucc0 (t1 , t2 )

It is straightforward to show that ι is an injection and that
ι maps relation ⊂ into ≤, relation Succ0 into TSucc0 , and
relation Succ1 into TSucc1 . Moreover, the range of ι is the
set of all terms t such that sh(t) = se where se = sh(te ).

A tree with a tree domain D is a total function T from the
set of leaves of D to the set {a, b}.
Note that the tree domain D of a tree T can be reconstructed from T as the prefix closure of the domain of the
graph of function T ; we write TDom(T ) for the tree domain
of tree T .
Two trees are equal if they are equal as functions. Hence,
equal trees have equal function domains and equal tree domains.
We say that T1 ≤ T2 iff TDom(T1 ) = TDom(T2 ) and
T1 (w) ≤0 T2 (w) for every word w ∈ TDom(T1 ). Here ≤0 is
the relation {ha, ai, ha, bi, hb, bi}.
If T1 and T2 are trees, then g(T1 , T2 ) denotes the tree T
such that

T (l · w) = T1 (w),

(103)

se = ts (se , . . . , se )

46

then we could express all statements of SIT within the BF
subtheory, and therefore SIT would be decidable.
The fundamental problem with specifying P (x) is not the
use of two bits to encode the three possible elements {a, b, g},
but the constraint that if a term contains a subterm of the
form t4 (t1 , t2 , a, a) or t4 (t1 , t2 , a, b) at some even depth, then
t1 ≡ t2 ≡ te . Compared to the relationships given by constructor g, this constraint requires taking about successor
relation at the opposite side of the paths within a tree, see
Section 7.6.

If t(x1 , . . . , xn ) ∈ {a, b} is then (7.2) is false.
If
t(x1 , . . . , xn ) ≡ x1 , we obtain formula of the desired form.
So assume t(x1 , . . . , xn ) ≡ g(t21 , t22 ). Then sh(t21 ) =
g s (se , se ) and sh(t22 ) = cs . Therefore, t21 ≡ g(t211 , t212 )
where either sh(t211 ) = sh(t212 ) = se or t1 = t2 is
false. Similarly, either t22 ∈ {a, b} or t1 = t2 is false.
Therefore, t(x1 , . . . , xn ) ≡ g(g(t211 , t212 ), a), t(x1 , . . . , xn ) ≡
g(g(t211 , t212 ), b), or t1 = t2 is false. If t(x1 , . . . , xn ) ≡
g(g(t211 , t212 ), a) then we may replace the t1 = t2 with the
formula
∃e y1 , y2 . x0 = g(g(y1 , y2 ), a) ∧ y1 = t211 ∧ y2 = t212

7.4

and similarly in the other case. By continuing this process
by the induction on the structure of the term t(x1 , . . . , xn )
we either conclude that t1 = t2 is false, or we conclude that
t1 = t2 is equivalent to a conjunction of formulas of the
desired form.
Conversion of atomic formula of form t1 ≤ t2 is analogous
to the conversion of formulas t1 = t2 .
To see the decidability it now suffices to convert
the formulas of the form x0 = g(g(x1 , x2 ), a) and
x0 = g(g(x1, x2 ), b) into formulas TSucc0 (t1 , t2 ) and
TSucc1 (t1 , t2 ). Expressibility of x0 = g(g(x1, x2 ), a) follows from the fact that the following relationship between
X0 , X1 , X2 is expressible in MSOL:

We next argue that if we allow the logic to have a copy of
bounded quantifiers ∃s , ∀s for every constant shape s, we
obtain a decidable theory. To denote constant shapes in a
finite number of symbols we consider in addition to term
algebra symbols g s , cs the expressions that yield solutions of
mutually recursive equations on shapes; the details of the
representation of types are not crucial for our argument, see
e.g. [12]
Consider a closed formula in such language. Because every variable has an associated constant shape, we can compute the set of all shapes occurring in the formula. This
means that all variables of the formula range over a finite
known set of shapes. This allows us to define the predicate
P given by (104) as a disjunction of cases, one case for every shape. Define hmin , hmax functions that take a shape and
produce a lower and upper bound for terms of that shape:

X0 = {w · 0 | w ∈ X1 } ∪ {w · 1 | w ∈ X2 }
Similarly, the expressibility of x0 = g(g(x1, x2 ), b) follows
from the fact that

hmin (g

X0 = {w · 0 | w ∈ X1 } ∪ {w · 1 | w ∈ X2 } ∪ {ǫ}
is expressible in MSOL. We conclude that the set of closed
BF formulas that are true in SIT is decidable.
7.3

Subtyping Trees of Known Shape

hmax (g

s

hmin (cs ) =

ta

(ts1 , ts2 ))

tg (hmin (ts1 ), hmin (ts2 ))

=

hmax (cs ) =

tb

s

tg (hmax (ts1 ), hmax (ts2 ))

(ts1 , ts2 ))

=

If s1 , . . . , sn is the list of shapes occurring in a formula, we
then define a predicate P specific to that formula by

Embedding Terms into Terms

We next give an embedding of the set of all terms into Te .
As in Section 7.1 te be the unique solution of the equation
te = g(g(te, te ), a) and let

P (t) =

n
_

(hmin (si ) ≤ t ∧ t ≤ hmax (t))

i=1

t4 (x1 , x2 , x3 , x4 ) ≡ g(g(g(g(x1, x2 ), x3 ), te ), x4 )
Define

We can therefore define P (t) and use it to translate the
formula into a BF formula of the same truth value. Therefore, structural subtyping with quantification bounded to
constant shapes is decidable.
For decidability of the structural subtyping recursive
types it would be interesting to examine the decision procedure for MSOL and determine whether there is some uniformity in it that would allow us to handle even quantification
over shapes that are determined by variables.

ta ≡ t4 (te , te , a, a)
tb ≡ t4 (te , te , a, b)
tg (x1 , x2 ) ≡ t4 (x1 , x2 , b, b)

Then define the homomorphism hT from the set of all terms
to the set Te by
hT (a) =

ta

7.5

hT (b) =

tb

We next remark that certain notion of subtyping of recursive
feature trees is decidable. By a feature tree we mean an infinite tree built using a constructor which takes other feature
trees and an optional node label as an argument. In this section we consider the simple case of one binary constructor f
and assume only one label denoted by 1. Hence, an empty
feature tree is a feature tree, and if t1 and t2 are feature trees
then so are f ǫ (t1 , t2 ) and f 1 (t1 , t2 ). We represent an empty
feature tree e by an infinite tree that has all features ǫ. We
compare feature trees as follows. Let ≤ be defined on the

hT (g(t1 , t2 )) =

tg (hT (t1 ), hT (t2 ))

Then hT is embedding of the set of all terms into the subset
subset Te of all terms. The term algebra operations a, b, g
map to ta , tb , tg and ≤ maps to ≤.
Note that, if it were possible to define a predicate P (t)
such that
P (x) ⇐⇒ ∃y.hT (y) = x
(104)

47

Recursive Feature Trees

features {ǫ, 1} as the relation {hǫ, ǫi, hǫ, 1i, h1, 1i}. Define ≤
on trees as the least relation such that:

Every subset of C(w) in PCl is a of the form C(w1 ) for some
word w1 . Define PSucc0 and PSucc1 on PCl by:

1. e ≤ t for all terms t;
2. t1 ≤

t′1

and t2 ≤

t′2

implies

r1

f (t1 , t2 ) ≤ f

r2

(t′1 , t′2 )

The decidability of feature trees follows from Section 7.1
because of the isomorphism hF between the set of terms Te
and the set of feature trees. Here hF is defined by:
hF (e) =

te
g(hF (t1 ), hF (t2 ), a)

1

g(hF (t1 ), hF (t2 ), b)

hF (f (t1 , t2 )) =
hF (f (t1 , t2 )) =

The feature trees as we defined them have a limited feature and node label alphabet. This is not a fundamental
problem. Muchnik’s theorem [56] gives the decidability of
MSOL of trees over arbitrary decidable structures. It is
reasonable to expect that the decidability of MSOL over
decidable structures yields a generalization of the result of
Section 7.1 and therefore the decidability of feature trees
with a richer vocabulary of features.
The crucial property of our definition of feature trees is
that features can appear in any node of the tree. Hence,
there are no prefix closure requirements on trees as in Section 7.3, which is responsible for relatively simple reduction
to MSOL.
7.6

∃w. X1 = C(w) ∧ X2 = C(0 · w)

PSucc1 (X1 , X2 ) =

∃w. X1 = C(w) ∧ X2 = C(1 · w)

Consider a monadic theory PrefT with relations PSucc0 and
PSucc1 where second-order variables range over the subsets
of PCl. It is easy to see that PrefT corresponds to the firstorder theory of non-structural subtyping of recursive types,
with subset relation ⊆ corresponding to subtype relation ≤,
empty set corresponding to the least type ⊥, PSucc0 (X1 , X2 )
corresponding to X2 = f (X1 , ⊥), and PSucc1 (X1 , X2 ) corresponding to X2 = f (⊥, X2 ). The first-order theory of
non-structural subtyping was shown undecidable in [48], so
PrefT is undecidable. An interesting open problem is the decidability of fragments of the first-order theory of structural
subtyping. This problem translates directly to the decidability of the fragments of PrefT, a monadic theory with
prefix-closed sets, or, under the word-reversal isomorphism,
the decidability of fragments of the monadic theory of two
successor symbols with suffix-closed sets.

for all r1 , r2 ∈ {ǫ, 1} such that r1 ≤ r2 .

ǫ

PSucc0 (X1 , X2 ) =

8

Conclusion

In this paper we presented a quantifier elimination procedure for the first-order theory of structural subtyping of
non-recursive types. Our proof uses quantifier elimination.
Our decidability proof for the first-order theory of structural
subtyping clarifies the structure of the theory of structural
subtyping by introducing explicitly the notion of shape of a
term.
We presented the proof in several stages with the hope of
making the paper more accessible and self-contained. Our
result on the decidability of Σ-term-power is more general
than the decidability of structural subtyping non-recursive
types, because we allow even infinite decidable base structures for primitive types. We view this decidability result
as an interesting generalization of the decidability for term
algebras and decidability of products of decidable theories.
This generalization is potentially useful in theorem proving
and program verification.
Of potential interest might be the study of axiomatizability properties; the quantifier elimination approach is appropriate for this purpose [31, 30], we did not pay much attention to this because we view the language and the mechanism for specifying the axioms of secondary importance.
Our goal in describing quantifier elimination procedure
was to argue the decidability of the theory of structural subtyping. While it should be relatively easy to extract an algorithm from our proofs, we did not give a formal description
of the decision procedure. One possible formulation of the
decision procedure would be a term-rewriting system such as
[11]; this formulation is also appropriate for implementation
within a theorem prover. Our approach eliminates quantifiers as opposed to quantifier alternations. For that purpose
we extended the language with partial functions. The use of
Kleene logic for partial functions seems to preserve most of
the properties of two valued logic and appears to agree with
the way partial functions are used in informal mathematical
practice. An alternative direction for proving decidability
of structural subtyping would be to use Ehrenfeucht-Fraisse
games [53, Page 405]; [15] uses techniques based on games
to study both the decidability and the computational complexity of theories.

Reversed Binary Tree with Prefix-Closed Sets

It is instructive to compare the difficulties our approach
faces in showing the decidability of structural subtyping of
recursive types with the difficulties reported in [48]. In [48,
Section 5.3] the authors remark that the difficulty with applying tree automata is that the set x = f (y, z) is not regular. By reversing the set of paths in a tree representing
a term we have shown in Section 7.1 that the relationship
x = f (y, z) becomes expressible. However, the difficulty now
becomes specifying a set of words that represents a valid
term, because there is no immediate way of stating that a
set of words is prefix-closed. If we add an operation that
allows expressing relationship at both “ends” of the words,
we obtain a structure whose MSOL is undecidable due to
the following result [52, Page 183].
Theorem 95 MSOL theory of the structure with two successor operations w · 0 and w · 1 and one inverse successor
operation 0 · w is undecidable.
The case that is of interest of us is the dual to Theorem 95
under the word-reversing isomorphism: a structure with operations 0 · w, 1 · w, w · 0 has undecidable MSOL closed
formulas.
Instead of expressing prefix-closure using operations w·0,
w · 1, let us consider MSOL over the structure that contains
only operations 0 · w and 1 · w, but where all second-order
variables range over prefix-closed sets. This logic also turns
out to be undecidable.
Let PCl be the set of prefix-closed sets. For each word w,
there exists the smallest PCl set containing w, namely the
set C(w) given by:
C(w) = {w′ | w′ ≺ w}
48

The complexity of our the decidability for structural subtyping non-recursive types is non-elementary and is a consequence of the non-elementary complexity of the term algebra, whose elements and operations are present in the theory
of structural subtyping. Tools like MONA [25] show that
non-elementary complexity does not necessarily make the
implementation of a decision procedure uninteresting. An
interesting property of quantifier elimination is that it can
be applied partially to elimination an innermost quantifier
from some formula. This property makes our decision procedure applicable as part of an interactive theorem prover
or a subroutine of a more general decision procedure.
In this paper we have left open the decidability of structural subtyping of recursive types, giving only a few remarks
in Section 7. In particular we have observed in Section 7.1
that every formula in the monadic second-order theory of the
infinite binary tree [6, Page 317] has a corresponding formula
in the first-order theory of structural subtyping of recursive
types. In that sense, the decision problem for structural
subtyping recursive types is at least as hard as the decision
problem for the monadic second-order logic interpreted over
the infinite binary tree. This observation is relevant for two
reasons.
First, it is unlikely that a minor modification of the quantifier elimination technique we used to show the decidability of structural subtyping non-recursive types can be used
to show the decidability of recursive types. Because of the
embedding in Section 7.1 such a quantifier-elimination proof
would have to subsume the determinization of tree automata
over infinite trees.
Second, the embedding suggests even greater difficulties
in implementing a decision procedure for the first-order theory of structural subtyping (provided that it exists). While
we know at least one interesting example of weak monadic
second-order logic decision procedure, namely [25] we are
not aware of any implementation of the full monadic secondorder logic decision procedure for the infinite tree.
The relationship between the non-structural as well as
structural subtyping and monadic second-order logic of the
infinite binary tree and tree like structures [57] requires further study. In that respect the work on feature trees [36, 37]
appears particularly relevant.

[5] L. O. Andersen. Program Analysis and Specialization
of the C Programming Language. PhD thesis, DIKU,
University of Copenhagen, 1994.
[6] Egon Börger, Erich Gräedel, and Yuri Gurevich. The
Classical Decision Problem. Springer-Verlag, 1997.
[7] Witold Charatonik and Leszek Pacholski. Set constraints with projections are in NEXPTIME. In Proc.
35th Annual Symposium on Foundations of Computer
Science (FOCS), pages 642–653, 1994.
[8] Witold Charatonik and Andreas Podelski. Set constraints with intersection. In Proc. 12th IEEE LICS,
pages 362–372, 1997.
[9] Hubert Comon. Disunification: A survey. In JeanLouis Lassez and Gordon Plotnik, editors, Computational Logic: Essays in Honor of Alan Robinson. The
MIT Press, Cambridge, Mass., 1991.
[10] Hubert Comon and Catherine Delor. Equational formulae with membership constraints. Information and
Computation, 112(2):167–216, 1994.
[11] Hubert Comon and Pierre Lescanne. Equational problems and disunification. Journal of Symbolic Computation, 7(3):371, 1989.
[12] Bruno Courcelle. Fundamental properties of infinite
trees. Theoretical Computer Science, 25(2):95–169,
March 1983.
[13] Rowan Davies and Frank Pfenning. Intersection types
and computational effects. In Proc. ICFP, pages 198–
208, 2000.
[14] S. Feferman and R. L. Vaught. The first order properties of products of algebraic systems. Fundamenta
Mathematicae, 47:57–103, 1959.
[15] Jeanne Ferrante and Charles W. Rackoff. The Computational Complexity of Logical Theories, volume 718 of
Lecture Notes in Mathematics. Springer-Verlag, 1979.
[16] Tim Freeman and Frank Pfenning. Refinement types
for ML. In Proc. ACM PLDI, 1991.

Acknowledgements The first author would like to thank
Albert Meyer for pointing out to the work [15], and Jens
Palsberg and Jakob Rehof for useful discussions about the
subject of this paper.

[17] Alexandre Frey. Satisfying subtype inequalities in polynomial space. Theoretical Computer Science, 277:105–
117, 2002.

References

[18] Yuri Gurevich and Leo Harrington. Trees, automata,
and games. In Proceedings of the fourteenth annual
ACM symposium on Theory of computing, pages 60–
65, 1982.

[1] Alexander Aiken. Introduction to set constraint-based
program analysis. Science of Computer Programming,
35:79–111, 1999.

[19] Nevin Heintze and Olivier Tardieu. Ultra-fast aliasing
analysis using CLA: A million lines of C code in a second. In Proc. ACM PLDI, 2001.

[2] Alexander Aiken, Dexter Kozen, and Ed Wimmers. Decidability of systems of set constraints with negative
constraints. Information and Computation, 122, 1995.

[20] Fritz Henglein and Jakob Rehof. The complexity of subtype entailment for simple types. In Proc. 12th IEEE
LICS, pages 352–361, 1997.

[3] Alexander Aiken, Edward L. Wimmers, and T. K. Lakshman. Soft typing with conditional types. In Proc.
21st ACM POPL, pages 163–173, New York, NY, 1994.

[21] L. Henkin, J. D. Monk, and A. Tarski. Cylindric Algebras, Part I. North Holland, 1971.

[4] Roberto M. Amadio and Luca Cardelli. Subtyping recursive types. Transactions on Programming Languages
and Systems, 15(4):575–631, 1993.

[22] Wilfrid Hodges. Model Theory, volume 42 of Encyclopedia of Mathematics and its Applications. Cambridge
University Press, 1993.
49

[39] Derek C. Oppen. Reasoning about recursively defined
data structures. Journal of the ACM, 27(3), 1980.

[23] Trevor Jim and Jens Palsberg. Type inference in systems of recursive types with subtyping. http://www.
cs.purdue.edu/homes/palsberg/, 1999.

[40] Frank Pfenning. Unification and anti-unification in the
calculus of constructions. In Proc. 6th IEEE LICS,
pages 74–85, 1991.

[24] Manfred Kerber and Michael Kohlhase. A mechanization of strong Kleene logic for partial functions. In
Alan Bundy, editor, Proc. 12th CADE, pages 371–385,
Nancy, France, 1994. Springer Verlag, Berlin, Germany.
LNAI 814.

[41] Francois Pottier. Simplifying subtyping constraints: A
theory. Information and Computation, 170(2):153–183,
November 2001.

[25] Nils Klarlund, Anders Møller, and Michael I.
Schwartzbach. MONA implementation secrets. In Proc.
5th International Conference on Implementation and
Application of Automata. Lecture Notes in Computer
Science, 2000.

[42] Jakob Rehof. The Complexity of Simple Subtyping
Systems. PhD thesis, Computer Science Department,
Univ. of Copenhagen (DIKU), April 1998.
[43] Tatiana Rybina and Andrei Voronkov. A decision procedure for term algebras with queues. ACM Transactions on Computational Logic (TOCL), 2(2):155–181,
2001.

[26] Stephen Cole Kleene. Introduction to Metamathematics. D. Van Nostrand Company, Inc., Princeton, New
Jersey, 1952. fifth reprint, 1967.
[27] Dexter Kozen. Complexity of boolean algebras. Theoretical Computer Science, 10:221–247, 1980.

[44] Mooly Sagiv, Thomas Reps, and Reinhard Wilhelm.
Parametric shape analysis via 3-valued logic. ACM
TOPLAS, 24(3):217–298, 2002.

[28] Dexter Kozen, Jens Palsberg, and Michael I.
Schwartzbach. Efficient recursive subtyping. Mathematical Structures in Computer Science, 5(1):113–125,
1995.

[45] Jörg H. Siekmann. Unification theory. Journal of Symbolic Computation, 7(3):207–274, 1989.
[46] Thoralf Skolem. Untersuchungen über die Axiome des
Klassenkalküls and über “Produktations- und Summationsprobleme”, welche gewisse Klassen von Aussagen
betreffen. Skrifter utgit av Vidnskapsselskapet i Kristiania, I. klasse, no. 3, Oslo, 1919.

[29] John W. Lloyd. Foundations of Logic Programming.
Springer-Verlag, 2nd edition, 1987.
[30] Michael J. Maher. Complete axiomatizations of the
algebras of the finite, rational, and infinite trees. Proc.
3rd IEEE LICS, 1988.

[47] Bjarne Steensgaard. Points-to analysis in almost linear
time. In Proc. 23rd ACM POPL, St. Petersburg Beach,
FL, January 1996.

[31] Anatolii Ivanovic Mal’cev. The Metamathematics of
Algebraic Systems, volume 66 of Studies in Logic and
The Foundations of Mathematics. North Holland, 1971.

[48] Zhendong Su, Alexander Aiken, Joachim Niehren, Tim
Priesnitz, and Ralf Treinen. First-order theory of subtyping constraints. In Proc. 29th ACM POPL, 2002.

[32] Ursula Martin and Tobias Nipkow. Boolean unification:
The story so far. Journal of Symbolic Computation,
7(3):275–293, 1989.

[49] Madhu Sudan. Quantifier elimination for boolean algebras is trivial. Personal Communication, MIT LCS
Elevator, 9 October 2002.

[33] John McCarthy and James Painter. Correctness of a
compiler for arithmetic expressions. In Proceedings of
Symposia in Applied Mathematics. American Mathematical Society, 1967.

[50] Alfred Tarski. Arithmetical classes and types of algebraically closed and real-closed fields. Bull. Amer.
Math. Soc., 55, 64, 1192, 1949.

[34] John C. Mitchell. Type inference with simple types.
Journal of Functional Programming, 1(3):245–285,
1991.

[51] Alfred Tarski. Arithmetical classes and types of boolean
algebras. Bull. Amer. Math. Soc., 55, 64, 1192, 1949.

[35] Andrzej Mostowski. On direct products of theories.
Journal of Symbolic Logic, 17(1):1–31, March 1952.

[52] Wolfgang Thomas. Automata on infinite objects. In
Handbook of Theoretical Computer Science, Volume B,
pages 133–191. Elsevier and The MIT Press, 1990.

[36] Martin Mueller and Joachim Niehren.
Ordering
constraints over feature trees expressed in secondorder monadic logic. Information and Computation,
159(1/2):22–58, 2000.

[53] Wolfgang Thomas. Languages, automata, and logic. In
Handbook of Formal Languages Vol.3: Beyond Words.
Springer-Verlag, 1997.
[54] Jerzy Tiuryn. Subtype inequalities. In Proc. 7th IEEE
LICS, 1992.

[37] Martin Mueller, Joachim Niehren, and Ralf Treinen.
The first-order theory of ordering constraints over feature trees. Discrete Mathematics and Theoretical Computer Science, 4(2):193–234, September 2001.

[55] K. N. Venkataraman. Decidability of the purely existential fragment of the theory of term algebras. Journal
of the ACM (JACM), 34(2):492–510, 1987.

[38] Greg Nelson and Derek C. Oppen. Fast decision procedures based on congruence closure. Journal of the
ACM (JACM), 27(2):356–364, 1980.

[56] Igor Walukiewicz. Monadic second-order logic on treelike structures. In STACS’96, volume 1046 of Lecture
Notes in Computer Science, 1996.
50

[57] Igor Walukiewicz. Monadic second-order logic on treelike structures. Theoretical Computer Science, 275(1–
2):311–346, March 2002.

51

