Computing on a free tree via complexity-preserving mappings (Q1098314)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Computing on a free tree via complexity-preserving mappings |
scientific article; zbMATH DE number 4037245
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Computing on a free tree via complexity-preserving mappings |
scientific article; zbMATH DE number 4037245 |
Statements
Computing on a free tree via complexity-preserving mappings (English)
0 references
1987
0 references
The relationship between linear lists and free trees is studied. We examine a number of well-known data structures for computing functions on linear lists and show that they can be canonically transformed into data structures for computing the same functions defined over free trees. This is used to establish new upper bounds on the complexity of several query- answering problems.
0 references
abstract data types
0 references
inverse Ackermann function
0 references
linear lists
0 references
free trees
0 references
query-answering
0 references
