Path Languages of Random Permitting Context Tree Grammars are Regular

• Autorzy: Drewes F. , van der Merwe B.
• Języki publikacji: EN

Abstrakty

EN

The path languages of random permitting context tree languages are investigated. The main result is that these path languages are regular. This confirms a previous conjecture.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 82, nr 1-2
• Strony: 47--60
• Opis fizyczny: bibliogr. 7 poz.

Twórcy

autor

Drewes F.

autor

van der Merwe B.

• Department of Computing Science, Umea University, S-901 87 Umea, Sweden,

Bibliografia

• [1] Dassow, J., Păun, G.: Regulated Rewriting in Formal Language Theory, EATCS Monographs in Theoretical Computer Science, Springer, Berlin, 1989, ISBN 3-540-51414-7.
• [2] Drewes, F.: Grammatical Picture Generation - A Tree-Based Approach, Texts in Theoretical Computer Science. An EATCS Series, Springer, 2006.
• [3] Drewes, F., Ewert, S., H¨ogberg, J., van der Merwe, B., du Toit, C., Walt, A. P. v. d.: Random Context Tree Grammars and Tree Transducers, South African Computer Journal, 34, 2005, 11-25.
• [4] Ewert, S., Walt, A. P. v. d.: Generating Pictures using Random Permitting Context, International Journal of Pattern Recognition and Artificial Intelligence, 13, 1999, 339-355.
• [5] Ewert, S., Walt, A. P. v. d.: Random Context Picture Grammars, Publicationes Mathematicae (Debrecen), 54 (Supp), 1999, 763-786.
• [6] Mezei, J.,Wright, J. B.: Algebraic Automata and Context-Free Sets, Information and Control, 11, 1967, 3-29.
• [7] Walt, A. P. v. d.: Random Context Languages, Information Processing, 71, 1972, 66-68.