What type of study is this?

This is a Experimental Study study.

October 9, 2025Open Access

On Complementation of Nondeterministic Finite Automata without Full Determinization (Technical Report)

Key Points

Using novel approaches to complement NFAs can yield significantly smaller complements, reducing computational overhead.
The paper explores methods that avoid complete determinization, which can exponentially increase size.
Alternative constructions based on the inherent structure of NFAs have been developed and tested.
Experiments on a large data set reveal the efficacy of these methods in practical applications.

Abstract

Complementation of finite automata is a basic operation used in numerous applications. The standard way to complement a nondeterministic finite automaton (NFA) is to transform it into an equivalent deterministic finite automaton (DFA) and complement the DFA. The DFA can, however, be exponentially larger than the corresponding NFA. In this paper, we study several alternative approaches to complementation, which are based either on reverse powerset construction or on two novel constructions that exploit a commonly occurring structure of NFAs. Our experiment on a large data set shows that using a different than the classical approach can in many cases yield significantly smaller complements.

Read Full Paperexternally

Mark Helpful

Bookmark

Relay

View Full Paper