Check out the new USENIX Web site.

next up previous
Next: Implementation Up: Text Constraints Previous: Definitions and Constraint Systems

Expressiveness

The theoretical power of TC -- that is, the set of languages that can be matched by a TC expression -- depends on the power of the matchers and parsers it uses. If its matchers and parsers generate only regular languages, then the TC expression is also regular, since regular languages are closed under the TC operators concatenation, intersection, and union [11]. Since context-free languages are not closed under intersection, however, a TC expression using context-free parsers may match a non-context-free language.

A TC constraint system that uses only literals (no regular expressions or external parsers) is less powerful than a regular expression, because TC lacks recursive constraints or repetition operators (such as the * operator). Future work discussed in Section 7 will address this issue.



Robert C. Miller and Brad A. Myers
Mon Apr 26 11:34:19 EDT 1999