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

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

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