|A new formalism for Context-Free Expressions is going to print firstname.lastname@example.org (2018-11-09)|
|Date:||Fri, 9 Nov 2018 14:41:49 -0800 (PST)|
|Injection-Info:||gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="59089"; mail-complaints-to="email@example.com"|
|Posted-Date:||09 Nov 2018 21:51:34 EST|
The first of a series of papers, reestablishing much of formal language and
automata theory on a categorical foundation and applying this to the issue of
developing a framework for "type 2"-ism analogous to the "regular expression"
framework for "type 3"-ism has now been published.
This framework is applicable to all things that are type-2 in flavor (e.g.
context-free languages, syntax directed translations, inter-procedural control
flow analysis, recursive schemata, etc.)
Two algebraic formalisms for the type-2 level of the Chomsky hierarchy emerged
over the past 10 years; their equivalence has been established and the way has
been set to a new theory of context-free expressions, formalising what I've
made mention of here frequently over the past 30 years. The representation is
both an application and culmination of the Chomsky-Schuetzenberger Theorem and
provides a seamless upward extension of regular expressions.
Example 10 of the "co-equalizer" paper is of particular interest and shows the
Chomsky, himself, has been notified of these developments and has received the
The conference presentation of the "co-equalizers" paper.
A web-ified version of the PDF. (Still experimenting with doing web-by-PDF).
A discussion (addressed as a reply to Chomsky) of "how we got here" -- with
all the algebraic formalisms from the 1960's onward. This will be upgraded and
more directly tied into the presentations.
The evolution of recent developments in formal language theory from the
(And thanks to my friend Lydia for the video.)
Return to the
Search the comp.compilers archives again.