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

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> (permalink)
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

Show key headers only | View raw

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

Back to comp.compilers | Previous | Next | Find similar

Thread

A new formalism for Context-Free Expressions is going to print rockbrentwood@gmail.com - 2018-11-09 14:41 -0800

csiph-web