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

Displaying 381 – 400 of 995

Showing per page

Restricted ideals and the groupability property. Tools for temporal reasoning

J. Martínez, P. Cordero, G. Gutiérrez, I. P. de Guzmán (2003)

Kybernetika

In the field of automatic proving, the study of the sets of prime implicants or implicates of a formula has proven to be very important. If we focus on non-classical logics and, in particular, on temporal logics, such study is useful even if it is restricted to the set of unitary implicants/implicates [P. Cordero, M. Enciso, and I. de Guzmán: Structure theorems for closed sets of implicates/implicants in temporal logic. (Lecture Notes in Artificial Intelligence 1695.) Springer–Verlag, Berlin 1999]....

Reverse mathematics of some topics from algorithmic graph theory

Peter Clote, Jeffry Hirst (1998)

Fundamenta Mathematicae

This paper analyzes the proof-theoretic strength of an infinite version of several theorems from algorithmic graph theory. In particular, theorems on reachability matrices, shortest path matrices, topological sorting, and minimal spanning trees are considered.

Signed bits and fast exponentiation

Wieb Bosma (2001)

Journal de théorie des nombres de Bordeaux

An exact analysis is given of the benefits of using the non-adjacent form representation for integers (rather than the binary representation), when computing powers of elements in a group in which inverting is easy. By counting the number of multiplications for a random exponent requiring a given number of bits in its binary representation, we arrive at a precise version of the known asymptotic result that on average one in three signed bits in the non-adjacent form is non-zero. This shows that...

Solving word equations

Habib Abdulrab (1990)

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

Some Algebraic Properties of Machine Poset of Infinite Words

Aleksandrs Belovs (2008)

RAIRO - Theoretical Informatics and Applications

The complexity of infinite words is considered from the point of view of a transformation with a Mealy machine that is the simplest model of a finite automaton transducer. We are mostly interested in algebraic properties of the underlying partially ordered set. Results considered with the existence of supremum, infimum, antichains, chains and density aspects are investigated.

Some problems in automata theory which depend on the models of set theory

Olivier Finkel (2011)

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

We prove that some fairly basic questions on automata reading infinite words depend on the models of the axiomatic system ZFC. It is known that there are only three possibilities for the cardinality of the complement of an ω-language L ( 𝒜 ) L(x1d49c;) accepted by a Büchi 1-counter automaton 𝒜 x1d49c;. We prove the following surprising result: there exists a 1-counter Büchi automaton 𝒜 x1d49c; such that the cardinality of the complement L ( 𝒜 ) - L(𝒜) −  of the ω-language L ( 𝒜 ) L(𝒜) is not determined...

Currently displaying 381 – 400 of 995