Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Decidability of Definability Issues in the Theory of Real Addition

Bès Alexis, Choffrut Christian

Fundamenta Informaticae

2022

Vol. 188 nr 1

15--39

Given a subset of X ⊆ ℝn we can associate with every point x ∈ ℝn a vector space V of maximal dimension with the property that for some ball centered at x, the subset X coincides inside the ball with a union of lines parallel to V. A point is singular if V has dimension 0. In an earlier paper we proved that a 〈ℝ, +, <, ℤ〉-definable relation X is 〈ℝ, +, <, 1〉-definable if and only if the number of singular points is finite and every rational section of X is 〈R, +, <, 1〉-definable, where a rational section is a set obtained from X by fixing some component to a rational value. Here we show that we can dispense with the hypothesis of X being 〈ℝ, +, <, ℤ〉-definable by requiring that the components of the singular points be rational numbers. This provides a topological characterization of first-order definability in the structure 〈ℝ, +, <, 1〉. It also allows us to deliver a self-definable criterion (in Muchnik's terminology) of 〈ℝ, +, <, 1〉- and 〈ℝ, +, <,ℤ〉-definability for a wide class of relations, which turns into an effective criterion provided that the corresponding theory is decidable. In particular these results apply to the class of so-called k–recognizable relations which are defined by finite Muller automata via the representation of the reals in a integer basis k, and allow us to prove that it is decidable whether a k–recognizable relation (of any arity) is l–recognizable for every base l ≥ 2.

Complexity and (Un)decidability of Fragments of 〈ωωλ;×〉

Bès Alexis, Choffrut Christian

Fundamenta Informaticae

2019

Vol. 164, nr 1

1--15

We specify the frontier of decidability for fragments of the first-order theory of ordinal multiplication. We give a NEXPTIME lower bound for the complexity of the existential fragment of 〈ωω λ; ×,ω,ω+1,ω2+1〉 for every ordinal λ. Moreover, we prove (by reduction from Hilbert Tenth Problem) that the ∃*∀6-fragment of 〈ωω λ; ×〉 is undecidable for every ordinal λ.