Search results for "Computer Science::Logic in Computer Science"
showing 10 items of 72 documents
Left-star order structure of Rickart *-rings
2015
Janowitz proved in 1983 that the initial segments of a Rickart *-ring with the star order are orthomodular posets. In this paper, the same result is proved for the left-star order , which was introduced by Marovtet al., by finding an orthogonality which corresponds to in a certain way and then applying a result proved by Cīrulis which states that the initial segments of any quasi-orthomodular set are orthomodular.
The expansion $\star$ mod $\bar{o}(\hbar^4)$ and computer-assisted proof schemes in the Kontsevich deformation quantization
2019
The Kontsevich deformation quantization combines Poisson dynamics, noncommutative geometry, number theory, and calculus of oriented graphs. To manage the algebra and differential calculus of series of weighted graphs, we present software modules: these allow generating the Kontsevich graphs, expanding the noncommutative & x22c6;-product by using a priori undetermined coefficients, and deriving linear relations between the weights of graphs. Throughout this text we illustrate the assembly of the Kontsevich & x22c6;-product up to order 4 in the deformation parameter Already at this stage, the & x22c6;-product involves hundreds of graphs; expressing all their coefficients via 149 w…
Tally languages accepted by Monte Carlo pushdown automata
1997
Rather often difficult (and sometimes even undecidable) problems become easily decidable for tally languages, i.e. for languages in a single-letter alphabet. For instance, the class of languages recognizable by 1-way nondeterministic pushdown automata equals the class of the context-free languages, but the class of the tally languages recognizable by 1-way nondeterministic pushdown automata, contains only regular languages [LP81]. We prove that languages over one-letter alphabet accepted by randomized one-way 1-tape Monte Carlo pushdown automata are regular. However Monte Carlo pushdown automata can be much more concise than deterministic 1-way finite state automata.
La ontología de la proposición en el Russell de "The Principles of Mathematics" y los artículos de Meinong
2005
Bertrand Russell, in The Principles of Mathematics and ¿Meinong¿s Theory of Complexes and Assumptions¿, maintains a unitary conception of the ontology of propositions. He makes a difference between judgment and proposition. Propositions are independent entities and they have different presentations. False propositions subsist; this is related to the relation in the proposition called ¿affirmation¿ and the double condition of predicates (meaning and term). But that conception has bad consequences for the unity and identity of proposition.
Query automata
1999
A main task in document transformation and information retrieval is locating subtrees satisfying some pattern. Therefore, unary queries, i.e., queries that map a tree to a set of its nodes, play an important role in the context of structured document databases. We want to understand how the natural and well-studied computation model of tree automata can be used to compute such queries. We define a query automaton (QA) as a deterministic two-way finite automaton over trees that has the ability to select nodes depending on the state and the label at those nodes. We study QAs over ranked as well as over unranked trees. Unranked trees differ from ranked ones in that there is no bound on the num…
Negative results in the theory of games with lexicographic utilities
2003
When players may have lexicographic utilities, there are: (i) extensive games having a non-empty set of equilibria but empty sets of sequentially rational, sequential and perfect equilibria (ii) normal form games having a non-empty set of equilibria but an empty set of proper equilibria and no stable set of equilibria and (iii) two extensive games having the same normal form representation and disjoint sets of sequential equilibria.
Some Computational Aspects of DISTANCE-SAT
2007
In many AI fields, one must face the problem of finding a solution that is as close as possible to a given configuration. This paper addresses this problem in a propositional framework. We introduce the decision problem distance-sat, which consists in determining whether a propositional formula admits a model that disagrees with a given partial interpretation on at most d variables. The complexity of distance-sat and of several restrictions of it are identified. Two algorithms based on the well-known Davis/Logemann/Loveland search procedure for the satisfiability problem sat are presented so as to solve distance-sat for CNF formulas. Their computational behaviors are compared with the ones …
How to Enrich Description Logics with Fuzziness
2017
International audience; The paper describes the relation between fuzzy and non-fuzzy description logics. It gives an overview about current research in these areas and describes the difference between tasks for description logics and fuzzy logics. The paper also deals with the transformation properties of description logics to fuzzy logics and backwards. While the process of transformation from a description logic to a fuzzy logic is a trivial inclusion, the other way of reducing information from fuzzy logic to description logic is a difficult task, that will be topic of future work.
Full CNF Encoding: The Counting Constraints Case
2004
Many problems are naturally expressed using CNF clauses and boolean cardinality constraints. It is generally believed that solving such problems through pure CNF encoding is inefficient, so many authors has proposed specialized algorithms : the pseudo-boolean solvers. In this paper we show that an appropriate pure CNF encoding can be competitive with these specialized methods. In conjunction with our encoding, we propose a slight modification of the DLL procedure that allows any DLL-based SAT solver to solve boolean cardinality optimization problems. We show experimentally that our encoding allows zchaff to be competitive with pseudo-boolean solvers on some decision and optimization problem…
Very narrow quantum OBDDs and width hierarchies for classical OBDDs
2014
In the paper we investigate a model for computing of Boolean functions - Ordered Binary Decision Diagrams (OBDDs), which is a restricted version of Branching Programs. We present several results on the comparative complexity for several variants of OBDD models. - We present some results on the comparative complexity of classical and quantum OBDDs. We consider a partial function depending on a parameter k such that for any k > 0 this function is computed by an exact quantum OBDD of width 2, but any classical OBDD (deterministic or stable bounded-error probabilistic) needs width 2 k+1. - We consider quantum and classical nondeterminism. We show that quantum nondeterminism can be more efficien…