Path: utzoo!attcan!uunet!wuarchive!udel!burdvax!dbs
From: dbs@PRC.Unisys.COM (David Searls)
Newsgroups: comp.theory
Subject: Dyck sets
Keywords: Dyck, semi-Dyck, context-free
Message-ID: <14668@burdvax.PRC.Unisys.COM>
Date: 3 Aug 90 14:20:48 GMT
Sender: news@PRC.Unisys.COM
Lines: 16

A theorem by Chomsky and Schutzenberger established the equivalence of
ANY context-free language to a homomorphic image of the intersection
of some regular language with a semi-Dyck set.  (See, for instance,
Harrison chapter 10.4).  A semi-Dyck set is a language consisting of 
strings of well-balanced parentheses, brackets, braces, etc. so that
the string "[()({}())]([])" is a member of the semi-Dyck set of size
three (i.e. three types of parens), whereas "[()[" is not.

Can anyone tell me what befalls this theorem if, instead of semi-Dyck
sets, the full or two-sided Dyck sets are allowed?  These also allow
cancellation of like parens facing opposite, e.g. "(][)}{" is in a
two-sided Dyck set.  I believe the proofs I have seen fall apart,
but I haven't seen any better characterization of what happens.  I
would appreciate any references that bear on this.

David Searls, dbs@prc.unisys.com