A pumping lemma for output languages of attributed tree transducers

An attributed tree transducer is a formal model for studying properties of attribute grammars. In this paper we introduce and prove a pumping lemma for output languages of noncircular, producing, and visiting attributed tree transducers. We apply this pumping lemma to gain two results: (1) there is...

Teljes leírás

Elmentve itt :
Bibliográfiai részletek
Szerzők: Kühnemann Armin
Vogler Heiko
Dokumentumtípus: Cikk
Megjelent: 1994
Sorozat:Acta cybernetica 11 No. 4
Kulcsszavak:Számítástechnika, Kibernetika
Tárgyszavak:
Online Access:http://acta.bibl.u-szeged.hu/12534
Leíró adatok
Tartalmi kivonat:An attributed tree transducer is a formal model for studying properties of attribute grammars. In this paper we introduce and prove a pumping lemma for output languages of noncircular, producing, and visiting attributed tree transducers. We apply this pumping lemma to gain two results: (1) there is no noncircular, producing, and visiting attributed tree transducer which computes the set of all monadic trees with exponential height as output and (2) there is a hierarchy of noncircular, producing, and visiting attributed tree transducers with respect to their number of attributes.
Terjedelem/Fizikai jellemzők:261-305
ISSN:0324-721X