migrating from traditional regexp cardinalities to shexj abstract syntax

This email lays out the current cardinality tests in preparation for
adapting them to ShExJ's abstract syntax.

The triple expressions in shexj are one of:

  triple constraint: predicate, inverse, value expression, cardinality
  allOf: sequence of triple expressions, cardinality
  someOf: sequence of triple expressions, cardinality
  inclusion: ref to a shape's triple expression.

Currently the permissible cardinality on any of these is {0,∞}.  We
may restrict the permissible cardinalities on allOfs and containers of
allOfs in the future in order to simplify the 

The ICDT paper gave the membership formula like:

Σ: edge labels
∆: set of symbols, possibly in Σ
ω: ∆→N: map symbols in ∆ to number of occurrences
   e.g. w₀ = ⦃a, a, a, c, c⦄ means {a:3, c:2, *:0}

      I(ε) = [0;∞]
      I(a[n,m]) = [⌈ω(a)/m⌉;⌊ω(a)/n⌋]
        0/∞ = 0
        i/∞ = 1 for i ≥ 1
  or: I(E₁ ∣ E₂) = I(E₁) ⊕ I(E₂)
        ⊕: pairwise addition: [n₁;m₁]⊕[n₂;m₂]=[n₁+n₂; m₁+m₂]
        m+∞ = ∞+m = ∞
 and: I(E₁ ∥ E₂) = I(E₁) ∩ I(E₂)
        [n₁;m₁]∩[n₂;m₂]=[max(n₁,n₂);min(m₁,m₂)]
              ⎧         [0;∞] if ω∆(E) = ε
      I(E*) = ⎨         [1;∞] if ω∆(E) ≠ ε and I(E) ≠ 0
              ⎩             ∅ otherwise
              ⎧         [0;0] if ω∆(E) = ε
      I(E⁺) = ⎨[1;max(I(E))⌉] if ω∆(E) ≠ ε and I(E) ≠ 0
              ⎩             ∅ otherwise
        all ε∥E* are expressed as E⁺


Example:
 I(a[n,m]) tests
  <S> { :p . } / { <s> :p true }
    ∆={:p}, ω={:p→1}
    I(:p[1,1]) = [⌈1/1⌉;⌊1/1⌋] = [1;1] pass
  <S> { :p . } / { <s> :q true }
    ∆={:p}, ω={:p→0}
    I(:p[1,1]) = [⌈0/1⌉;⌊0/1⌋] = [0;0] fail
?⎧<S> { :p .? } / { <s> :q true }
/⎨  ∆={:p}, ω={:p→0}
0⎩  I(:p[0,1]) = [⌈0/1⌉;⌊0/0⌋] = [0;1] pass (adding rule for 0/0=∞)
  <S> { :p .{2} } / { <s> :p true }
    ∆={:p}, ω={:p→1}
    I(:p[2,2]) = [⌈1/2⌉;⌊1/2⌋] = [1;0] fail
⅔⎧<S> { :p .{2,3} } / { <s> :p 1 }
/⎨  ∆={:p}, ω={:p→1}
1⎩  I(:p[2,3]) = [⌈1/3⌉;⌊1/2⌋] = [1;0] fail
⅔⎧<S> { :p .{2,3} } / { <s> :p 1,2 }
/⎨  ∆={:p}, ω={:p→2}
2⎩  I(:p[2,3]) = [⌈2/3⌉;⌊2/2⌋] = [1;1] pass
⅔⎧<S> { :p .{2,3} } / { <s> :p 1,2 }
/⎨  ∆={:p}, ω={:p→3}
3⎩  I(:p[2,3]) = [⌈3/3⌉;⌊3/2⌋] = [1;2] pass
⅔⎧<S> { :p .{2,3} } / { <s> :p 1,2,3,4 }
/⎨  ∆={:p}, ω={:p→4}
4⎩  I(:p[2,3]) = [⌈4/3⌉;⌊4/2⌋] = [2;2] fail
?/0 is really modeled as I(I(:p[1,1]) ∣ I(ε)) below

  I(ε) tests
  <S> { } / { <s> :p true }
    ∆={:p}, ω={}
    I(ε) = [0;∞] pass
