Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
Visit Stack Exchange
Stack Internal
Knowledge at work
Bring the best of human thought and AI automation together at your work.
Explore Stack InternalThe complexity of deciding equality of regular languages (and many other problems on regular languages) varies a lot depending on the system of representation:
P for deterministic automaton (more precisely NL-complete)
PSPACE-complete for nondeterministic automaton or regular expression
EXPSPACE-complete for regular expression with squaring operation.
NONELEMENTARY for Monadic Second-Order (MSO) formula.
The complexity of deciding equality of regular languages (and many other problems on regular languages) varies a lot depending on the system of representation:
P for deterministic automaton
PSPACE-complete for nondeterministic automaton or regular expression
EXPSPACE-complete for regular expression with squaring operation.
NONELEMENTARY for Monadic Second-Order (MSO) formula.
The complexity of deciding equality of regular languages (and many other problems on regular languages) varies a lot depending on the system of representation:
P for deterministic automaton (more precisely NL-complete)
PSPACE-complete for nondeterministic automaton or regular expression
EXPSPACE-complete for regular expression with squaring operation.
NONELEMENTARY for Monadic Second-Order (MSO) formula.
The complexity of deciding equality of regular languages (and many other problems on regular languages) varies a lot depending on the system of representation:
P for deterministic automaton
PSPACE-complete for nondeterministic automaton or regular expression
EXPSPACE-complete for regular expression with squaring operation.
NONELEMENTARY for Monadic Second-Order (MSO) formula.
