All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 3

Displaying 41 – 51 of 51

Showing per page

Theories of orders on the set of words

Dietrich Kuske (2010)

RAIRO - Theoretical Informatics and Applications

It is shown that small fragments of the first-order theory of the subword order, the (partial) lexicographic path ordering on words, the homomorphism preorder, and the infix order are undecidable. This is in contrast to the decidability of the monadic second-order theory of the prefix order [M.O. Rabin, Trans. Amer. Math. Soc., 1969] and of the theory of the total lexicographic path ordering [P. Narendran and M. Rusinowitch, Lect. Notes Artificial Intelligence, 2000] and, in case of the ...

Three generators for minimal writing-space computations

Serge Burckel, Marianne Morillon (2010)

RAIRO - Theoretical Informatics and Applications

We construct, for each integer n, three functions from {0,1}n to {0,1} such that any boolean mapping from {0,1}n to {0,1}n can be computed with a finite sequence of assignations only using the n input variables and those three functions.

Tree Automata and Automata on Linear Orderings

Véronique Bruyère, Olivier Carton, Géraud Sénizergues (2009)

RAIRO - Theoretical Informatics and Applications

We show that the inclusion problem is decidable for rational languages of words indexed by scattered countable linear orderings. The method leans on a reduction to the decidability of the monadic second order theory of the infinite binary tree [9].

Turning Borel sets into clopen sets effectively

Vassilios Gregoriades (2012)

Fundamenta Mathematicae

We present the effective version of the theorem about turning Borel sets in Polish spaces into clopen sets while preserving the Borel structure of the underlying space. We show that under some conditions the emerging parameters can be chosen in a hyperarithmetical way and using this we obtain some uniformity results.

Currently displaying 41 – 51 of 51

Previous Page 3