A Formalisation of the Myhill-Nerode Theorem Based on Regular Expressions (Proof Pearl).
Chunhan WuXingyuan ZhangChristian UrbanPublished in: ITP (2011)
Keyphrases
- regular expressions
- interactive theorem proving
- pattern matching
- finite automata
- query language
- semistructured data
- regular languages
- xml schema
- deterministic finite automata
- finite state machines
- theorem proving
- tree automata
- query evaluation
- low level
- matching algorithm
- databases
- regular path queries
- theorem prover
- context free grammars
- co occurrence
- relational databases