Vocabulary designers / users:

• Draw a picture
• of two content models
• showing what is valid in both models
• what is valid in one but not the other

Computer scientists:

• A simple, practical application of
• Brzozowski derivatives and
• Glushkov automata.

The Igel project is sponsored by the Institut für Deutsche Sprache, Mannheim.

Igel is building tools for comparing document vocabularies.

Given two related DTDs,

• How do they differ?
• How are they the same?
• Have any old documents become invalid?

E.g. XHTML 1.0 Strict vs. Transitional.

E.g. HTML 3.2 vs HTML 4.0.

E.g. JATS 3.1 Archiving vs JATS 4.0 Authoring

E.g. TEI Lite and XCES (or ...)

E.g. Two customizations of Docbook.

E.g. Two versions of MathML.

If we have translated the DTD into XML, we can expand the parameter entities and label the expansions:

Now A has:

<!ELEMENT bibl ( %phrase.seq{{ #PCDATA 
               | %m.phrase{{ 
                   %m.token{{ abbr | date | num 
                    | measure | name | term | time 
                    | }}m.token;
                   foreign | mentioned | distinct 
                   | title | hi | list | corr 
                   | gap | reg | ptr | ref | 
                 }}m.phrase; 
              }}phrase.seq; 
              author)* >

And B has:

<!ELEMENT bibl ( %phrase.seq{{ #PCDATA
               | %m.phrase{{
                   %m.token{{ 
                     %x.token{{ }}x.token;
                     abbr | date | num 
                     | dateRange | numRange | timeRange
                     | measure | name | term | time 
                     | w | }}m.token;
                   corr | distinct | foreign 
                   | gap | hi | list | mentioned
                   | orig | q | ref | reg | s
                   | stage | title | table 
                   | xref | 
                 }}m.phrase; 
               }}phrase.seq; 
               author | 
               %ids.milestones{{ 
                 pb | lb | ptr | xptr 
               }}ids.milestones;)* >

A little better, perhaps, but ...

The simplest method of making an FSA is to construct the Glushkov automaton.

• Each primitive token becomes a state (the state of just having seen that token).
• Define transitions to agree with the regex. (Glushkov, Brüggemann-Klein, Wood).
• Plus one more for start state.
• Mark the final states.

Content models ((a|x|y)*, z) and ((b|x|y)+, z):

In a Glushkov automaton, every path into a state has the same label.

So we can label the states, not the arcs. (Easier to read and understand.)

One state per token clutters up fast. Let's reduce or-groups into single states, but preserve the Glushkov property:

An initial sketch of the goal:

• clarity,* simplicity
• what's valid in both: black/white
• what's valid in just one: red or blue
• determinism is good
• the Glushkov property is good
• each token maps to one state* — no clever stuff

Black/white: paths that work in both FSAs.

Red, blue: paths that work in only one FSA.

The standard way to calculate the intersection of two FSAs:

• Run them both in parallel.
• Do they both accept the string?

Start with the two start states: i.e. state (Start_A, Start_B).

Calculate the next state pair for each symbol.

• (Start_A, Start_B) × a ⇒ ((a|x|y)_A, Error_B). Omit (error state).
• (Start_A, Start_B) × b ⇒ (Error_A, (b|x|y)_B). Omit (error state).
• (Start_A, Start_B) × x ⇒ ((a|x|y)_A, (b|x|y)_B). New state.
• (Start_A, Start_B) × y ⇒ ((a|x|y)_A, (b|x|y)_B). Same new state.
• (Start_A, Start_B) × z ⇒ (z_A, Error_B). Omit (error state).

Continue the same process with any new states.

• ((a|x|y)_A, (b|x|y)_B) × a ⇒ ((a|x|y)_A, Error_B). Omit (error state).
• ((a|x|y)_A, (b|x|y)_B) × b ⇒ (Error_A, (b|x|y)_B). Omit (error state).
• ((a|x|y)_A, (b|x|y)_B) × x ⇒ ((a|x|y)_A, (b|x|y)_B). Known state.
• ((a|x|y)_A, (b|x|y)_B) × y ⇒ ((a|x|y)_A, (b|x|y)_B). Known state.
• ((a|x|y)_A, (b|x|y)_B) × z ⇒ (z_A, z_B). New state.

One more state (all errors — no exit from state):

• (z_A, z_B) × a ⇒ (Error_A, Error_B).
• (z_A, z_B) × b ⇒ (Error_A, Error_B).
• (z_A, z_B) × x ⇒ (Error_A, Error_B).
• (z_A, z_B) × y ⇒ (Error_A, Error_B).
• (z_A, z_B) × z ⇒ (Error_A, Error_B).

