Gershom Bazerman on "Homological Computations for Term Rewriting Systems"

In 1987, C. Squier wrote "Word problems and a homological finiteness condition for monoids," which proved a fascinating result that spawned an entire field, but which is little known outside of it. The great mathematical popularizer and category theorist John Baez sketched the ideas in 1995. We consider "word problems," which ask the equality of two terms modulo a set of equivalences, restrict ourselves to simple objects called "monoids" that many functional programmers are fond of, and ask about the decidability of equality over them. This is the same as looking at strings and asking when they are equal if you consider mappings that equate some contiguous sequences with other contiguous sequences. (Such problems arise ubiquitously in interesting computational problems -- consider for example the equivalence of sequences of patches, or of edit actions across a distributed system). The way computer scientists would think to answer this is to see if you can rewrite both sides of the equation into a single canonical form that you can compare for equality. Indeed, that's what Don Knuth and Peter Bendix did, and the result is the Knuth-Bendix algorithm, used in theorem provers and many other applications.

But just how universal is the Knuth-Bendix algorithm? Well, Squier showed that there are finite monoids with decidable word problems that cannot be turned into such canonical rewrite procedures as Knuth-Bendix gives us. And furthermore, he showed that this result derives from considering our systems using the tools of modern algebraic topology! In particular, he showed how to calculate a homology of a monoid presentation.

Ever since then, people have been seeking to generalize Squier's result in new and exciting ways. One of the niftiest and newest was presented last year at FSCD, this talk's paper, which I love, but do not claim to fully understand. Instead of a monoid, we consider an arbitrary "algebraic theory" (say, a syntax tree of a programming language with some equalities between certain forms of trees). And we now ask not about the word problem, but just the minimum number of equalities necessary to present such a theory. The answer, which can be computed with an algorithm, comes from even more, and more generalized homology. The purpose of this talk is to make the above understandable to a lay audience, to sketch some idea of how to think about things that arise in computer science topologically, and to provide an invitation to basic notions of homology.

Transcript

1. Gershom Bazerman Homological Computations for Term Rewriting Systems Papers We Love, NY Aug 2017
4. Homological Computations for Term Rewriting Systems 4 - 6 + 4 = 2 8 - 12 + 6 = 2 6 - 12 + 8 = 2 20 - 30 + 12 = 2 12 - 30 + 20 = 2
5. (a) Homology (theory) is a Functor Mathematical Object (like a space) -> Sequence of Mathematical Objects (like groups)
6. An Aside on Groups •A set with a single associative operation (•), a zero element (e), and a negation operation such that a • -a = e. •A generating set with terms as sequences of elements of the set, zero, and their negations under the group laws, and an identification of some terms (e.g. adq=bc). •A closed collection of permutations of a set (Cayley). •A one object category with all morphisms invertible •Closed paths in a space.
7. An Aside on Groups •A one object category with all morphisms invertible Since categories are considered up to isomorphism, this is the group. In all other cases there may be multiple descriptions which map, one to one, to one another. The rank of a group is the size of the smallest generating set of the group.
8. (a) Homology (theory) is a Functor 4 Vertices, 6 Edges, 4 Faces Or 1 0-blob (connected component), 
 0 1-blobs (2-d components)
 1 2-blob (3-d components)
9. Euler’s Formula: V - E + F
10. Generalization • Euler Characteristic:
 Alternating sum of vertices, faces, etc.
 Alternating sum of Betti numbers • Betti numbers:
 Number of “holes” at each dimension
 Rank of the n-th homology group • Homology group:
 Group constructed from dissecting an object into n-blobs and finding the cycles
 Function on adjacent components of a chain complex
12. Homological Computations for Term Rewriting Systems
13. Monoids A Set 
 equipped with a Binary Operation and Distinguished Element
 such that the operation is associative and the element is identity Examples: {T,F} (and, T) {T,F} (or, F) {0,1,2…} (+,0) {1,2,3…} (*,1)
14. Monoid Presentations • Motivation: Finite presentation of infinite structure. • All monoids are quotients of free monoids. • A Set 
 Another Set, consisting of pairs of Words from the first set. • Examples: 
 {a | _ } (natural numbers under addition)
 {a | aa = a} (the boolean lattice)
 {p,q | pq = 1} (the bicyclic monoid)
 {a,b | aa = a, bb = b} (the free band on two elements) • All presentations give rise to monoids
 Monoids admit multiple presentations
15. Monoid Presentations <=> String Rewriting Systems “The Word Problem”
 Given a monoid presentation, find an algorithm to test if two elements are equal under the given rewrite rules. Emil Post (1947): There are monoids for which equality is undecidable Proof: Consider a monoid presented by S, K, I. Then look up the “halting problem” on Wikipedia.
16. Aside: String Rewriting and Computer Science • Fundamental results in computability • Instruction sequences in assembly • Unrestricted grammars • Combinatory logic • Operational Transformation
 (edit sequences to documents) • Distributed and asynchronous systems
