Ich mache derzeit einige formale Sprachrecherchen mit Sprachklassen über Regular, aber unter Context Free. Ich betrachte Dinge wie umkehrbar gebundene Multicounter-Maschinen, Single-Stack-Counter-Maschinen, deterministische CFLs usw.
Ich frage mich, ob irgendjemand ein gutes Buch oder einen Fragebogen kennt, der die Eigenschaften dieser Sprachen beschreibt. Das meiste, was ich mir anschaue, ist zu dunkel oder zu neu, um es in meinem Hopcroft-Ullman-Buch wiederzugeben, sogar in der Ausgabe von 1979.
Hauptsächlich suche ich, welche Sprachklassen ineinander enthalten sind, die Abschlusseigenschaften dieser Sprachen und die Entscheidbarkeit grundlegender Probleme (F-Probleme) für diese Sprachen.
Einige Beispiele für Dinge, die ich in dieser Referenz nachschlagen würde:
- Werden alle Sprachen, die von umkehrgebundenen Mehrfachzählern akzeptiert werden, auch von nicht umkehrgebundenen Einzelzählern akzeptiert?
- Sind die deterministischen umkehrgebundenen MultiCounter-Sprachen unter linker und rechter Verkettung geschlossen?
- Ist bei Einzelzählern die Universalität bestimmbar?
Dies sind nur Beispielfragen, ich habe viele andere, die in meiner täglichen Arbeit auftauchen.
Als Ausgangspunkt habe ich versucht aufzuspüren, welche Papiere Oscar Ibarras "Umkehr-gebundene Multicounter-Maschinen und ihre Entscheidungsprobleme" zitieren, aber nicht viel gefunden.
quelle
Antworten:
Keine Standardthemen, nein. Und leider habe ich keinen allgemeinen Überblick.
In der Doktorarbeit von Klaus Reinhardt möchte ich jedoch zumindest ein Bild der verschiedenen Familien sehen, die in diesem Bereich leben. Auf Seite 64 finden Sie ein Diagramm des Zoos. Von Petri-Netzen mit Inhibitor-Lichtbögen motiviert, untersucht Reinhardt vorrangige Multizähler mit Einschränkungen, wann Null-Tests durchzuführen sind. Nicht trivial.
Übrigens, Ihre letzte Beispielfrage wurde in diesem Forum von Benutzer Sam Jones diskutiert . Eine weitere Ibarra-Referenz.
quelle