Search results for " artificial intelligence"
showing 10 items of 1992 documents
Burrows-Wheeler transform and Run-Length Enconding
2017
In this paper we study the clustering effect of the Burrows-Wheeler Transform (BWT) from a combinatorial viewpoint. In particular, given a word w we define the BWT-clustering ratio of w as the ratio between the number of clusters produced by BWT and the number of the clusters of w. The number of clusters of a word is measured by its Run-Length Encoding. We show that the BWT-clustering ratio ranges in ]0, 2]. Moreover, given a rational number \(r\,\in \,]0,2]\), it is possible to find infinitely many words having BWT-clustering ratio equal to r. Finally, we show how the words can be classified according to their BWT-clustering ratio. The behavior of such a parameter is studied for very well-…
Probability Propagation in Selected Aristotelian Syllogisms
2019
This paper continues our work on a coherence-based probability semantics for Aristotelian syllogisms (Gilio, Pfeifer, and Sanfilippo, 2016; Pfeifer and Sanfilippo, 2018) by studying Figure III under coherence. We interpret the syllogistic sentence types by suitable conditional probability assessments. Since the probabilistic inference of $P|S$ from the premise set ${P|M, S|M}$ is not informative, we add $p(M|(S ee M))>0$ as a probabilistic constraint (i.e., an ``existential import assumption'') to obtain probabilistic informativeness. We show how to propagate the assigned premise probabilities to the conclusion. Thereby, we give a probabilistic meaning to all syllogisms of Figure~III. We…
Conjunction and Disjunction Among Conditional Events
2017
We generalize, in the setting of coherence, the notions of conjunction and disjunction of two conditional events to the case of n conditional events. Given a prevision assessment on the conjunction of two conditional events, we study the set of coherent extensions for the probabilities of the two conditional events. Then, we introduce by a progressive procedure the notions of conjunction and disjunction for n conditional events. Moreover, by defining the negation of conjunction and of disjunction, we show that De Morgan’s Laws still hold. We also show that the associative and commutative properties are satisfied. Finally, we examine in detail the conjunction for a family \(\mathcal F\) of t…
Compound conditionals, Fr\'echet-Hoeffding bounds, and Frank t-norms
2021
Abstract In this paper we consider compound conditionals, Frechet-Hoeffding bounds and the probabilistic interpretation of Frank t-norms. By studying the solvability of suitable linear systems, we show under logical independence the sharpness of the Frechet-Hoeffding bounds for the prevision of conjunctions and disjunctions of n conditional events. In addition, we illustrate some details in the case of three conditional events. We study the set of all coherent prevision assessments on a family containing n conditional events and their conjunction, by verifying that it is convex. We discuss the case where the prevision of conjunctions is assessed by Lukasiewicz t-norms and we give explicit s…
Generalized probabilistic modus ponens
2017
Modus ponens (from A and “if A then C” infer C) is one of the most basic inference rules. The probabilistic modus ponens allows for managing uncertainty by transmitting assigned uncertainties from the premises to the conclusion (i.e., from P(A) and P(C|A) infer P(C)). In this paper, we generalize the probabilistic modus ponens by replacing A by the conditional event A|H. The resulting inference rule involves iterated conditionals (formalized by conditional random quantities) and propagates previsions from the premises to the conclusion. Interestingly, the propagation rules for the lower and the upper bounds on the conclusion of the generalized probabilistic modus ponens coincide with the re…
Randomized renaming in shared memory systems.
2021
Abstract Renaming is a task in distributed computing where n processes are assigned new names from a name space of size m . The problem is called tight if m = n , and loose if m > n . In recent years renaming came to the fore again and new algorithms were developed. For tight renaming in asynchronous shared memory systems, Alistarh et al. describe a construction based on the AKS network that assigns all names within O ( log n ) steps per process. They also show that, depending on the size of the name space, loose renaming can be done considerably faster. For m = ( 1 + ϵ ) ⋅ n and constant ϵ , they achieve a step complexity of O ( log log n ) . In this paper we consider tight as well as loos…
The Descriptive Complexity Approach to LOGCFL
1999
Building upon the known generalized-quantifier-based firstorder characterization of LOGCFL, we lay the groundwork for a deeper investigation. Specifically, we examine subclasses of LOGCFL arising from varying the arity and nesting of groupoidal quantifiers. Our work extends the elaborate theory relating monoidal quantifiers to NC1 and its subclasses. In the absence of the BIT predicate, we resolve the main issues: we show in particular that no single outermost unary groupoidal quantifier with FO can capture all the context-free languages, and we obtain the surprising result that a variant of Greibach's "hardest contextfree language" is LOGCFL-complete under quantifier-free BIT-free interpre…
Uncountable classical and quantum complexity classes
2018
It is known that poly-time constant-space quantum Turing machines (QTMs) and logarithmic-space probabilistic Turing machines (PTMs) recognize uncountably many languages with bounded error (A.C. Cem Say and A. Yakaryılmaz, Magic coins are useful for small-space quantum machines. Quant. Inf. Comput. 17 (2017) 1027–1043). In this paper, we investigate more restricted cases for both models to recognize uncountably many languages with bounded error. We show that double logarithmic space is enough for PTMs on unary languages in sweeping reading mode or logarithmic space for one-way head. On unary languages, for quantum models, we obtain middle logarithmic space for counter machines. For binary la…
Uncountable Realtime Probabilistic Classes
2018
We investigate the minimal cases for realtime probabilistic machines that can define uncountably many languages with bounded error. We show that logarithmic space is enough for realtime PTMs on unary languages. On non-unary case, we obtain the same result for double logarithmic space, which is also tight. When replacing the work tape with a few counters, we can still achieve similar results for unary linear-space two-counter automata, unary sublinear-space three-counter automata, and non-unary sublinear-space two-counter automata. We also show how to slightly improve the sublinear-space constructions by using more counters.
New Encodings of Pseudo-Boolean Constraints into CNF
2009
International audience; This paper answers affirmatively the open question of the existence of a polynomial size CNF encoding of pseudo-Boolean (PB) constraints such that generalized arc consistency (GAC) is maintained through unit propagation (UP). All previous encodings of PB constraints either did not allow UP to maintain GAC, or were of exponential size in the worst case. This paper presents an encoding that realizes both of the desired properties. From a theoretical point of view, this narrows the gap between the expressive power of clauses and the one of pseudo-Boolean constraints.