Symmetric and Antisymmetric Regular Expressions
Anmol Singh Gill · SIAM Journal on Applied Mathematics · 1970
In this paper the “dual” of a binary regular expression is defined as the same expression with 0’s and 1’s interchanged. The “duals” of tapes and events are defined analogously, and various properties and interrelations associated with duality are developed. On the basis of these definitions, two classes of regular expressions are introduced—the “symmetric” and the “antisymmetric” regular expressions (these classes are shown to be infinite). A symmetric expression is one whose dual represents the same event, while an antisymmetric expression is one whose dual represents the complement of the same event. Thus, the acceptor of an event represented by a symmetric expression is invariant under input complementation, while the acceptor of an event represented by an antisymmetric expression is invariant under simultaneous complementation of input and output. It is shown that the class of symmetric expressions is closed under regular operations, while the class of antisymmetric expressions is closed only under set complementation. It is also shown that every symmetric expression is equivalent to the union of two nonintersecting mutually-dual expressions, and hence that the acceptor of the event represented by a symmetric expression can be realized by an interconnection (using one OR gate and one inverter) of two identical automata. Definitions and characterizations are given for “symmetric” and “antisymmetric” automata which are shown to accept symmetric and antisymmetric expressions, respectively. On the basis of these automata, algorithms are formulated for deciding whether or not a given expression is symmetric or antisymmetric. Finally, it is shown that the acceptor of any regular event can be realized (in two different ways) as an interconnection (using one OR gate and one AND gate) of three automata—two of which are symmetric and the third antisymmetric.