Logische Klassifizierung regulärer Sprachen
Die folgenden Begriffe haben genau die gleiche Ausdruckskraft
bei der Beschreibung von Sprachen (von Wörtern und Bäumen):
- endliche Automaten
- reguläre Ausdrücke
- schwache monadische Logik zweiter Stufe
Durch Einschränkung erhalten wir Teiklassen.
Eine interessante Klasse von Wortsprachen sind diejenigen,
die beschrieben werden durch
- aperiodische Automaten
- sternfreie erweiterte reguläre Ausdrücke
- Logik erster Stufe
Diese Klasse wird von der Straubing-Hierarchie ausgeschöpft.
Der Vortrag präsentiert dazugehörige Definitionen,
Sätze und Beweisideen und erwähnt offenen Probleme,
insbesondere beim Übertragen der Begriffe auf Baumsprachen.
Literatur:
- D. Perrin: Finite Automata,
in: Handbook of Theoretical Computer Science, Elsevier, 1990
- J.-E. Pin: Syntactic Semigroups,
in: Handbook of Formal Languages, Springer, 1996
- A. Potthoff: Logische Klassifizierung regulärer Baumsprachen,
Diss., Univ. Kiel, 1994
- W. Thomas: Languages, Automata, and Logic,
in: Handbook of Formal Languages, Springer, 1996
this page is best viewed with
any
browser
http://www.informatik.uni-leipzig.de/~joe/
mailto:joe@informatik.uni-leipzig.de