A new formalism for Context-Free Expressions is going to print

Fri, 9 Nov 2018 14:41:49 -0800 (PST)

          From comp.compilers

Related articles
A new formalism for Context-Free Expressions is going to print rockbrentwood@gmail.com (2018-11-09)
| List of all articles for this month |

From: rockbrentwood@gmail.com
Newsgroups: comp.compilers
Date: Fri, 9 Nov 2018 14:41:49 -0800 (PST)
Organization: Compilers Central
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="59089"; mail-complaints-to="abuse@iecc.com"
Keywords: theory,
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.)

LNCS 11194


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
news enthusiastically.

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.)

Post a followup to this message

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