On the undecidability and descriptional complexity of synchronized regular expressions.
Jingnan XieHarry B. HuntPublished in: Acta Informatica (2023)
Keyphrases
- regular expressions
- pattern matching
- finite automata
- tree automata
- query language
- xml schema
- deterministic finite automata
- semistructured data
- regular path queries
- exptime complete
- regular languages
- query evaluation
- query containment
- pspace complete
- special case
- matching algorithm
- description logics
- computational complexity
- conjunctive regular path queries
- decision problems