A Hierarchy of Deterministic Top-down Tree Transformations

Thumbnail Image
Date
1993-04-13
Authors
Slutzki, Giora
Vagvolgyi, Sandor
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Authors
Research Projects
Organizational Units
Organizational Unit
Computer Science

Computer Science—the theory, representation, processing, communication and use of information—is fundamentally transforming every aspect of human endeavor. The Department of Computer Science at Iowa State University advances computational and information sciences through; 1. educational and research programs within and beyond the university; 2. active engagement to help define national and international research, and 3. educational agendas, and sustained commitment to graduating leaders for academia, industry and government.

History
The Computer Science Department was officially established in 1969, with Robert Stewart serving as the founding Department Chair. Faculty were composed of joint appointments with Mathematics, Statistics, and Electrical Engineering. In 1969, the building which now houses the Computer Science department, then simply called the Computer Science building, was completed. Later it was named Atanasoff Hall. Throughout the 1980s to present, the department expanded and developed its teaching and research agendas to cover many areas of computing.

Dates of Existence
1969-present

Related Units

Journal Issue
Is Version Of
Versions
Series
Department
Abstract

The classes DTA, DTT, DTT{DR}, and DTT{R} stand for the family of tree transductions induced by all deterministic top-down tree automata, deterministic top-down tree transducers, deterministic top-down tree transducers with deterministic top-down look-ahead, and deterministic top-down tree transducers with regular look-ahead, respectively. In this paper we study two hierarchies obtained by compositions of tree transformation classes and show that they are proper and that they ``shuffle perfectly''. Using these results we show that the problem of determining the correct inclusion relationship between two arbitrary compositions of tree transformation classes from the set M={ DTA, DTT, DTT{DR}, DTT{R} } can be decided in linear time.

Comments
Description
Keywords
Citation
DOI
Source
Subject Categories
Copyright
Collections