Nondeterministic Syntactic Complexity
Robert S.R. Myers, Stefan Milius, Henning Urbat · Lecture notes in computer science · 2021
Abstract We introduce a new measure on regular languages: theirnondeterministic 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 anysubatomicnondeterministic 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.