# Overlap operator for simple ( regex-like ) Patterns

( Introduction )

Some Notation

• lower case letters, $$a, b, c$$ will be used to denote single symbols
• Upper case letters, $$P, Q, R$$ will be used to denote string of symbols
• $$a\!:\!S$$ means a string starting with a symbol, $$a$$ and ending with the string $$S$$

I'm currently formulating a simple form of regex-like patterns defined as follows

Given

• An alphabet, $$\Sigma$$, st. $$\{ ?, * \} \notin \Sigma$$

Define

• A pattern over $$\Sigma$$ to be an element of $$( \Sigma\ \cup\ \{ ?, * \})^*$$
• $$\bar\Sigma = \Sigma\ \cup\ \{?\}$$
• $$r(\Sigma) = ( \Sigma\ \cup\ \{ ?, * \})^*$$

( $$.^*$$ denotes to Kleene star operator )

Define the match operator, $$M_s$$, recursively as

$$\forall S \in \Sigma^*.\ \forall P \in r(\Sigma).\ \forall a \in \Sigma.\ \forall \bar{a} \in \bar{\Sigma}.\ \begin{cases} M_s( & \epsilon &, & \epsilon & )\ = & \text{Accept} \\ M_s( & \epsilon &, & \bar{a}:P & )\ = & \text{Reject} \\ M_s( & \epsilon &, & *:P & )\ = & M_s( \epsilon, P ) \\ M_s( & a:S &, & \epsilon & )\ = & \text{Reject} \\ M_s( & a:S &, & \bar{a}:P & )\ = & \begin{cases} M(a,\bar{a}) & M_s( S, P ) \\ \text{otherwise} & \text{Reject} \end{cases}\\ M_s( & a:S &, & *:P & )\ = & M_s( S, *:P )\ \vee\ M_s( a:S, P ) \end{cases}$$

where

$$M(a,b) \equiv ( a = b ) \vee ( a = ? ) \vee ( b = ? )$$

In simple terms, a pattern matches a string if the pattern can be transformed into the string by:

• Substituting $$?$$ for any character
• Substituting $$*$$ for any sequence ( including empty ) of characters

( Question )

I would like to define an overlap operator, $$M_p$$, which given two patterns can return:

• No Overlap
• Overlap, but neither are a subset of each other
• left is a subset of right
• right is a subset of left
• both patterns are equal

Ideally this operator would be defined in such a way that it can be efficiently implemented as well.

( My attempt )

$$\forall P, Q \in r(\Sigma).\ \forall \bar{a}, \bar{b} \in \bar{\Sigma}.\ \begin{cases} M_p( & \epsilon &, & \epsilon & )\ = & \text{Accept} \\ M_p( & \bar{a}:P &, & \epsilon & )\ = & \text{Reject} \\ M_p( & *:P &, & \epsilon & )\ = & M_p( P, \epsilon ) \\ M_p( & \epsilon &, & \bar{b}:Q & ) \ = & \text{Reject} \\ M_p( & \epsilon &, & *:Q & )\ = & M_p( \epsilon, Q ) \\ M_p( & \bar{a}:P &, & \bar{b}:Q & )\ = & \begin{cases} M(\bar{a},\bar{b}) & M_p( P, Q ) \\ \text{otherwise} & \text{Reject} \end{cases}\\ M_p( & \bar{a}:P &, & *:Q & )\ = & M_p( P, *:Q )\ \vee\ M_p( \bar{a}:P, Q ) \\ M_p( & *:P &, & \bar{b}:Q & )\ = & M_p( P, \bar{b}:Q )\ \vee\ M_p( *:P, Q ) \\ M_p( & *:P &, & *:Q & )\ = & M_p( P, *:Q )\ \vee\ M_p( *:P, Q ) \end{cases}$$

This function only gives whether the patterns have overlap. Also I'm unsure how to formally and rigorously show that this operator is correct.