17. A Partial Solution Knuth/Bendix Start with a finitely presented monoid. Create a confluent, normalizing, directed rewrite system (i.e. a different presentation). We do this by systematically rewriting the rewrite rules. It either succeeds, or fails to terminate. (Newman’s lemma: if all critical pairs are confluent,
 the system is globally confluent)
18. Knuth/Bendix Example {x,y|x^3=y^3=(xy)^3=1} 1. Create directed reductions in e.g. lexiographic order
 x^3->1, y^3->1, (xy)^3->1 2. Check overlaps to find a critical pair (nonconfluent branch) 
 x^3yxyxy -> yxyxy 
 x^3yxyxy -> x^2 3. Add a new rule to complete the pair
 yxyxy->x^2 4. Remove rules now made redundant, goto 2. Result: x^3 -> 1, y^3 -> 1, yxyx -> x^2y^2, y^2x^2 -> xyxy
19. Next Question • What if we restrict ourselves to finitely presented monoids with decidable word problems. Can we get a normalization procedure? • Consider {s,t| sts = tst}
 No normalization is possible. • But, create a new presentation where a=st, and we get.
 {s,t,a | ta->as, st->a, sas->aa, saa->aat} • So we must establish this as a question over all possible generators.
20. Moving Between Presentations Tietze Transformations: Add a generator expressed as other generators
 Remove a generator expressible by other generators
 Add a derivable relation
 Remove a redundant relation

21. The big a-ha Add a generator <-> add a vertex
 Remove a generator <-> delete a vertex
 Add a derivable relation <-> add an edge
 Remove a redundant relation <-> delete an edge
22. Rewrite Systems as Spaces abbd ed acd x ? Confluence requires a topological property: all cycles of a certain shape can be “filled” by a 2-cell.
 Find a homological invariant of a monoid that is preserved under Tietze transformations.
