2021/01/08 by Robert P. Myers, Myers, Robert, Stefan Milius +3
Computer Science · #Advanced Algebra and Logic #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Natural Language Processing Techniques #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2101.03039
openalex publication_date 2021/01/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce a new measure on regular languages: their nondeterministic syntactic complexity. It is the least degree of any extension of the `canonical boolean representation' of the syntactic monoid. Equivalently, it is the least number of states of any subatomic nondeterministic acceptor. It turns out that essentially all previous structural work on nondeterministic state-minimality computes this measure. Our approach rests on an algebraic interpretation of nondeterministic finite automata as deterministic finite automata endowed with semilattice structure. Crucially, the latter form a self-dual category.