Eine Referenz für einen „algebraischeren“ Ansatz für Pushdown-Automaten und CFLs?

17

In dem Buch über die Automatentheorie von Sakarovitch heißt es in der Einleitung zum Abschnitt über Rationalitäten in der freien Gruppe, dass das darin vorgestellte Material "die Grundlage einer wirklich mathematischen Theorie kontextfreier Sprachen" bildet. Dies wird jedoch nicht explizit erwähnt, da kontextfreie Sprachen und Pushdown-Automaten den Rahmen des Buches sprengen.

Mir sind einige Zusammenhänge von freien Gruppen (und insbesondere von dem, was Sakarovitch involutive Monoiden nennt ) mit der Theorie der Pushdown-Automaten und kontextfreien Sprachen bekannt - z. B. die Dyck-Sprache, das Shamir-Theorem usw. Es ist schwierig, eine Quelle zu finden, in der die von Sakarovitch erwähnte "wirklich mathematische Theorie der kontextfreien Sprachen" tatsächlich aufgebaut ist.

Das nächste, was ich gefunden habe, ist Berstels Buch über Transduktionen und kontextfreie Sprachen. Auf den ersten Blick scheint mir jedoch, dass Pushdown-Automaten in diesem Buch nur am Rande behandelt werden, während die Theorie der rationalen Teilmengen einer freien Gruppe überhaupt nicht angewendet wird. Vielleicht ist das von mir gesuchte Material für Eilenbergs Band C bestimmt, aber da bin ich mir auch nicht sicher.

Deshalb möchte ich um einen Hinweis auf ein Buch, eine Umfrage oder vielleicht eine Reihe von Artikeln bitten, aus denen ich etwas über die "wahrhaft mathematische Theorie der kontextfreien Sprachen" von Sakarovitch und ihre Beziehungen zu freien Gruppen und deren Vernunft lernen kann Teilmengen. Oder suche ich etwas, das es eigentlich nicht gibt?

Jára Cimrman
quelle

Antworten:

9

Sakarovitch promovierte 1976 unter dem Titel Monoïdes syntactiques et languages ​​algébriques (syntaktische Monoide und algebraische Sprachen) zu diesem Thema. Zu dieser Zeit führte dies zur Definition von spitzen Monoiden (siehe z. B. seine MFCS'75-Veröffentlichung ). Um die 80er Jahre verlagerte sich das algebraische Objekt der Wahl, um CFLs zu studieren, auf die Hotz-Gruppe - Sakarovitch hat sogar einen Aufsatz zu diesem Thema in Acta. Inf. Soweit ich weiß, haben spitze Monoide nicht die Aufmerksamkeit erhalten, die sie verdient haben, obwohl die gleichen Ideen bei Behle, Krebs et al. ; Ebenso könnten einige neuere Ansätze, die auf komplexeren Werkzeugen basieren, insbesondere die Stone-Dualität, einen soliden Rahmen für solche Studien bieten.

Ein anderer moderner Ansatz ist der von Clark über das syntaktische Konzeptgitter , mit dem ich nicht vertraut bin.

Was die tatsächlichen Absichten des Autors betrifft, besteht ein sicherer Weg darin, ihn direkt zu fragen.

Michaël Cadilhac
quelle