The emptiness of complement problem for semi extended regular expressions requires \(c^n\) space

DOI10.1016/0020-0190(79)90073-5zbMath0423.68010OpenAlexW1969832527MaRDI QIDQ1134514

John Michael Robson

Publication date: 1979

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(79)90073-5

zbMATH Keywords

regular expressionsspace complexityemptiness of complement

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (1)

Succinctness of regular expressions with interleaving, intersection and counting

Cites Work

• Unnamed Item

This page was built for publication: The emptiness of complement problem for semi extended regular expressions requires \(c^n\) space