On classes of tractable unrestricted regular expressions (Q1061498)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On classes of tractable unrestricted regular expressions |
scientific article |
Statements
On classes of tractable unrestricted regular expressions (English)
0 references
1985
0 references
The class of unrestricted regular expressions (URE) is defined by adding to classical regular operations (i.e. union, concatenation and star iteration) the set of language operations generated by arbitrary boolean functions. It is well known that the problem of deciding whether two URE expressions accept the same language is not elementary recursive. The subclasses of URE having tractable complexity are studied in the paper.
0 references
0 references
