Pro-Aperiodic Monoids via Saturated Models
summary
Free pro-aperiodic monoids are realized as the Stone dual of the Lindenbaum algebra for first-order theory of finite words, and elements are represented by omega-saturated models so concatenation and substitution become concrete, continuous operations. Model-theoretic tools (types, saturation) yield combinatorial descriptions of factorizations, give a short proof of equidivisibility, and show prefixes/suffixes of Omega-terms remain Omega-terms, recovering and simplifying known algorithms and structural results.
AI-written summary · about
chapters (8)
- 0:00Start
- 0:37Introduction
- 1:26First-order definability and aperiodicity
- 3:44The Stone space of a first-order theory
- 8:07Concatenation and substitution
- 11:02A larger pro-aperiodic monoid
- 19:11First application: equidivisibility
- 20:12Further applications: factors of a substitution
related talks
33mOn the Dominance-Based Strengthening Rule
30mDetermination Problems for Orbit Closures and Matrix Groups
33mUnlimited Register Machines, Gödelization and Universality
54mConstraints, Gadgets, and Invariants
56mApproximate Counting II
01h 02mConsistency of NEXP Not in P/poly in a Strong Theory
58mDichotomy Theorems for Counting Problems II
48mUnprovability of Strong Complexity Lower Bounds in Bounded Arithmetic