An Upper Bound on the Space Complexity of Random Formulae in Resolution
We prove that, with high probability, the space complexity of refuting a random unsatisfiable Boolean formula in k-CNF on n variables and m = Δn clauses is .
Annihilators and deductive systems in commutative Hilbert algebras
The properties of deductive systems in Hilbert algebras are treated. If a Hilbert algebra considered as an ordered set is an upper semilattice then prime deductive systems coincide with meet-irreducible elements of the lattice of all deductive systems on and every maximal deductive system is prime. Complements and relative complements of are characterized as the so called annihilators in .
Annihilators in BCK-algebras
We introduce the concepts of an annihilator and a relative annihilator of a given subset of a BCK-algebra . We prove that annihilators of deductive systems of BCK-algebras are again deductive systems and moreover pseudocomplements in the lattice of all deductive systems on . Moreover, relative annihilators of with respect to are introduced and serve as relative pseudocomplements of w.r.t. in .
Anzahlquantoren in der Prädikatenlogik
Application de l'étude de certaines congruences à un problème de décidabilité
Approches des grammaires catégorielles
Étant donné l'importance que prennent les grammaires catégorielles dans le domaine de la linguistique computationnelle, il nous a semblé intéressant de dresser un panorama sur cette question. Nous espérons fournir, aux chercheurs intéressés, un matériau de base susceptible de les aider à approfondir par eux-mêmes le sujet.
Approximable concepts, Chu spaces, and information systems.
Approximation theory of uniqueness conditions by existence conditions
Arithmetic over the rings of all algebraic integers.
Automated theorem proving in monadic predicate calculus
Automatic risk control based on FSA methodology adaptation for safety assessment in intelligent buildings
The main area which Formal Safety Assessment (FSA) methodology was created for is maritime safety. Its model presents quantitative risk estimation and takes detailed information about accident characteristics into account. Nowadays, it is broadly used in shipping navigation around the world. It has already been shown that FSA can be widely used for the assessment of pilotage safety. On the basis of analysis and conclusion on the FSA approach, this paper attempts to show that the adaptation of this...
Automatické formování hypotéz metodou GUHA - teorie a aplikace
Autonomous posets and quantales
Axiomatic foundations of the kinematics common to classical physics and special relativity
Axiomatisation des manipulations symboliques en calcul des prédicats
Axiomatizability in fuzzy logic
Axiomatizability of second order arithmetic with ω-rule
Axiomatization and undecidability results for linear betweenness relations
Axiomatizing omega and omega-op powers of words
In 1978, Courcelle asked for a complete set of axioms and rules for the equational theory of (discrete regular) words equipped with the operations of product, omega power and omega-op power. In this paper we find a simple set of equations and prove they are complete. Moreover, we show that the equational theory is decidable in polynomial time.
Axiomatizing omega and omega-op powers of words
In 1978, Courcelle asked for a complete set of axioms and rules for the equational theory of (discrete regular) words equipped with the operations of product, omega power and omega-op power. In this paper we find a simple set of equations and prove they are complete. Moreover, we show that the equational theory is decidable in polynomial time.