Search results for "Information Systems"
showing 10 items of 1926 documents
The computational complexity of the relative robust shortest path problem with interval data
2004
Abstract The paper deals with the relative robust shortest path problem in a directed arc weighted graph, where arc lengths are specified as intervals containing possible realizations of arc lengths. The complexity status of this problem has been unknown in the literature. We show that the problem is NP -hard.
The computational complexity of the criticality problems in a network with interval activity times
2002
Abstract The paper analyzes the criticality in a network with interval activities duration times. A natural generalization of the criticality notion (for a path, an activity and an event) for the case of network with interval activity duration times is given. The computation complexity of five problems linked to the introduced criticality notion is presented.
The small-world of 'Le Petit Prince': Revisiting the word frequency distribution
2016
[EN] Many complex systems are naturally described through graph theory, and different kinds of systems described as networks present certain important characteristics in common. One of these features is the so-called scale-free distribution for its node s connectivity, which means that the degree distribution for the network s nodes follows a power law. Scale-free networks are usually referred to as small-world because the average distance between their nodes do not scale linearly with the size of the network, but logarithmically. Here we present a mathematical analysis on linguistics: the word frequency effect for different translations of the Le Petit Prince in different languages. Compar…
Best Proximity Point Results in Non-Archimedean Fuzzy Metric Spaces
2013
We consider the problem of finding a best proximity point which achieves the minimum distance between two nonempty sets in a non-Archimedean fuzzy metric space. First we prove the existence and uniqueness of the best proximity point by using di fferent contractive conditions, then we present some examples to support our best proximity point theorems.
Generating binary trees by Glivenko classes on Tamari lattices
2003
Using algebraic-theoretic results, we give an algorithm for generating binary trees within Glivenko classes in Tamari lattices. Tamari lattices are lattices of binary trees endowed by the well-known rotation transformation.
The Monadic Quantifier Alternation Hierarchy over Grids and Graphs
2002
AbstractThe monadic second-order quantifier alternation hierarchy over the class of finite graphs is shown to be strict. The proof is based on automata theoretic ideas and starts from a restricted class of graph-like structures, namely finite two-dimensional grids. Considering grids where the width is a function of the height, we prove that the difference between the levels k+1 and k of the monadic hierarchy is witnessed by a set of grids where this function is (k+1)-fold exponential. We then transfer the hierarchy result to the class of directed (or undirected) graphs, using an encoding technique called strong reduction. It is notable that one can obtain sets of graphs which occur arbitrar…
Loop-free Gray code algorithm for the e-restricted growth functions
2011
The subject of Gray codes algorithms for the set partitions of {1,2,...,n} had been covered in several works. The first Gray code for that set was introduced by Knuth (1975) [5], later, Ruskey presented a modified version of [email protected]?s algorithm with distance two, Ehrlich (1973) [3] introduced a loop-free algorithm for the set of partitions of {1,2,...,n}, Ruskey and Savage (1994) [9] generalized [email protected]?s results and give two Gray codes for the set of partitions of {1,2,...,n}, and recently, Mansour et al. (2008) [7] gave another Gray code and loop-free generating algorithm for that set by adopting plane tree techniques. In this paper, we introduce the set of e-restricte…
DEFECT THEOREMS FOR TREES
2000
We generalize different notions of a rank of a set of words to sets of trees. We prove that almost all of those ranks can be used to formulate a defect theorem. However, as we show, the prefix rank forms an exception.
On approximate-type systems generated by L-relations
2014
The aim of this work is to study approximate-type systems induced by L-relations in the framework of the general theory of M-approximate systems introduced in [42] and its generalizations. Special attention is payed to the structural properties of lattices of such systems and to the study of connections between categories of such systems and the corresponding categories of sets endowed with L-relations.
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…