We don't want just the intersection.

We also want A and B to be visible.

So instead of discarding any pair containing either Error_A or Error_B, let's discard only the pair (Error_A, Error_B).

If we do that, we get a larger FSA ...

N.B. the McCarthy principle or tainted string approach: once red, always red.

N.B. proliferation of states.

A first attempt at keeping the reduced or-groups of A and B.

We have lost determinism and Glushkov Property.

Can we find another way to reduce state count?

Can we overcome McCarthyism and allow ‘recovery’ from errors?

[N.B. name change: in proceedings, this is color-filter approach.]

Except that strictly speaking, we cannot reduce or-groups now.

Strictly speaking, we cannot reduce or-groups.

All or-groups are long gone!

We are merging states with

• same set of predecessor states;
• same set of successor states;
• same color.

Preserves equivalence, deteminism, Glushkov Property.

A tricolor automaton is an FSA whose

• states,
• arcs, and
• final-state markers

are (independently) colored

• red,
• white, or
• blue

A tricolor automaton is a triple (A, Χ, Φ), where

• A is the underlying finite state automaton (Q, Σ, δ, q₀, F), where

  • Q is a set of states
  • Σ is an input alphabet
  • δ is a transition function mapping from Q × Σ to Q
  • q₀ ∈ Q is the start state
  • F ⊆ Q is the set of final states
• Χ is a chromatic function mapping from Q ∪ δ to the colors {red, white, blue}.
• Φ is a chromatic function mapping from F to the colors {red, white, blue}.

Need more time? http//blackmesatech.com/2015/08/tricolor-automata/

But what does it mean?

• black/white paths = paths legal in both A and B
• red/white paths = paths legal in A
• at least one red state or arc = legal in A, not in B
• blue/white paths = paths legal in B
• at least one blue state or arc = legal in B, not in A

N.B.

• red/white/blue paths ≠ union of A and B (but ...)

The definitions allows some things that don't make ‘sense’:

• red arc to/from blue state (or vice versa)
• arc from red to blue state (or vice versa)
• red final marker on blue state (or vice versa)

N.B. If these things happen, the rules of interpetation still hold.

States: (Start_A, Start_B) plus all triples (σ, P_A, Q_B) where P_A ≠ Start_A and Q_B ≠ Start_B.

Alphabet: union of Σ_A and Σ_B.

Transitions:

• (x, P_A, Q_B) × σ ⇒ (σ, P_A′, Q_B′) iff A has P_A × σ ⇒ P_A′ and A has Q_B × σ ⇒ Q_B′.
• (x, P_A, Q_B) × σ ⇒ (σ, P_A′, Error_B) iff A has P_A × σ ⇒ P_A′ and σ ∉ Σ_B.
• (x, P_A, Q_B) × σ ⇒ (σ, Error_A, Q_B′) iff B has Q_B × σ ⇒ Q_B′ and σ ∉ Σ_A.

Start state: (Start_A, Start_B).

Final states: union of Final_A and Final_B.

Need more time? http//blackmesatech.com/2015/08/tricolor-automata/

State coloring::

• red for (σ, P_A, Error_B)
• blue for (σ, Error_A, Q_B)
• otherwise white.

Arc coloring::

• red if source or target state is red
• blue if source or target state is blue
• otherwise white.

Finality coloring::

• white if P_A ∈ Final_A and Q_B ∈ Final_B.
• red if P_A ∈ Final_A and Q_B ∉ Final_B.
• blue if P_A ∉ Final_A and Q_B ∈ Final_B.

Need more time? http//blackmesatech.com/2015/08/tricolor-automata/

Steps as before, for intersection, but don't throw away partial errors.

Start with (Start_A, Start_B); calculate next state for each symbol.

• (Start_A, Start_B) × a ⇒ (a, (a|x|y)_A, Error_B). Red state.
• (Start_A, Start_B) × b ⇒ (b, Error_A, (b|x|y)_B). Blue state.
• (Start_A, Start_B) × x ⇒ (x, (a|x|y)_A, (b|x|y)_B). White state.
• (Start_A, Start_B) × y ⇒ (y, (a|x|y)_A, (b|x|y)_B). White state.
• (Start_A, Start_B) × z ⇒ (z, z_A, Error_B). Red state.

For each new state; calculate next state for each symbol.

Omitting transitions to (σ, Error_A, Error_B):

