 |
HAL UPEC - UPEM Portal |  |
 |
Journal articles
Deciding definability by deterministic regular expressions
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.
Cited literature [32 references]
https://hal-upec-upem.archives-ouvertes.fr/hal-01806706
Contributor : Admin Upem <>
Submitted on : Monday, June 4, 2018 - 3:01:29 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:07 PM
Long-term archiving on: : Wednesday, September 26, 2018 - 1:48:25 PM
Contributor : Admin Upem <>
Submitted on : Monday, June 4, 2018 - 3:01:29 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:07 PM
Long-term archiving on: : Wednesday, September 26, 2018 - 1:48:25 PM
File
jcss-dre.pdf
Files produced by the author(s)