Extended Regular Expressions: Succinctness and Decidability.
Dominik D. FreydenbergerPublished in: STACS (2011)
Keyphrases
- regular expressions
- pattern matching
- query language
- finite automata
- monadic second order logic
- deterministic finite automata
- query containment
- regular path queries
- semistructured data
- xml schema
- tree automata
- query evaluation
- query answering
- regular languages
- expressive power
- graph databases
- description logics
- integrity constraints
- information extraction
- modal logic
- normal form
- matching algorithm
- database