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 6 Next

Displaying 101 – 120 of 126

Showing per page

Time and space complexity of reversible pebbling

Richard Královič (2010)

RAIRO - Theoretical Informatics and Applications

This paper investigates one possible model of reversible computations, an important paradigm in the context of quantum computing. Introduced by Bennett, a reversible pebble game is an abstraction of reversible computation that allows to examine the space and time complexity of various classes of problems. We present a technique for proving lower and upper bounds on time and space complexity for several types of graphs. Using this technique we show that the time needed to achieve optimal space for...

Traces of term-automatic graphs

Antoine Meyer (2008)

RAIRO - Theoretical Informatics and Applications

In formal language theory, many families of languages are defined using either grammars or finite acceptors. For instance, context-sensitive languages are the languages generated by growing grammars, or equivalently those accepted by Turing machines whose work tape's size is proportional to that of their input. A few years ago, a new characterisation of context-sensitive languages as the sets of traces, or path labels, of rational graphs (infinite graphs defined by sets of finite-state...

Universality of Reversible Hexagonal Cellular Automata

Kenichi Morita, Maurice Margenstern, Katsunobu Imai (2010)

RAIRO - Theoretical Informatics and Applications

We define a kind of cellular automaton called a hexagonal partitioned cellular automaton (HPCA), and study logical universality of a reversible HPCA. We give a specific 64-state reversible HPCA H1, and show that a Fredkin gate can be embedded in this cellular space. Since a Fredkin gate is known to be a universal logic element, logical universality of H1 is concluded. Although the number of states of H1 is greater than those of the previous models of reversible CAs having universality,...

Wadge degrees of ω -languages of deterministic Turing machines

Victor Selivanov (2003)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We describe Wadge degrees of ω -languages recognizable by deterministic Turing machines. In particular, it is shown that the ordinal corresponding to these degrees is ξ ω where ξ = ω 1 CK is the first non-recursive ordinal known as the Church–Kleene ordinal. This answers a question raised in [2].

Wadge Degrees of ω-Languages of Deterministic Turing Machines

Victor Selivanov (2010)

RAIRO - Theoretical Informatics and Applications

We describe Wadge degrees of ω-languages recognizable by deterministic Turing machines. In particular, it is shown that the ordinal corresponding to these degrees is ξω where ξ = ω1CK is the first non-recursive ordinal known as the Church–Kleene ordinal. This answers a question raised in [2].

What machines can and cannot do.

Luis M. Laita, Roanes-Lozano, Luis De Ledesma Otamendi (2007)

RACSAM

In this paper, the questions of what machines cannot do and what they can do will be treated by examining the ideas and results of eminent mathematicians. Regarding the question of what machines cannot do, we will rely on the results obtained by the mathematicians Alan Turing and Kurt G¨odel. Turing machines, their purpose of defining an exact definition of computation and the relevance of Church-Turing thesis in the theory of computability will be treated in detail. The undecidability of the “Entscheidungsproblem”...

Currently displaying 101 – 120 of 126