```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

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.

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

```