Abstract | ||
---|---|---|
In order to investigate the structure of computable functions over (binary) trees, we define two classes of recursive tree functions by extending the notion of recursive functions over natural numbers in two different ways, and also define the class of functions computable by whileprograms over trees. Then we show that those classes coincide with the class of conjugates of recursive functions over natural numbers via a standard coding function (between trees and natural numbers). We also study what happens when we change the coding function, and present a necessary and sufficient condition for a coding function to satisfy the property above mentioned. |
Year | DOI | Venue |
---|---|---|
2000 | 10.1007/3-540-44464-5_20 | ASIAN |
Keywords | Field | DocType |
computable tree functions,sufficient condition,different way,standard coding function,recursive tree function,functions computable,coding function,recursive function,natural number,computable function,satisfiability,binary tree | Discrete mathematics,Combinatorics,Natural number,Primitive recursive function,Recursive set,Binary tree,μ operator,Recursive tree,Computable function,Mathematics,Binary number | Conference |
Volume | ISSN | ISBN |
1961 | 0302-9743 | 3-540-41428-2 |
Citations | PageRank | References |
1 | 0.40 | 1 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Masahiro Kimoto | 1 | 6 | 2.52 |
Masako Takahashi | 2 | 281 | 44.43 |