Formal Semantics and Abstract Properties of String Pattern Operations and Extended Formal Language Description Mechanisms
A. C. Fleck, R. S. Limaye · SIAM Journal on Computing · 1983
Two formal models of string patterns are introduced. One is based on an idealization of patterns as systems of set equations, and the other is based on an abstract procedure model of a pattern. Each model is then shown to yield certain insights and in particular is used to explore an operation not commonly considered in conjunction with string patterns. These two new pattern operations are (set) complementation and reversal of cursor direction. Each is shown to have a dramatic effect on both the expressive power and the complexity of patterns in which they are included. These pattern operations may in turn be regarded as extensions to the usual formal language definition mechanisms (i.e., grammars and equation systems), and our results interpreted in terms of formal language description.