Extended Regular Expressions: Succinctness and Decidability.
Dominik D. FreydenbergerPublished in: Theory Comput. Syst. (2013)
Keyphrases
- regular expressions
- pattern matching
- finite automata
- xml schema
- monadic second order logic
- query language
- query containment
- deterministic finite automata
- regular path queries
- tree automata
- semistructured data
- regular languages
- matching algorithm
- description logics
- databases
- modal logic
- decision procedures
- context free grammars
- expressive power
- type checking
- relational databases
- learning algorithm