On Classes of Tractable Unrestricted Regular Expressions.
Ernst L. LeissPublished in: Theor. Comput. Sci. (1985)
Keyphrases
- regular expressions
- regular languages
- pattern matching
- query language
- finite automata
- semistructured data
- xml schema
- deterministic finite automata
- tree automata
- query evaluation
- graph databases
- regular path queries
- data exchange
- np complete
- np hard
- matching algorithm
- data management
- context free grammars
- grammatical inference
- domain knowledge
- data model
- computational complexity