Path: csiph.com!3.us.feeder.erje.net!feeder.erje.net!news.linkpendium.com!news.linkpendium.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From: rockbrentwood@gmail.com
Newsgroups: comp.compilers
Subject: A new formalism for Context-Free Expressions is going to print
Date: Fri, 9 Nov 2018 14:41:49 -0800 (PST)
Organization: Compilers Central
Lines: 44
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <18-11-002@comp.compilers>
Mime-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 8bit
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
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
Xref: csiph.com comp.compilers:2114

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

https://link.springer.com/book/10.1007/978-3-030-02149-8?fbclid=IwAR3Mo3xzUXY
U9HiGZb39ADOyEY9y1ZSMEz0SYMiIOcMEBDvybjEQNHVwITs

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

Chomsky, himself, has been notified of these developments and has received the
news enthusiastically.

The conference presentation of the "co-equalizers" paper.
https://www.scribd.com/document/392094657/Co-Equalizers-and-Tensor-Products-f
or-Idempotent-Semirings

A web-ified version of the PDF. (Still experimenting with doing web-by-PDF).
https://www.scribd.com/document/392539788/CoEquWeb

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
1960's.
https://www.scribd.com/document/392094748/The-evolution-of-recent-development
s-in-formal-language-theory-from-the-1960-s

(And thanks to my friend Lydia for the video.)