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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [32 references]  Display  Hide  Download

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, December 4, 2019 - 12:38:09 PM
Long-term archiving on : Wednesday, September 26, 2018 - 1:48:25 PM

File

jcss-dre.pdf
Files produced by the author(s)

Identifiers

Citation

Wojciech Czerwiński, Claire David, Katja Losemann, Wim Martens. Deciding definability by deterministic regular expressions. Journal of Computer and System Sciences, Elsevier, 2017, 88, pp.75-89. ⟨10.1016/j.jcss.2017.03.011⟩. ⟨hal-01806706⟩

Share

Metrics

Record views

143

Files downloads

179