Applications of Brzozowski derivatives to XML Schema processing

Given a set R of sequences and some finite sequence s, the derivative of R with respect to s is denoted by D_sR and is D_sR = {t | st ∈ R}.

• how to construct a regex for D_sR
• any regular R has only finite number of unequal characteristic derivatives
• ... and a finite number of dissimilar derivatives
• how to construct FSA from regex

• [Wilmott] [1991]
• Brüggemann-Klein / Wood (1993, 1998, ...)
• English 1999
• Clark 2002
• Kawaguchi 2003

• Hopkins 1994

• Thompson/Tobin 2003
• Fuchs/Brown 2003

• ε can follow a and make a.
• Nothing can follow b and make a member of {a}.

• --0 = 0
• --unbounded = unbounded
• --n = n - 1, for n > 0

• E | E = E
• E | F = F | E
• (E | F) | G = E | (F | G)
• ε, E = E, ε = E
• ε & E = E & ε = E
• ∅ | E = E | ∅ = E
• ∅, E = E, ∅ = ∅
• ∅ & E = E & ∅ = ∅

• E | E = E
• E | F = F | E
• (E | F) | G = E | (F | G)

1. Let counter n = 0, set Derivatives = {}, flag alldone = true.
2. For each string s ∈ Σ* with length n,
   1. Find F = D_sE.
   2. If F ∈ Derivatives, then do nothing.
   3. Else add F to Derivatives and set alldone flag = false.
   4. If alldone = false, then increment n, set alldone flag = true, and go to 2.
   5. Else stop.

1. D_εE = (a, b, c+)
2. D_aE = (b, c+)
3. D_abE = c+
4. D_abcE = D_abccE = D_abcccE = ... = c*
5. For all other s, D_sE = ∅

• D_hE = h*, ((p+, s*) | (p*, s+)), t?
• D_{h h}E = h*, ((p+, s*) | (p*, s+)), t?
• D_{h h p}E = ((p*, s*) | (p* s+)), t?
• ...
• D_{h h p p p p p}E = ((p*, s*) | (p* s+)), t?
• D_{h h p p p p p s}E = (s* | s*), t?

• D_iE = i{0,9998}, (h?, i{1,9999}){0,9998}
• D_iiE = (i{0,9997}, (h?, i{1,9999}){0,9998})
         | (i{0,9998}, (h?, i{1,9999}){0,9997})
• D_iiE = (i{0,9996}, (h?, i{1,9999}){0,9998})
         | (i{0,9997}, (h?, i{1,9999}){0,9997})
         | (i{0,9998}, (h?, i{1,9999}){0,9996})
• ...

For all symbols x ∈ Σ,
and for all characteristic derivatives F of the original content model,
c(x, F) ≤ 1.

• If E = ε or ∅ or an expanded name or wc(KW,NS) or wc(KW,not(NS)), then E′ = E.
• If E = F | G, then E′ = F′ | G′.
• If E = F, G, then E′ = F′, G′.
• If E = F{n, m}, then E′ = F′{j,k}, where
  • F′ is the recursive simplification of F.
  • If n = m > 1, then j = k = 2.
  • Else j = min(1,n), k = min(2,m), where for all natural numbers n, min(n, unbounded) = n

• D_εE = (a{2,4}, a), c(a, D_εE) = 1
• D_aE = (a{1,3}, a), c(a, D_aE) = 1
• D_aaE = (a{0,2}, a), c(a, D_aaE) = 2
• D_aaaE = ((a?, a) | ε), c(a, D_aaaE) = 2
• D_aaaaE = (a | ε), c(a, D_aaaaE) = 1

• D_εE′ = (a{1,2}, a), c(a, D_εE′) = 1
• D_aE′ = (a{0,1}, a), c(a, D_aE′) = 2
• D_aaE′ = (a | ε), c(a, D_aaE′) = 1

• constructing Glushkov automaton
• checking its determinism

1. D_a E = b+ & ((c* | d*), e)
2. D_ab E = b* & ((c* | d*), e)
3. D_abe E = (b* | ∅) = b*
4. D_abeb E = b*

1. D_a E = b+, ((c* | d*), e)
2. D_ab E = b*, ((c* | d*), e)
3. D_abe E = (ε | ∅) = ε
4. D_abeb E = (∅ | ∅) = ∅

• F and G
• ~F

• D_s (F and G) = (D_s F) and (D_s G)
• D_s (~F) = ~(D_s F)

• F = (a?, (b?, c*)+, a?)
• G = (b | c)*, a)

• D_εE = (((b | c)*, a) and ~(a?, (b?, c*)+, a?))
• D_aE = ((ε) and ~(((b?, c*)+, a?) | ε))
• D_bE = (((b | c)*, a) and ~(c*, (b?, c*)*, a?))
• D_cE = (((b | c)*, a) and ~((b?, c*)*, a?))
• D_aaE = ((∅) and ~(ε | ε))
• D_abE = ((∅) and ~((c*, (b?, c*)*, a?) | ε))
• D_baE = ((ε) and ~(ε))

• easily extensible to new regex notations
• concise, precise
• easy to implement
• sometimes cheaper / faster than FSA-based methods
• even when theoretically not faster, often easier to use, more perspicuous