23. Chain Complexes Revisited (source: http://visualizingmath.tumblr.com/post/128146041831/isomorphismes-homology-for-normal-humans-my) The chain condition: ^2 = 0.
 Our slogan: “The boundary of the boundary is zero”
24. Given a chain complex (A•, d•) Homology is ker(dn)/im(dn+1) Suppose: im(dn+1) = ker(dn). Then the homology is trivial. (no holes), and we are exact at n. Exact sequence: chain such that it is exact at every n. Exact Sequences
25. Resolutions If we only care about homotopy (or homology) structure, then we want to treat any two spaces with the same associated groups as equivalent. A weak equivalence is a map between spaces that introduces an isomorphism on homotopy structure. A resolution of a space is a weakly equivalent space subject to some condition (depending on the resolution). It gives a way of “rearranging” a space to make it more understandable.
26. Homology Resolutions A plain object (group, module, ring, etc) A, considered as a node in a chain complex yields:
 0 -> A -> 0 A resolution of A is a new chain complex that shares topological structure. A left resolution, for example, looks like:
 … A2 -> A1 -> A -> 0 As such, a resolution is an exact sequence containing A.
27. Theorem (Squier 1987) • We take ℤM as the free ring generated by a monoid M;
 i.e. polynomials in elements of M. Taking M to have elements {a,b,c} we get:
 5a+2b-3c, 2a-1b+4b, … • A free ℤM-module over a set S, written ℤM[S] contains formal sums of pairs from M and S; i.e. polynomials in pairs from M and S.
 Taking S to have elements {x,y,z} we get:
 2ax + 4cy, ay - az, …
28. Theorem (Squier 1987) • Given a presentation (Σ1,Σ2) of a M, there is an exact sequence of free ℤM-modules:
 
 
 
 
 
 (the overbar is the element of the monoid corresponding to a given generator) (images: GM16)
29. Theorem (Squier 1987) • Given a finite presentation (Σ1,Σ2) of a M, there is an exact sequence of free ℤM-modules:
 
 
 
 
 
 
 (the overbar is the element of the monoid corresponding to a given generator) • Theorem: This is a partial free resolution of length 2, composed of finitely generated, projective modules. • Hence we say M is of homological type left-FP2 (images: GM16)
30. Aside: the bracket [x] is an element of ℤM[Σ1], x ̅ an element of ℤM [α] is an element of [Σ2], but s(α) is an element of Σ1*, not Σ1 ! So, using a “pun” we define [.] of elements of Σ1* : Σ1* -> ℤM[Σ1] This is an inductive function (in fact, a fold): [.] 1 = 0 [.] uv = [u] + u ̅[v] (images: GM16)
31. Theorem (Squier 1987) • If (Σ1,Σ2) is confluent, we can generate Σ3, given by the “fillers” of the critical branches. Then we extend our sequence like so:
 
 
 
 
 • Theorem: This is a partial free resolution of length 3 • Hence we say M is of homological type left-FP3 (images: GM16)
32. Theorem (Squier 1987) • Every monoid is of type left-FP0 • Every finitely generated monoid is of type left-FP1 • Every finitely presented monoid is of type left-FP2 • Every finite convergent monoid is of type left-FP3
33. Example (Squier 1987) (image: Squier 1987) (Sk is proved to have a decidable word problem for all k)
34. Whew!
35. Meanwhile in 1987
36. Meanwhile in 1987 String rewriting systems present monoids Term (tree) rewriting systems present algebraic theories. As with monoids, we view these things presentation first, but understanding that different presentations may describe the same mathematical object.
37. Algebraic Theories An equational theory involves: Operations with arities (0-ary constants, 1-ary, binary, etc.)
 Universally quantified relations over those operations Example: groups generating operations: e : 0, - : 1, • : 2 relations: ∀ x. x • e = x, ∀ x. e • x = x, 
 ∀ x, y, z. (x • y) • z = x • (y • z)
 ∀ x. x • -x = e, ∀ x. -x • x = e An algebraic theory is an equivalence class of equational theories.
38. Aside: Term Rewriting and Computer Science • Typeclasses and laws as theories • Typeclasses with functional dependencies as a rewrite system • Syntax trees under equivalence induced by eval • eval itself
 (though note: lambda binders mean a theory is not algebraic) • Computer algebra • Theorem proving
39. 30 years later… Monoids correspond to string rewriting systems. Algebraic theories correspond to term rewriting systems. If homology of monoids lets us prove facts about string rewriting presentations. Then… homology of algebraic theories lets us prove facts about term rewriting systems?
40. 30 years later… Groups don’t need five relations. In fact, they only need one! (proven in 1952). x / 
 ((((x / x) / y) / z) / 
 (((x / x) / x) / z))
 = y
41. 30 years later… Groups are one- based Semi-lattices and distributive lattices are not. Normal lattices are. Boolean algebra? Proven one-based in 2,000, with a single axiom of over 40 million symbols. 
 (this was later improved)
42. There is a Homology that determines if a theory is one-based Idea: each rewrite rule consumes some symbols, and produces other symbols. We can forget the shape of the rule, and just examine the net effect. g(f(x),f(x)) = h(x) —> h = 2f + g however we need to interpret this in a way that is aware of substitutions into contexts.
43. Aside: Contexts g f f h g f j h A context in Kn is a term with a distinguished variable and n other variables
 A bicontext in (m,n) is a context in n and an arrow from a term in m to a term in n. Bicontexts induce functions between terms (in fact, rewriting functions).
44. Contexts make Things Complicated Monoid —> Ringoid Free monoid —> Quotient of the free ringoid (by context equivalences induced by the relations), aka R.
 (images: MM16)
45. There is a Homology that determines if a theory is one-based Theorem: Every convergent presentation of an algebraic theory gives rise to a partial resolution of the form: with P1 the generators, P2 the relations, and P3 the critical pairs. ( here is the trivial R module) (images: MM16)
46. There is a Homology that determines if a theory is one-based This is an exact sequence, so the homology is trivial.
 Hence we take homology over this tensored by op.
 (conceptually, this “cancels” the coefficients in R). Theorem: The rank of H1 (= ker(op⊗d0 )/im(op⊗d1 )) is a lower bound on the number of operations of a theory. Theorem: The rank of H2 (= ker(op⊗d1 )/im(op⊗d2 )) is a lower bound on the number of relations of a theory. (images: MM16)
47. The Homotopification of Everything –Marshall Stone (1938) “A cardinal principle of modern mathematical research may be stated as a maxim: ‘One must always topologize’”
48. The Homotopification of Everything –We Do Not Choose Mathematics as OurProfession, It Chooses Us: Interview with Yuri Manin (2009) “But fundamental psychological changes also occur… Instead of sets, clouds of discrete elements, we envisage some sorts of vague spaces, which can be very severely deformed, mapped one to another, and all the while the specific space is not important, but only the space up to deformation. If we really want to return to discrete objects, we see continuous components, the pieces whose form or even dimension does not matter. Earlier, all these spaces were thought of as Cantor sets with topology, their maps were Cantor maps, some of them were homotopies that should have been factored out, and so on….
49. The Homotopification of Everything “I am pretty strongly convinced that there is an ongoing reversal in the collective consciousness of mathematicians: the right hemispherical and homotopical picture of the world becomes the basic intuition, and if you want to get a discrete set, then you pass to the set of connected components of a space defined only up to homotopy. That is, the Cantor points become continuous components, or attractors, and so on — almost from the start. Cantor’s problems of the infinite recede to the background: from the very start, our images are so infinite that if you want to make something finite out of them, you must divide them by another infinity.” –We Do Not Choose Mathematics as OurProfession, It Chooses Us: Interview with Yuri Manin (2009)
50. The Tree and the Shadows (Fontainebleau Forest, Monet, 1865)
51. References • More on Squier’s Theorem:
 Polygraphs of Finite Derivation Type
 (Giuraud, Malbos, 2016) [GM16]
 Word Problems and a Homological Finiteness Condition for Monoids (Squier, 1987) • More on Algebraic Topology:
 Algebraic Topology (Hatcher, 2002). • More on Homological Algebra:
 Introduction to Commutative Algebra (Atiyah, MacDonald, 1969). • More on Groups:
 Group Theory (Course notes by J.S. Milne, 1996 onwards). (All otherwise unattributed mathematical images sourced from Wikimedia Commons) (Memes due to Asif Raza Rana)