Home  Trees  Indices  Help 



This module provides Finite Automata with Counters.
FACs are type of state machine where a transition may include a constraint and a modification to a set of counters. They are used to implement regular expressions with numerical constraints, as are found in POSIX regexp, Perl, and XML schema.
The implementation here derives from Regular Expressions with Numerical Constraints and Automata with Counters, Dag Hovland, Lecture Notes in Computer Science, 2009, Volume 5684, Theoretical Aspects of Computing  ICTAC 2009, Pages 231245. In what follows, this reference will be denoted HOV09.
A regular expression is directly translated into a term tree, where nodes are operators such as sequence, choice, and counter restrictions, and the leaf nodes denote symbols in the language of the regular expression.
In the case of XML content models, the symbols include element declarations and wildcard elements. A numerical constraint node corresponds to an XML particle, and choice and sequence nodes derive from model groups of types choice and sequence. As suggested in The Membership Problem for Regular Expressions with Unordered Concatenation and Numerical Constraints the all content model can be translated into state machine using choice and sequence at the cost of a quadratic size explosion. Since some XML content models might have a hundred terms in an unordered catenation, this is not acceptable, and the implementation here optimizes this construct by creating a leaf node in the automaton which in turn contains subautomata for each term, and permits an exit transition only when all the terms that are required have been completed.
Note: In XSD 1.1 the restriction that terms in an all model group occur at most once has been removed. Since the current implementation removes a completed term from the set of available terms, this will not work: instead the subconfiguration with its counter values must be retained between matches.


FACError  
InvalidTermTreeError Exception raised when a FAC term tree is not a tree. 

UpdateApplicationError Exception raised when an unsatisfied update instruction is executed. 

AutomatonStepError Symbol rejected by Configuration_ABC.step. 

UnrecognizedSymbolError Configuration.step failed to find a valid transition. 

NondeterministicSymbolError Configuration.step found multiple transitions. 

SymbolMatch_mixin Mixin used by symbols to provide a custom match implementation. 

State A thin wrapper around an object reference. 

CounterCondition A counter condition is a range limit on valid counter values. 

UpdateInstruction An update instruction pairs a counter with a mutation of that counter. 

Transition Representation of a FAC state transition. 

Configuration_ABC Base class for something that represents an Automaton in execution. 

Configuration The state of an Automaton in execution. 

MultiConfiguration Support parallel execution of state machine. 

Automaton Representation of a Finite Automaton with Counters. 

Node Abstract class for any node in the term tree. 

MultiTermNode Intermediary for nodes that have multiple child nodes. 

LeafNode Intermediary for nodes that have no child nodes. 

NumericalConstraint A term with a numeric range constraint. 

Choice A term that may be any one of a set of terms. 

Sequence A term that is an ordered sequence of terms. 

All A term that is an unordered sequence of terms. 

Symbol A leaf term that is a symbol. 


log_ = <logging.Logger object>


__package__ =

Home  Trees  Indices  Help 


Generated by Epydoc 3.0.1 on Sun Sep 18 22:33:49 2016  http://epydoc.sourceforge.net 