2018/03/20 by Christopher Hawthorne, Hawthorne, Christopher D. C.
Computer Science · #03C65 (Primary) #68Q45 #68Q70 #Computability, Logic, AI Algorithms #F.4.1 #F.4.3 #FOS: Mathematics #Logic (math.LO) #Logic, programming, and type systems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1803.07234
openalex publication_date 2018/03/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a monoid (M,ε,⋅ ) it is shown that a subset A⊆ M is recognizable in the sense of automata theory if and only if the φ-rank of x=x is zero in the first-order theory Th(M,ε ,⋅ ,A), where φ(x;u) is the formula xu∈ A. In the case where M is a finitely generated free monoid on a finite alphabet Σ, this gives a model-theoretic characterization of the regular languages over Σ. If A is a regular language over Σ then the φ-multiplicity of x=x is the state complexity of A. Similar results holds for φ' (x;u,v) given by uxv∈ A, with the φ' -multiplicity now equal to the size of the syntactic monoid of A.