• (a, (a|x|y)_A, Error_B) × a ⇒ (a, (a|x|y)_A, Error_B).
• (a, (a|x|y)_A, Error_B) × x ⇒ (x, (a|x|y)_A, Error_B). New red state.
• (a, (a|x|y)_A, Error_B) × y ⇒ (y, (a|x|y)_A, Error_B). New red state.
• (a, (a|x|y)_A, Error_B) × z ⇒ (z, z_A, Error_B).
• (b, Error_A, (b|x|y)_B) × b ⇒ (b, Error_A, (b|x|y)_B).
• (b, Error_A, (b|x|y)_B) × x ⇒ (x, Error_A, (b|x|y)_B). New blue state.
• (b, Error_A, (b|x|y)_B) × y ⇒ (y, Error_A, (b|x|y)_B). New blue state.
• (b, Error_A, (b|x|y)_B) × z ⇒ (z, Error_A, z_B). New blue state.
• (x, (a|x|y)_A, (b|x|y)_B) × a ⇒ (a, (a|x|y)_A, Error_B).
• (x, (a|x|y)_A, (b|x|y)_B) × b ⇒ (b, Error_A, (b|x|y)_B).
• (x, (a|x|y)_A, (b|x|y)_B) × x ⇒ (x, (a|x|y)_A, (b|x|y)_B).
• (x, (a|x|y)_A, (b|x|y)_B) × y ⇒ (y, (a|x|y)_A, (b|x|y)_B).
• (x, (a|x|y)_A, (b|x|y)_B) × z ⇒ (z, z_A, z_B). New white state.
• (y, (a|x|y)_A, (b|x|y)_B) × a ⇒ (a, (a|x|y)_A, Error_B).
• (y, (a|x|y)_A, (b|x|y)_B) × b ⇒ (b, Error_A, (b|x|y)_B).
• (y, (a|x|y)_A, (b|x|y)_B) × x ⇒ (x, (a|x|y)_A, (b|x|y)_B).
• (y, (a|x|y)_A, (b|x|y)_B) × y ⇒ (y, (a|x|y)_A, (b|x|y)_B).
• (y, (a|x|y)_A, (b|x|y)_B) × z ⇒ (z, z_A, z_B). New white state.

Shaded states are old; new ones need to be processed.

For each new state; calculate next state for each symbol.

Omitting transitions to (σ, Error_A, Error_B):

• (x, (a|x|y)_A, Error_B) × a ⇒ (a, (a|x|y)_A, Error_B).
• (x, (a|x|y)_A, Error_B) × x ⇒ (x, (a|x|y)_A, Error_B).
• (x, (a|x|y)_A, Error_B) × y ⇒ (y, (a|x|y)_A, Error_B).
• (x, (a|x|y)_A, Error_B) × z ⇒ (z, z_A, Error_B).

(y, (a|x|y)_A, Error_B) similarly ...

• (x, Error_A, (b|x|y)_B) × b ⇒ (b, Error_A, (b|x|y)_B).
• (x, Error_A, (b|x|y)_B) × x ⇒ (x, Error_A, (b|x|y)_B).
• (x, Error_A, (b|x|y)_B) × y ⇒ (y, Error_A, (b|x|y)_B).
• (x, Error_A, (b|x|y)_B) × z ⇒ (z, Error_A, z_B).

(y, Error_A, (b|x|y)_B) similarly ...

Now we're done.

Replace bookkeeping information with simpler labels:

We've seen this before.

For every state (σ, P_A, Q_B):

• if state (σ, P_A, Error_B) exists, or
• state (σ, Error_A, Q_B) exists,
• with same* successors,

then merge the states. Repeat.

In our example:

• (x, (a|x|y)_A, (b|x|y)_B) ∼ (x, (a|x|y)_A, Error_B), (x, Error_A, (b|x|y)_B), but successors differ
• (y, (a|x|y)_A, (b|x|y)_B) ∼ (y, (a|x|y)_A, Error_B), (y, Error_A, (b|x|y)_B), but successors differ
• (z, z_A, z_B) ∼ (z, z_A, Error_B), (z, Error_A, z_B), with same successors (i.e. none).

Now

• (x, (a|x|y)_A, (b|x|y)_B) ∼ (x, (a|x|y)_A, Error_B), (x, Error_A, (b|x|y)_B), with same* successors
• (y, (a|x|y)_A, (b|x|y)_B) ∼ (y, (a|x|y)_A, Error_B), (y, Error_A, (b|x|y)_B), with same* successors

Now simplify the labels.

For each pair of states (σ₁, P_A, Q_B) and (σ₂, P_A, Q_B) with the same predecessors, successors, and color, merge the states.

Here, the x and y states.