@inproceedings{5c1667d7b2fe4bfd82728adbf5fa6628,

title = "The complexity of the inequivalence problem for regular expressions with intersection",

abstract = "The nondeterministic lower space bound √n of Hunt, for the problem if a regular expression with intersection describes a non-empty language, is improved to the upper bound n. For the general inequivalence problem for regular expressions with intersection the lower bound cn matches the upper bound except for the constant c. And the proof for this tight lower bound is simpler than the proofs for previous bounds. Methods developed in a result about one letter alphabets are extended to get a complete characterization for the problem of deciding if one input-expression describes a given language. The complexity depends only on the property of the given language to be finite, infinite but bounded, or unbounded.",

author = "Martin Furer",

year = "1980",

month = jan,

day = "1",

doi = "10.1007/3-540-10003-2_74",

language = "English (US)",

isbn = "9783540100034",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "234--245",

editor = "{de Bakker}, Jaco and {van Leeuwen}, Jan",

booktitle = "Automata, Languages and Programming - 7th Colloquium",

address = "Germany",

note = "7th International Colloquium on Automata, Languages and Programming, ICALP 1980 ; Conference date: 14-07-1980 Through 18-07-1980",

}