Abstract : We investigate the complexity of deciding whether a given regular language can be defined with a deterministic regular expression. Our main technical result shows that the problem is Pspace-complete if the input language is represented as a regular expression or nondeterministic finite automaton. The problem becomes Expspace-complete if the language is represented as a regular expression with counters.
https://hal-upec-upem.archives-ouvertes.fr/hal-00788609
Contributor : Claire David <>
Submitted on : Thursday, February 14, 2013 - 5:05:04 PM Last modification on : Wednesday, February 3, 2021 - 7:54:27 AM Long-term archiving on: : Wednesday, May 15, 2013 - 4:02:58 AM