Bug 357420

Comment 1 Ed Merks 2011-09-18 10:23:45 EDT

The only real way to address this problem (quadratic or worse performance of state minimization) is to eliminate the step entirely; the basic parts of the algorithm have already been performance tuned to the greatest extent possible and the algorithm itself has basic limitations.  In other words, validation and content recognition could use an NFA instead of a DFA. But that won't happen without several man weeks of effort, which in turn won't happen without associated funding for such work.  And even then, things like <all> also cause a problem in that they result in an exponentially large NFA, so even that would need specialized support beyond what's possible with an NFA.

Comment 2 Tim Kimber 2011-11-29 09:31:55 EST

Ed: Thanks for the clarification. 

Just wondering whether the DFA minimization is an optional step that could be switched off if the client app knows that the performance costs will outweigh the benefits. Can you explain the purpose of the DFA minimization, and what exact benefits it gives?

Comment 3 Ed Merks 2011-11-29 09:45:34 EST

The DFA is required to do subset testing, i.e., to test that a content model is a valid restriction of some base content model.  It's also used to test the unique particle attribution rule.  In theory those could be done with a DFA with epsilon transitions. 

Another possibility is to make all the validations that require the DFA be optional.

Comment 4 Tim Kimber 2012-11-29 11:44:08 EST

Ed, two questions:

1. Can you give a sizing for making the call to XSDNFA.minimize() optional ( I am assuming that the validation code would still work if the XSDNFA.minimize() was not called ).
2. Can you give an off-the-cuff sizing for making the entire validation step optional?

Comment 5 Ed Merks 2012-11-29 12:34:43 EST

Making validations themselves optional is probably 2 days of work.

Making validation work with an NFA is *minimally* 10 days of work. Handling validation for <all> without an exponentially large NFA requires something other than an NFA, i.e., something that involves pruning transitions/states so they can be used at most once. That's a bit more of an open-ended design problem. I imagine a complete design is likely to involve 15 days of work, but until I spend at least 2 days on a preliminary detailed analysis and prototyping, this is just an off-the-cuff sense of the complexity of the problem.

I imagine using an NFA will require keeping track of the set of states for the automaton and to deal with <all>, will require keeping track of disallowed states/transition in addition to that.  It's important to realize that this will move some of the very expensive up front cost of minimization to produce a DFA to the (hopefully much less expensive) validation processing using the NFA instead of a DFA.