The pseudofinite monadic second order theory of words

2022/02/15 by Deacon Linkhorn, Linkhorn, Deacon
Computer Science · #06E25 #2020 Mathematics Subject Classification. Primary: 03C64 #20M99 #22A30 #Advanced Algebra and Logic #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO) #Natural Language Processing Techniques #Secondary: 06E15 #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2202.07774

openalex publication_date 2022/02/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We analyse the pseudofinite monadic second order theory of words over a fixed finite alphabet. In particular we present an axiomatisation of this theory, working in a one-sorted first order framework. The analysis hinges on the fact that concatenation of words interacts nicely with monadic second order logic. More precisely, give a signature under which for each natural number k, equivalence of (monadic second order versions of) words with respect to formulas of quantifier depth at most k is a congruence for concatenation. We use our analysis to present an alternative proof of a theorem connecting recognisable languages and finitely generated free profinite monoids via extended Stone duality, due to Gehrke, Grigorieff, and Pin.

Related

• The Pseudofinite Monadic Second Order Theory of Linear Order
• Monadic Monadic Second Order Logic
• Positive first-order logic on words
• Languages recognised by finite semigroups, and their generalisations to objects such as trees and graphs, with an emphasis on definability in monadic second-order logic
• Lecture Notes on Monadic First- and Second-Order Logic on Strings