1
$\begingroup$

( 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.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.