Modular tree automata

Patrick Bahr

doi:10.1007/978-3-642-31113-0_14

Modular tree automata

Patrick Bahr

Department of Computer Science

2 Citations (Scopus)

88 Downloads (Pure)

Abstract

Tree automata are traditionally used to study properties of tree languages and tree transformations. In this paper, we consider tree automata as the basis for modular and extensible recursion schemes. We show, using well-known techniques, how to derive from standard tree automata highly modular recursion schemes. Functions that are defined in terms of these recursion schemes can be combined, reused and transformed in many ways. This flexibility facilitates the specification of complex transformations in a concise manner, which is illustrated with a number of examples.

Original language	English
Title of host publication	Mathematics of Program Construction : 11th International Conference, MPC 2012, Madrid, Spain, June 25-27, 2012. Proceedings
Editors	Jeremy Gibbons, Pablo Nogueira
Number of pages	37
Publisher	Springer
Publication date	2012
Pages	263-299
ISBN (Print)	978-3-642-31112-3
ISBN (Electronic)	978-3-642-31113-0
DOIs	https://doi.org/10.1007/978-3-642-31113-0_14
Publication status	Published - 2012
Event	11th International Conference on Mathematics of Program Construction - Madrid, Spain Duration: 25 Jun 2012 → 27 Jun 2012 Conference number: 11

Conference

Conference	11th International Conference on Mathematics of Program Construction
Number	11
Country/Territory	Spain
City	Madrid
Period	25/06/2012 → 27/06/2012

Series	Lecture notes in computer science
Volume	7342
ISSN	0302-9743

Keywords

Faculty of Science
compiler
tree transducer
deforestation
attribute grammar
syntax-directed

Access to Document

10.1007/978-3-642-31113-0_14

Bahr_2012_Modular_tree_automata_postprintAccepted author manuscript, 339 KB

Cite this

Modular tree automata. / Bahr, Patrick.

Mathematics of Program Construction: 11th International Conference, MPC 2012, Madrid, Spain, June 25-27, 2012. Proceedings. ed. / Jeremy Gibbons; Pablo Nogueira. Springer, 2012. p. 263-299 (Lecture notes in computer science, Vol. 7342).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Bahr, P 2012, Modular tree automata. in J Gibbons & P Nogueira (eds), Mathematics of Program Construction: 11th International Conference, MPC 2012, Madrid, Spain, June 25-27, 2012. Proceedings. Springer, Lecture notes in computer science, vol. 7342, pp. 263-299, 11th International Conference on Mathematics of Program Construction, Madrid, Spain, 25/06/2012. https://doi.org/10.1007/978-3-642-31113-0_14

@inproceedings{d1c3eb64f1b2495e8bd2ee33443e1594,

title = "Modular tree automata",

abstract = "Tree automata are traditionally used to study properties of tree languages and tree transformations. In this paper, we consider tree automata as the basis for modular and extensible recursion schemes. We show, using well-known techniques, how to derive from standard tree automata highly modular recursion schemes. Functions that are defined in terms of these recursion schemes can be combined, reused and transformed in many ways. This flexibility facilitates the specification of complex transformations in a concise manner, which is illustrated with a number of examples.",

keywords = "Faculty of Science, compiler, tree transducer, deforestation, attribute grammar, syntax-directed",

author = "Patrick Bahr",

year = "2012",

doi = "10.1007/978-3-642-31113-0_14",

language = "English",

isbn = "978-3-642-31112-3",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "263--299",

editor = "Jeremy Gibbons and Pablo Nogueira",

booktitle = "Mathematics of Program Construction",

note = "11th International Conference on Mathematics of Program Construction, MPC 2012 ; Conference date: 25-06-2012 Through 27-06-2012",

}

TY - GEN

T1 - Modular tree automata

AU - Bahr, Patrick

N1 - Conference code: 11

PY - 2012

Y1 - 2012

N2 - Tree automata are traditionally used to study properties of tree languages and tree transformations. In this paper, we consider tree automata as the basis for modular and extensible recursion schemes. We show, using well-known techniques, how to derive from standard tree automata highly modular recursion schemes. Functions that are defined in terms of these recursion schemes can be combined, reused and transformed in many ways. This flexibility facilitates the specification of complex transformations in a concise manner, which is illustrated with a number of examples.

AB - Tree automata are traditionally used to study properties of tree languages and tree transformations. In this paper, we consider tree automata as the basis for modular and extensible recursion schemes. We show, using well-known techniques, how to derive from standard tree automata highly modular recursion schemes. Functions that are defined in terms of these recursion schemes can be combined, reused and transformed in many ways. This flexibility facilitates the specification of complex transformations in a concise manner, which is illustrated with a number of examples.

KW - Faculty of Science

KW - compiler

KW - tree transducer

KW - deforestation

KW - attribute grammar

KW - syntax-directed

U2 - 10.1007/978-3-642-31113-0_14

DO - 10.1007/978-3-642-31113-0_14

M3 - Article in proceedings

SN - 978-3-642-31112-3

T3 - Lecture notes in computer science

SP - 263

EP - 299

BT - Mathematics of Program Construction

A2 - Gibbons, Jeremy

A2 - Nogueira, Pablo

PB - Springer

T2 - 11th International Conference on Mathematics of Program Construction

Y2 - 25 June 2012 through 27 June 2012

ER -

Modular tree automata

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this