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-01806706 Contributor : Admin UpemConnect in order to contact the contributor Submitted on : Monday, June 4, 2018 - 3:01:29 PM Last modification on : Saturday, January 15, 2022 - 3:58:27 AM Long-term archiving on: : Wednesday, September 26, 2018 - 1:48:25 PM