 |
HAL UPEC - UPEM Portal |  |
 |
Conference papers
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 [27 references]
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 26, 2020 - 7:06:06 PM
Long-term archiving on: : Wednesday, May 15, 2013 - 4:02:58 AM
Contributor : Claire David <>
Submitted on : Thursday, February 14, 2013 - 5:05:04 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:06 PM
Long-term archiving on: : Wednesday, May 15, 2013 - 4:02:58 AM
File
2013fossacs.pdf
Files produced by the author(s)