CEX - Context-Free Expression Filter: update.

Rock Brentwood <rockbrentwood@gmail.com>
Sun, 4 Apr 2021 16:55:10 -0500

          From comp.compilers

Related articles
CEX - Context-Free Expression Filter markwh04@yahoo.com (2007-02-25)
CEX - Context-Free Expression Filter: update. rockbrentwood@gmail.com (Rock Brentwood) (2021-04-04)
| List of all articles for this month |

From: Rock Brentwood <rockbrentwood@gmail.com>
Newsgroups: comp.compilers
Date: Sun, 4 Apr 2021 16:55:10 -0500
Organization: Compilers Central
References: 07-02-067
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="58492"; mail-complaints-to="abuse@iecc.com"
Keywords: tools, theory
Posted-Date: 04 Apr 2021 21:14:02 EDT

The following is an update of the comp.compilers article

"CEX - Context-Free Expression Filter"
2007 February 25

Both an updated and UTF-8 converted version of the original have been
posted under comp.theory here:


The following cites from the original have been updated:

> In 1993, the regular expression filter REX was introduced. Notable
> amongst its features was that processing was carried out entirely
> within an algebraic paradigm. The utility and the algorithms
> underlying it have eventually found their way into other applications
> (e.g. XML-Query).

This was originally in the comp.compilers archive. The latest updates
may now be found at GitHub under


>CEX is the long-planned successor to REX. It will not handle the full
>range of REX functionality, but will process language expressions at
>the next stage up the Chomsky hierarchy: Context-Free Expressions.
>The Untold Story of Formal Languages
>(Numerous other references may be found on this page, both above and
>below this link)

Currently linked at:

Descriptions only are available, not the PDF's; and has been largely
subsumed both by the following and publications recent and pending
listed in the references (cited in the comp.theory article):

The Algebraic Approach II-V

The new framework for context-free expressions, which is part of a new
algebraic foundation for formal language and automata theory laid out
in recent publications and elsewhere, is a descendant of the algebraic
formulation published in 1963 by Chomsky and Sch├╝tzenberger.

A follow-up note to the 2018 papers that I sent both directly to
Chomsky and as an open letter on the recent developments is here:


An early draft of the presentation for one of the recent publications
may be found here:

Co Equalizers and Tensor Products for Idempotent Semirings

More details may be found in the comp.theory article.

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.