Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTree-Automatic Well-Founded Trees
128
0
0.0
(
0
)
Added by
Markus Lohrey
Publication date
2012
fields
Informatics Engineering
and research's language is
English
Authors
Martin Huschenbett
Ask ChatGPT about the research
No Arabic abstract
We investigate tree-automatic well-founded trees. Using Delhommes decomposition technique for tree-automatic structures, we show that the (ordinal) rank of a tree-automatic well-founded tree is strictly below omega^omega. Moreover, we make a step towards proving that the ranks of tree-automatic well-founded partial orders are bounded by omega^omega^omega: we prove this bound for what we call upwards linear partial orders. As an application of our result, we show that the isomorphism problem for tree-automatic well-founded trees is complete for level Delta^0_{omega^omega} of the hyperarithmetical hierarchy with respect to Turing-reductions.
rate research
Read More
This paper studies tree-automatic ordinals (or equivalently, well-founded linearly ordered sets) together with the ordinal addition operation +. Informally, these are ordinals such that their elements are coded by finite trees for which the linear order relation of the ordinal and the ordinal addition operation can be determined by tree automata. We describe an algorithm that, given two tree-automatic ordinals with the ordinal addition operation, decides if the ordinals are isomorphic.
We consider extensive games with perfect information with well-founded game trees and study the problems of existence and of characterization of the sets of subgame perfect equilibria in these games. We also provide such characterizations for two classes of these games in which subgame perfect equilibria exist: two-player zero-sum games with, respectively, two and three outcomes.
We address questions of logic and expressibility in the context of random rooted trees. Infiniteness of a rooted tree is not expressible as a first order sentence, but is expressible as an existential monadic second order sentence (EMSO). On the other hand, finiteness is not expressible as an EMSO. For a broad class of random tree models, including Galton-Watson trees with offspring distributions that have full support, we prove the stronger statement that finiteness does not agree up to a null set with any EMSO. We construct a finite tree and a non-null set of infinite trees that cannot be distinguished from each other by any EMSO of given parameters. This is proved via set-pebble Ehrenfeucht games (where an initial colouring round is followed by a given number of pebble rounds).
We study density requirements on a given Banach space that guarantee the existence of subsymmetric basic sequences by extending Tsirelsons well-known space to larger index sets. We prove that for every cardinal $kappa$ smaller than the first Mahlo cardinal there is a reflexive Banach space of density $kappa$ without subsymmetric basic sequences. As for Tsirelsons space, our construction is based on the existence of a rich collection of homogeneous families on large index sets for which one can estimate the complexity on any given infinite set. This is used to describe detailedly the asymptotic structure of the spaces. The collections of families are of independent interest and their existence is proved inductively. The fundamental stepping up argument is the analysis of such collections of families on trees.
Finiteness spaces constitute a categorical model of Linear Logic (LL) whose objects can be seen as linearly topologised spaces, (a class of topological vector spaces introduced by Lefschetz in 1942) and morphisms as continuous linear maps. First, we recall definitions of finiteness spaces and describe their basic properties deduced from the general theory of linearly topologised spaces. Then we give an interpretation of LL based on linear algebra. Second, thanks to separation properties, we can introduce an algebraic notion of totality candidate in the framework of linearly topologised spaces: a totality candidate is a closed affine subspace which does not contain 0. We show that finiteness spaces with totality candidates constitute a model of classical LL. Finally, we give a barycentric simply typed lambda-calculus, with booleans ${mathcal{B}}$ and a conditional operator, which can be interpreted in this model. We prove completeness at type ${mathcal{B}}^nto{mathcal{B}}$ for every n by an algebraic method.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
