Copyright ©2008  T. H. Merrett

COMP 617	Information Systems		Winter 2008		Week 1

			Sequences in Aldat

1. Sequence relations

	e.g., aababb	Str(seq term)
			     1    a
			     2    a
			     3    b
			     4    a
			     5    b
			     6    b

2. Regular expressions

	e.g., (a|b)*(abb|aa*b)

   - are recognized by finite automata

	e.g.,		DFA( sS term eS )	final( eS)
			      1   a  125	      136
			      1   b    1	       14
			    125   a  125
			    125   b  136
			    136   a  125
			    136   b   14
			     14   a  125
			     14   b    1

	relation nextS(eS) <- {(1)};
	for k <- 1: [red max of seq] in Str
	{ nextS <- DFA[nextS,Str[k]] };
	pr final icomp nextS;

	NB nextS <- DFA[nextS,Str[k]]   means
	   nextS <- DFA[(intg)nextS,(strg)Str[k]]   or
	   nextS <- [eS] where  sS = [red max of eS] in nextS   and
				term = [red max of term] where seq=k in Str
			 in DFA

      Instead of for-loop, we could have read-events and event handlers:
	comp read:Str(nextS) is			<< Note output parameter >>
	{ k <- 1 + [red max of seq] in .trigger;
	  nextS <- DFA[nextS,Str[k]]
	}
	relation nextS(eS) <- {(1)};
	nextS <- DFA[nextS,Str[1]]
	pr term icomp nextS;

3. Deterministic finite automata, DFA, are generated from nondeterministic
   finite automata, NFA, which can be written down from the regular expression.
   [e.g., lambda.uta.edu/cse5317/spring01/notes/node9.html]

   e.g., (a|b)*(abb|aa*b)	NFA(sS term eS)		final(eS)
				     1   a   1		       4
				     1   b   1		       6
				     1   a   2
				     2   b   3
				     3   b   4
				     1   a   5
				     5   a   5
				     5   b   6

   Next steps: regex -> NFA; NFA -> DFA in Aldat.

   How about DFA -> regex?

4. Query by variables

	e.g., XXYX applied to aababb will match X=a, Y=b

	      Aldat:	term = fun succ of term order seq
			and
			term = fun succ of
				    fun succ of
					 fun succ of term order seq
				    order seq
				order seq
			and
			term != fun succ of
				     fun succ of term order seq
				order seq
		in the where clause:
		[seq] where .. in Str

	Let's introduce succ(n) and pred(n) operators:
		fun succ(0) of <> order  == <>
		fun succ(1) of <> order  == fun succ of <> order 
		fun succ(2) of <> order  == fun succ of
						   fun succ of <>
						   order 
						 order 
		..

	    Aldat:	term = fun succ(1) of term order seq
			and
			term = fun succ(3) of term order seq
			and
			term != fun succ(2) of term order seq

5. Can we make an operator for general patterns of this sort?
		domain X,Y term;		<< for singleton >>
		[X,Y] grepseq(seq,term,X,Y;X,X,Y,X) in Str
	gives		(X Y)
			 a b

	And beyond
		domain X term;		<< for singleton >>
		domain Y(seq,term);	<< for subsequence >>
		[X,Y] grepseq(seq,term,X,Y;X,Y,X) in Str
	gives		(X Y         )
			   (seq,term)
			 a   2    a
			     3    b
			 b   4    a
			     5    b
	(all the longest matches).