An application of the Ehrenfeucht-Fraisse game in formal language theory
An improved inductive definition of two restricted classes of triangulations of the plane
Analyses of languages accepted by varietor machines in category
Analytic determinacy and 0# A forcing-free proof of Harrington’s theorem
We prove the following theorem: Given a⊆ω and , if for some and all u ∈ WO of length η, a is , then a is . We use this result to give a new, forcing-free, proof of Leo Harrington’s theorem: -Turing-determinacy implies the existence of .
Anmerkungen zum Rekursionstheorem.
Another simplification of the recursion scheme.
Aperiodic words on three symbols.
Aperiodic words on three symbols. II.
Aperiodic words on three symbols. III.
Arithmetical classification of the set of all provably recursive functions
The set of all indices of all functions provably recursive in any reasonable theory is shown to be recursively isomorphic to , where is -complete set.
Arithmetical m-degrees.
Arithmetische Prädikate über einem Bereich endlicher Automaten.
Asymptotic density, computable traceability, and 1-randomness
Let r ∈ [0,1]. A set A ⊆ ω is said to be coarsely computable at density r if there is a computable function f such that {n | f(n) = A(n)} has lower density at least r. Our main results are that A is coarsely computable at density 1/2 if A is computably traceable or truth-table reducible to a 1-random set. In the other direction, we show that if a degree a is hyperimmune or PA, then there is an a-computable set which is not coarsely computable at any positive density.
Asymptotical behaviour of some non-uniform measures
Automata, Borel functions and real numbers in Pisot base
This note is about functions ƒ : Aω → Bω whose graph is recognized by a Büchi finite automaton on the product alphabet A x B. These functions are Baire class 2 in the Baire hierarchy of Borel functions and it is decidable whether such function are continuous or not. In 1920 W. Sierpinski showed that a function is Baire class 1 if and only if both the overgraph and the undergraph of f are Fσ. We show that such characterization is also true for functions on infinite words if we replace the real...
Automata-based representations for infinite graphs
New compact representations of infinite graphs are investigated. Finite automata are used to represent labelled hyper-graphs which can be also multi-graphs. Our approach consists of a general framework where vertices are represented by a regular prefix-free language and edges are represented by a regular language and a function over tuples. We consider three different functions over tuples: given a tuple the first function returns its first difference, the second one returns its suffix and the last...
Automata-based Representations for Infinite Graphs
New compact representations of infinite graphs are investigated. Finite automata are used to represent labelled hyper-graphs which can be also multi-graphs. Our approach consists of a general framework where vertices are represented by a regular prefix-free language and edges are represented by a regular language and a function over tuples. We consider three different functions over tuples: given a tuple the first function returns its first difference, the second one returns its suffix and...
Automatic listing of important observational statements. I
Automatic listing of important observational statements. II
Automatic listing of important observational statements. III