Home	Trees	Indices	Help	PyXB hosted on

Module fac

source code

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 231-245. 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 sub-automata for each term, and permits an exit transition only when all the terms that are required have been completed.

Home	Trees	Indices	Help	PyXB hosted on