?⎧<S> { :p .? } / { <s> :q true }
/⎨  ∆={:p}, ω={:p→0}
0⎩  I(I(:p[1,1]) ∣ I(ε)) = I([0;0] ∣ [0;∞]) = [0;∞]
⅔⎧<S> { :p .{2,3} } / { <s> :p 1 }
/⎨  ∆={:p}, ω={:p→1}
1⎩  I(:p[2,3]) = [⌈1/3⌉;⌊1/2⌋] = [1;0] fail
⅔⎧<S> { :p .{2,3} } / { <s> :p 1 }
/⎨  ∆={:p}, ω={:p→1}
1⎩  I(I(I(:p[2,2]) ∥ I(I(:p[1,1]) ∣ I(ε)))) =
    I(I([⌈1/2⌉;⌊1/2⌋] ∥ I([⌈0/1⌉;⌊0/1⌋] ∣ [0;∞]))) =
    I(I([1;0] ∥ I([0;0] ∣ [0;∞]))) = I(I([1;0] ∥ [0;∞])) = I([1;0]) fail
⅔⎧<S> { :p .{2,3} } / { <s> :p 1,2 }
/⎨  ∆={:p}, ω={:p→2}
2⎩  I(I(I(:p[2,2]) ∥ I(I(:p[1,1]) ∣ I(ε)))) =
    I(I([⌈2/2⌉;⌊2/2⌋] ∥ I([⌈0/1⌉;⌊0/1⌋] ∣ [0;∞]))) =
    I(I([1;1] ∥ I([0;0] ∣ [0;∞]))) = I(I([1;1] ∥ [0;∞])) = I([1;1]) pass
⅔⎧<S> { :p .{2,3} } / { <s> :p 1,2,3 }
/⎨  ∆={:p}, ω={:p→3}
3⎩  I(I(I(:p[2,2]) ∥ I(I(:p[1,1]) ∣ I(ε)))) =
    I(I([⌈3/2⌉;⌊3/2⌋] ∥ I([⌈0/1⌉;⌊0/1⌋] ∣ [0;∞]))) =
    I(I([2;1] ∥ I([0;0] ∣ [0;∞]))) = I(I([2;1] ∥ [0;∞])) = I([2;1]) fail
     -- overruns if <s> :p 3 assigned to [2,2] group
    I(I([⌈2/2⌉;⌊2/2⌋] ∥ I([⌈1/1⌉;⌊1/1⌋] ∣ [0;∞]))) =
    I(I([1;1] ∥ I([1;1] ∣ [0;∞]))) = I(I([1;1] ∥ [1;∞])) = I([1;1]) pass
     -- accepts if <s> :p 3 assigned to I(I(:p[1,1]) ∣ I(ε))
⅔⎧<S> { :p .{2,3} } / { <s> :p 1,2,3,4 }
/⎨  ∆={:p}, ω={:p→3}
4⎩  I(I(I(:p[2,2]) ∥ I(I(:p[1,1]) ∣ I(ε)))) =
    I(I([⌈4/2⌉;⌊4/2⌋] ∥ I([⌈0/1⌉;⌊0/1⌋] ∣ [0;∞]))) =
    I(I([2;2] ∥ I([0;0] ∣ [0;∞]))) = I(I([2;2] ∥ [0;∞])) = I([2;2]) fail
     -- overruns if <s> :p 4 assigned to [2,2] group
    I(I([⌈3/2⌉;⌊3/2⌋] ∥ I([⌈1/1⌉;⌊1/1⌋] ∣ [0;∞]))) =
    I(I([2;1] ∥ I([1;1] ∣ [0;∞]))) = I(I([2;1] ∥ [1;∞])) = I([2;1]) pass
     -- overruns if <s> :p 4 assigned to I(I(:p[1,1]) ∣ I(ε))

⅔/1, ⅔/2, ⅔/3, ⅔/4 really modeled as I(:p[2,3]) above

I'd continue here but I need help understanding ω∆(E) ≠ ε and I(E) ≠ 0.

-- 
-ericP

office: +1.617.599.3509
mobile: +33.6.80.80.35.59

(eric@w3.org)
Feel free to forward this message to any list for any purpose other than
email address distribution.

There are subtle nuances encoded in font variation and clever layout
which can only be seen by printing this message on high-clay paper.

Received on Thursday, 3 March 2016 22:38:39 UTC