the equality problem in�automata, combinatorics, and logic
L. Clemente (University of Warsaw)
Infinity @ Antwerp, September 2023
summary
1. combinatorial structures
a combinatorial class of structures over a signature Σ is a sequence A₁, A₂, …�where Aₙ is a class of structures over Σ with domain {1, …, n}.
examples:
1. labelled vs. unlabelled
Undirected graphs on three vertices
1
2
3
1
2
3
1
2
3
1
2
3
1
2
3
1
2
3
1
2
3
1
2
3
labelled
unlabelled
2. Wilf equivalence (labelled)
a combinatorial class of structures over a signature Σ is a sequence A₁, A₂, …�where Aₙ is a class of structures over Σ with domain {1, …, n}.
its labelled Specker sequence is Fₙ := size of Aₙ [1].
its labelled Specker series is F(x) := Σₙ Fₙ · xⁿ / n! (exponential generating series).
labelled Wilf equivalence problem: given two combinatorial classes,�do they have the same labelled Specker sequence / series?
[1] Specker, Blatter: “Recurrence relations for the number of labeled structures on a finite set” 1984
2. Wilf equivalence (unlabelled)
a combinatorial class of structures over a signature Σ is a sequence A₁, A₂, …�where Aₙ is a class of structures over Σ with domain {1, …, n}.
its unlabelled Specker sequence is fₙ := size of Aₙ up to automorphism.
its unlabelled Specker series is f(x) := Σₙ fₙ · xⁿ (ordinary generating series).
unlabelled Wilf equivalence problem: given two combinatorial classes,�do they have the same unlabelled Specker sequence / series?
[1] Specker, Blatter: “Recurrence relations for the number of labeled structures on a finite set” 1984
3. examples (empty signature)
3. examples (one unary relation P)
3. examples (one binary relation R)
3. case studies
3a. polynomials (PIT / ACIT / EqSLP)
3b. constructively algebraic series (CA)
3c. constructively differentially algebraic series (CDA)
3a. polynomial identity testing
polynomials (succinctly) represented as circuits with sum and product
+
✕
y₁
5
-3
✕
y₂
3a. polynomial identity testing
small circuits yield exponential degrees
y
✕
✕
✕
…
✕
y^(2^n)
3a. polynomial identity testing
[1] Schönhage “On the power of random access machines” ICALP’79
[2] Ibarra, Moran “Equivalence of straight-line programs” JACM’83
[3] DeMillo, Lipton “A probabilistic remark on algebraic program testing” IPL’78
[4] Schwartz “Fast probabilistic algorithms for verification of polynomial identities” JACM’80
[5] Zippel “Simplification of Radicals with Applications to Solving Polynomial Equations” MsC thesis ’77
[6] Allender, Bürgisser, Kjeldgaard-Pedersen, Miltersen “On the Complexity of Numerical Analysis” SIAM JC’09
3b. constructively algebraic series
series represented as circuits with (guarded) recursion
z = 1 + y · z²
⇒ z = 1 + y + 2y² + …
+
1
✕
y
✕
z
3b. constructively algebraic series
a tuple of multivariate power series
f₁, …, fₕ ∈ ℚ⟦y₁, … , yₖ⟧
is constructively algebraic (CA) if it is the unique solution�(cf. implicit function theorem) of a system of polynomial equations
z₁ = p₁ (y₁, … , yₖ; z₁, … , zₕ)
⋮
zₕ = pₕ (y₁, … , yₖ; z₁, … , zₕ)
where p₁, …, pₕ ∈ ℚ[y₁, … , yₖ; z₁, … , zₕ].
3b. CA series: examples (1)
open problem: Is every ℕ-valued CA series a ℕ-CA series?�(i.e., definable by a equations with coefficients in ℕ)
�[1] Kreweras “Sur une classe de problemes de denombrement lies au treillis des partitions des entiers” ‘65�[2] Tutte “On the enumeration of planar maps” AMS Bulletin ‘68
3b. CA series: examples (2)
census generating series of context-free grammars are algebraic [1]:�
grammar X ← a b a | a X X b
census fₘₙ := # derivation trees of words in L(X)
with m a’s and n b’s
census gen. series f(x₀, x₁) := ∑ₘₙ fₘₙ · x₀^m · x₁^n
polynomial eqn. y = x₀² · x₁ + x₀ · x₁ · y²
[1] Chomsky, Schützenberger “The Algebraic Theory of Context-Free Languages” ‘63
3b. CA series: problems
given a multivariate polynomial / CA series
represented as a circuit / the unique solution of a system of polynomial equations
the order (lowest degree) of e.g.
EqXXX reduces to OrdXXX by exponential upper bounds� on the order of a nonzero polynomial / series
3b. CA series: results
[0] Forejt, Jancar, Kiefer, Worrell “Language equivalence of probabilistic pushdown automata” Inf. Comput. ’14
[1] Kayal, Saha “On the Sum of Square Roots of Polynomials and Related Problems” ACM Trans. Comput. Theory’12
[2] Balaji, C, Nosan, Shirmohammadi, Worrell “Multiplicity Problems on Algebraic Series and Context-Free Grammars” LICS’23
OrdALG
EqALG
OrdSLP
EqSLP
polynomials
CA series
???
∈ coRP
∈ coRP^PP [1]
! [2]
[0] PSPACE ∋
3b. how bad is coRP^PP?
good: coRP^PP ⊆ PP^PP the second level of the counting hierarchy
CH = P ∪ PP ∪ PP^PP ∪ PP^(PP^PP) ∪ … ⊆ PSPACE�
bad: by Toda’s theorem [2], PH ⊆ P^PP (!)
[1] Gill “Computational Complexity of Probabilistic Turing Machines” SIAM Journal on Computing ‘77
[2] Toda “PP is as Hard as the Polynomial-Time Hierarchy” SIAM Journal on Computing ‘91
3b. solution concepts
(Strassen’s trick [3]: simulate division by multiplication)
→ The CA series and the polynomial computed by the circuit have the same order
�[1] Bourbaki “Commutative Algebra” 1998
[2] Eisenbud “Commutative algebra: with a view toward algebraic geometry 1995
[3] Strassen “Vermeidung von divisionen” 1973
3b. rational approx. of CA series
vs.
Newton iteration
the n-th iterate agrees with the CA series�on terms of total degree O(2ⁿ)
by Hensel’s lemma
Kleene iteration
the n-th iterate agrees with the CA series�on terms of total degree O(n)
3b. polynomial approx. of rat. series
3b. circuit approx. of rat. series
3b. CA series: results
Theorem [0]. EqALG reduces in PTIME to OrdSLP and thus is in coRP^PP.
[0] Balaji, C, Nosan, Shirmohammadi, Worrell “Multiplicity Problems on Algebraic Series and Context-Free Grammars” LICS’23
[1] Forejt, Jancar, Kiefer, Worrell “Language equivalence of probabilistic pushdown automata” Inf. Comput. ’14
open problem: does EqALG reduce in PTIME to EqSLP? is it in coRP?
(improving on PSPACE [1])
3b. CA series: one application
(*) for every word, they have the same number of accepting derivation trees
(**) L ⊆ w₁* … wₖ* for words w₁, …, wₖ ∈ Σ* [1]; by a PTIME reduction to EqALG
[0] Balaji, C, Nosan, Shirmohammadi, Worrell “Multiplicity Problems on Algebraic Series and Context-Free Grammars” LICS’23
[1] Ginsburg “The mathematical theory of context-free languages” 1966
[2] Mathew, Penelle, Saivasan, Sreejith “Weighted one-deterministic-counter automata” ArXiv’23
Theorem [0]. The following problem is decidable (in coRP^PP):
multiplicity equivalence (*) of grammars restricted to a bounded lang. (**).
major open problem: is multiplicity equivalence of grammars decidable?
3c. from CA to CDA series
a tuple of power series
f₁, …, fₕ ∈ ℚ⟦x⟧
is constructively algebraic (CA) if it is the unique solution�of a system of polynomial equations
f₁ = p₁ (x; f₁, …, fₕ)
⋮
fₕ = pₕ (x; f₁, …, fₕ)
with polynomial kernel p₁, …, pₕ ∈ ℚ[x; z₁, …, zₕ].
3c. from CA to CDA series
a tuple of power series
f₁, …, fₕ ∈ ℚ⟦x⟧
is constructively differentially algebraic (CDA) if it is the unique solution�of a system of ordinary differential equations (ODEs)
𝝏ₓ f₁ = p₁ (x; f₁, …, fₕ)
⋮
𝝏ₓ fₕ = pₕ (x; f₁, …, fₕ)
with polynomial kernel p₁, …, pₕ ∈ ℚ[x; z₁, …, zₕ].�(multivariate generalisation available)
3c. CA ⊆ CDA by example
Catalan numbers C = 1 + x · C²
⇒ 𝝏ₓC = C² + 2x · C · 𝝏ₓC
⇒ 𝝏ₓC = C² / (1 - 2x · C)
let D := 1 / (1 - 2x · C), then
𝝏ₓC = C² · D
𝝏ₓD = D² · (2C + 2x · C² · D)
3c. Bell numbers are CDA
by the composition principle, partition numbers satisfy
B = e^(e^x - 1)
⇒ 𝝏ₓB = B · e^x
let E := e^x, then
𝝏ₓB = B · E
𝝏ₓE = E
3c. Caley numbers are CDA
by the composition principle, rooted unordered trees satisfy
T = x · e^T
⇒ 𝝏ₓT = e^T + x · e^T · 𝝏ₓT = e^T + T · 𝝏ₓT
⇒ 𝝏ₓT = e^T / (1 - T)
let E := e^T, S = 1 / (1 - T), then
𝝏ₓT = E · S
𝝏ₓE = E
𝝏ₓS = E · S³
3c. series-parallel graphs are CDA [1]
a series-parallel graph is a single node / series / parallel graph
G = x + S + P
a series graph is a nonempty sequence of single nodes / parallel graphs
S = 1 / (1 - (x + P)) - 1
a parallel graph is a nonempty set of single nodes / series graphs
P = e^(x + S) - 1
𝝏ₓG = …
𝝏ₓS = …
𝝏ₓP = …
[1] Pivoteau, Salvy, Soria “Algorithms for combinatorial structures: Well-founded systems and Newton iterations” ’12
3c. constructing CDA series
Theorem [1, 2, 3, 4]. The power series of combinatorial classes built from the primitives above and recursion are CDA.
[1] Joyal: “Une théorie combinatoire des séries formelles” (Advances in Mathematics, 1981)
[2] Bergeron, Labelle, Leroux, Readdy: “Combinatorial Species and Tree-like Structures” (CUP, 1998)
[3] Flajolet, Sedgewick: “Analytic Combinatorics” (CUP, 2009)
[4] Pivoteau, Salvy, Soria: “Algorithms for combinatorial structures: Well-founded systems and Newton iterations” (Journal of Combinatorial Theory, 2012)
combinator singleton {a} disjoint union A ⊎ B product A · B list of A’s cyclic list of A’s multiset of A’s | algebra x sum f + g product f · g 1 / (1 - f) - log(1 - f) e^f |
3c. CDA closure properties
3c. CDA kernels = CDA
if a tuple of power series
f₁, … , fₕ ∈ ℚ⟦x⟧
solves the ODE
𝝏ₓ f₁ = g₁ (x; f₁, … , fₕ)
⋮
𝝏ₓ fₕ = gₕ (x; f₁, … , fₕ)
with CDA kernel g₁, …, gₕ ∈ ℚ⟦x; z₁, …, zₕ⟧, then it is itself CDA.
3c. CDA recursion = CDA
if a tuple of power series
f₁, … , fₕ ∈ ℚ⟦x⟧
is the unique solution of the system
f₁ = g₁ (x; f₁, … , fₕ)
⋮
fₕ = gₕ (x; f₁, … , fₕ)
with CDA kernel g₁, …, gₕ ∈ ℚ⟦x; z₁, …, zₕ⟧, then it is itself CDA.
3c. remarks
if f = a₀ + a₁·x + a₂·x²/ 2! + …
then 𝝏ₓ f = a₁ + a₂·x + a₃·x²/2! + …
however we never need this
⇒ we develop the theory of CDA series purely formally (algebraically)
⇒ this is a good fit to decide zeroness and equality of CDA series
3c. series zoo
differentially transcendental series: OGF of Bell numbers…
differentially algebraic series: OGF of n!
CDA series: EGF of Bell numbers, of n^n…
CA series: Catalan numbers
rational series: 1 + x + x² + x³ + ...
polynomials: 1 - x³
3c. CDA vs. D-finite series
a series f is D-finite if it satisfies a linear diff equation with poly coeffns [0]:
(p₀(x) + p₁(x)𝝏ₓ + p₂(x)𝝏ₓ² + … + pₙ(x)𝝏ₓⁿ) f = 0
the CDA and D-finite are incomparable:
a least common generalisation is available…
[0] Stanley “Differentiably Finite Power Series” European Journal of Combinatorics ’80
[1] Bostan, Di Vizio, Raschel “Differential transcendence of Bell numbers and relatives: a Galois theoretic approach” ’21
3c. CDA equality problem
Theorem. The CDA equality problem is decidable with 2EXPTIME complexity.
related results:
[1] Denef, Lipshitz “Power series solutions of algebraic differential equations” Mathematische Annalen 1984
3c. CDA solution technique
short witness property:�two distinct CDA series f, g differ by a monomial of degree at most 2-exp
roadmap via effective ideal theory:
[1] Novikov, Yakovenko “Trajectories of polynomial vector fields and ascending chains of polynomial ideals” 1999
3c. CDA solution technique (2)
ℚ⟦x⟧
ℚ[y₁, …, yₕ]
fix a CDA system 𝝏ₓf₁ = p₁(f₁, …, fₕ)
⋮
𝝏ₓfₕ = pₕ(f₁, …, fₕ)
p
f
_ ￮ (f₁, …, fₕ)
𝝏ₓf
𝝏ₓ
Lp
_ ￮ (f₁, …, fₕ)
L
L : ℚ[y₁, …, yₕ] → ℚ[y₁, …, yₕ]
L = p₁ · 𝝏y₁ + … + p₁ · 𝝏yₕ
(Lie derivative)
⇒ 𝝏ₓⁿ f = Lⁿp ￮ (f₁, …, fₕ)
is f = 0?
where f := p(f₁, …, fₕ)
3c. CDA solution technique (3)
Lˢ⁺¹p = q₀· L⁰p + … + qₛ· Lˢp
𝝏ₓˢ⁺¹ f = g₀· 𝝏ₓ⁰ f + … + gₛ· 𝝏ₓˢ f
3c. CDA finite basis problem
consider the ideal J of all polynomials vanishing on CDA series (f₁, …, fₕ):
J = { p ∈ ℚ[y₁, …, yₕ] | p(f₁, …, fₕ) = 0 }
open problems:
note: this is Skolem-hard for polynomial recursive sequences [1]
[1] Müllner, Moosbrugger, Kovács “Strong Invariants Are Hard: …” ArXiv 2023
3c. summary on the equality problem
(*) explicitly presented as LRS, otherwise PIT-complete if given with circuits
[1] Schützenberger “On the Definition of a Family of Automata” Information and Control 1961
[2] Tzeng “On path equivalence of nondeterministic finite automata” Information Processing Letters 1996
[3] Balaji, C, Nosan, Shirmohammadi, Worrell “Multiplicity Problems on Algebraic Series and Context-Free Grammars” LICS 2023
[4] Koechlin “Systèmes de fonctions holonomes, application à la théorie des automates” PhD thesis 2021
[5] Denef, Lipshitz “Power series solutions of algebraic differential equations” Mathematische Annalen 1984
4. VASS series
a VASS series f = Σₙ fₙ·xⁿ ∈ ℕ⟦x⟧ counts the number fₙ�of accepting computations of length n of a VASS
open problem: is equality of VASS series decidable?
notes:
[1] Jančar “Nonprimitive recursive complexity and undecidability for Petri net equivalences” TCS’01
[2] Czerwiński, Hofman “Language Inclusion for Boundedly-Ambiguous Vector Addition Systems Is Decidable” CONCUR’22
[3] Bostan, Bousquet-Mélou, Melczer “Counting walks with large steps in an orthant” ’18
4. VASS series
a VASS series f = Σₙ fₙ·xⁿ ∈ ℕ⟦x⟧ counts the number fₙ�of accepting computations of length n of a VASS
open problem: is equality of VASS series decidable?
notes:
[1] Jančar “Nonprimitive recursive complexity and undecidability for Petri net equivalences” TCS’01
[2] Czerwiński, Hofman “Language Inclusion for Boundedly-Ambiguous Vector Addition Systems Is Decidable” CONCUR’22
[3] Bostan, Bousquet-Mélou, Melczer “Counting walks with large steps in an orthant” ’18
4. Wilf equivalence for logic
a Specker series f = Σₙ fₙ·xⁿ ∈ ℕ⟦x⟧ counts the number fₙ�of models (up to iso) of a formula of logic
Wilf equivalence problem: equality of Specker series
open ended question�which logics have a decidable Wilf equivalence problem?
[1] Trakhtenbrot “Impossibility of an algorithm for the decision problem in finite classes” ’50
here be dragons
hic
sunt
leones
template #1
thank you for your question
template #2
here is the proof
template #3
I haven’t thought about it
template #4
if I had the time I would…
but I don’t Q.E.D.
template #5
can we take this offline
the real INFINITY