Regular languages with fixed circuit size have exact logical and algebraic descriptions
Rational Reductions and Regular Languages of Constant Circuit Complexity
Computational ComplexityFormal Languages and Automata TheoryLogic in Computer Science
Summary
The authors studied simple computer circuits that decide whether words belong to certain regular languages, which are patterns recognizable by small machines. They found precise logical rules and algebraic structures that exactly describe which languages can be recognized by circuits of constant size. They also showed how hard it is to tell if a given pattern can be recognized with such small circuits and introduced a new way to compare languages that preserves these complexity bounds. This work clarifies the boundaries between very efficient and slightly more complex recognition of regular languages.
What this means in practice
- •For compiler designers: Use algebraic characterizations to identify small-circuit patterns, optimizing code generation for pattern matching tasks.
- •For hardware engineers: Apply circuit complexity bounds to design minimal hardware for regular language recognition in embedded systems.
A theory result. No direct application yet.
Authors
Stefan Göller, Amaldev Manuel
Abstract
We study the circuit complexity of regular languages in terms of unbounded fan-in Boolean circuit families. We characterize the regular languages of constant circuit complexity in terms of the one-variable fragment of first-order logic with regular predicates, in terms of the pseudovariety of stamps $\mathbf{QEJ}_\mathbf{1}$, suitable word congruences and regular expressions. We analogously characterize the neutral letter regular languages of constant circuit complexity. Our lower bound result implies that the class of regular languages of sublogarithmic circuit complexity coincides with the one of constant circuit complexity. In addition we show that deciding whether a regular language, given as a nondeterministic finite automaton, has constant circuit complexity is $\mathbf{PSPACE}$-complete. We introduce a strong notion of reduction, called rational truth-table reduction, that is tailored towards algebraically defined classes of languages. We show that, for a class of functions we call mild, rational truth-table reductions preserve both upper and lower bounds on circuit complexity. We show that the class of regular languages, whose circuit complexity is bounded by a mild function, is in fact a length-multiplying variety of languages. Slightly extending the class of regular languages of constant circuit complexity, we analogously characterize the class of regular languages that are in the pseudovariety $\mathbf{QEACom}$. For these we derive logarithmic circuit complexity upper bounds.