Skip to Main content Skip to Navigation
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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [27 references]  Display  Hide  Download

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

File

2013fossacs.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00788609, version 1

Citation

Wojciech Czerwiński, Claire David, Katja Losemann, Wim Martens. Deciding Definability by Deterministic Regular Expressions. Foundations of Software Science and Computation Structure (FoSSaCS'13), 2013, Italy. pp.16. ⟨hal-00788609⟩

Share

Metrics

Record views

328

Files downloads

317