Thue specifications and their monadic second-order properties

• Autorzy: Knapik T. , Calbrix H.
• Języki publikacji: EN

Abstrakty

EN

This paper introduces oriented Thue specifications and their models which are simple directed edge-labeled graphs. The monadic second-order theory of these models is investigated and shown decidable for the class of suffix-bounded rational oriented Thue specifications. In addition, a characterization of prefix-closed context-free languages is given in terms of oriented Thue specifications.

Słowa kluczowe

EN

string-rewriting; infinite graphs; automata; monadic second-order logic

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 1999
• Tom: Vol. 39, Nr 3
• Strony: 305--325
• Opis fizyczny: bibliogr. 27 poz.

Twórcy

autor

Knapik T.

autor

Calbrix H.

• IREMIA, Universite de la Reunion, BP 7151, 97715 Saint Denis Messageries Cedex 9, Reunion,