NDLI: Compositions of n tree transducers

Please wait, while we are loading the content...

Subrecursive program schemata I & II(I. Undecidable equivalence problems, II. Decidable equivalence problems)

Characterizations of flowchartable recursions short version

Recursion schemes with lists

Flowchart schemata with counters

Program schemas with equality

On the equivalence of schemes

Time-bounded random access machines

Predecessor machines and regressing functions

Polynomial evaluation via the division algorithm the fast Fourier transform revisited

On the additions necessary to compute certain functions

A bound on the multiplication efficiency of iteration

Algorithms for rational function arithmetic operations

Linear time bounds for median computations

Rapid identification of repeated patterns in strings, trees and arrays

Binary search trees of bounded balance

Worst-case analysis of memory allocation algorithms

Maze recognizing automata (Extended Abstract)

Turing machines and the spectra of first-order formulas with equality

The process complexity and effective random tests.

The computation of finite functions

Program size and economy of descriptions: Preliminary Report

A hierarchy for nondeterministic time complexity

A patent problem for abstract programming languages; machine-independent computations

Compositions of n tree transducers

Uniformly erasable AFL

Developmental systems and languages

Validating register allocations for straight line programs

Flow graph reducibility

A technique for speeding up LR(k) parsers

Compositions of n tree transducers

Content Provider	ACM Digital Library
Author	Ogden, W. F. Rounds, W. C.
Abstract	Top-down tree transductions, introduced as models of syntax-directed translations and transformational grammars in [12] and [11], are not closed under relational composition. However, closure under relational composition is not always needed; for example, in establishing closure properties of surface sets.(Surface sets are tree-languages obtained as ranges of transductions.) One such closure property, whether the image of a surface set under a transduction is a surface set, remained open. In this paper, we show that transductions need not preserve surface sets. In fact, we exhibit a hierarchy of tree languages obtained by successive transductions. We do not have a good proof that the hierarchy inclusions are proper, but there are strong reasons for so suspecting. As is customary in tree automata papers, we spend some effort on notation. This time, we present a list of first-order axioms for plane (ordered) trees. The Gorn-Brainerd-Doner representation of trees as prefix-closed sets of sequences ([5],[2],[3]) really is a representation in the sense that any (well-founded) abstract tree satisfying our axioms is isomorphic to a prefix-closed set. We then adopt Rosen's notation [10] for trees in subsequent definitions. In our opinion, however, a universally acceptable notation remains to be discovered.
Starting Page	198
Ending Page	206
Page Count	9
File Format	PDF
DOI	10.1145/800152.804915
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1972-05-01
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in