Search results for " Computer Science"

Words and forbidden factors

2002

AbstractGiven a finite or infinite word v, we consider the set M(v) of minimal forbidden factors of v. We show that the set M(v) is of fundamental importance in determining the structure of the word v. In the case of a finite word w we consider two parameters that are related to the size of M(w): the first counts the minimal forbidden factors of w and the second gives the length of the longest minimal forbidden factor of w. We derive sharp upper and lower bounds for both parameters. We prove also that the second parameter is related to the minimal period of the word w. We are further interested to the algorithmic point of view. Indeed, we design linear time algorithm for the following two p…

On finding common neighborhoods in massive graphs

2003

AbstractWe consider the problem of finding pairs of vertices that share large common neighborhoods in massive graphs. We prove lower bounds on the resources needed to solve this problem on resource-bounded models of computation. In streaming models, in which algorithms can access the input only a constant number of times and only sequentially, we show that, even with randomization, any algorithm that determines if there exists any pair of vertices with a large common neighborhood must essentially store and process the input graph off line. In sampling models, in which algorithms can only query an oracle for the common neighborhoods of specified vertex pairs, we show that any algorithm must …

On Fine and Wilf's theorem for bidimensional words

2003

AbstractGeneralizations of Fine and Wilf's Periodicity Theorem are obtained for the case of bidimensional words using geometric arguments. The domains considered constitute a large class of convex subsets of R2 which include most parallelograms. A complete discussion is provided for the parallelogram case.

Two shortest path metrics on well-formed parentheses strings

1996

We present an analysis of two transformations on well-formed parentheses strings. Using a lattice approach, the corresponding least-move distances are computable, the first in linear time and the second in quadratic time.

A generalization of Sardinas and Patterson's algorithm to z-codes

1993

Abstract This paper concerns the framework of z-codes theory. The main contribution consists in an extension of the algorithm of Sardinas and Patterson for deciding whether a finite set of words X is a z-code. To improve the efficiency of this test we have found a tight upper bound on the length of the shortest words that might have a double z-factorization over X. Some remarks on the complexity of the algorithm are also given. Moreover, a slight modification of this algorithm allows us to compute the z-deciphering delay of X.

Closedness properties in ex-identification

2001

In this paper we investigate in which cases unions of identifiable classes are also necessarily identifiable. We consider identification in the limit with bounds on mindchanges and anomalies. Though not closed under the set union, these identification types still have features resembling closedness. For each of them we and n such that (1) if every union of n − 1 classes out of U1, ... , Un is identifiable, so is the union of all n classes; (2) there are classes U1, ... ,Un−1 such that every union of n−2 classes out of them is identifiable, while the union of n − 1 classes is not. We show that by finding these n we can distinguish which requirements put on the identifiability of unions of cl…

On bijections vs. unary functions

1996

A set of finite structures is in Binary NP if it can be characterized by existential second order formulas in which second order quantification is over relations of arity 2. In [DLS95] subclasses of Binary NP were considered, in which the second order quantifiers range only over certain classes of relations. It was shown that many of these subclasses coincide and that all of them can be ordered in a three-level linear hierarchy, the levels of which are represented by bijections, successor relations and unary functions respectively.

On embedding Boolean as a subtype of integer

1990

BARGAINING WITH COMMITMENT UNDER AN UNCERTAIN DEADLINE

2006

We consider an infinite horizon bargaining game in which a deadline can arise with positive probability and where players possess an endogenous commitment device. We show that for any truncation of the game, the equilibrium agreement can only take place if the deadline arises within this finite horizon. Since the deadline is an uncertain event, the equilibrium exhibits agreements which are delayed with positive probability.

Existence, uniqueness and comparison results for BSDEs with Lévy jumps in an extended monotonic generator setting

2018

We show existence of a unique solution and a comparison theorem for a one-dimensional backward stochastic differential equation with jumps that emerge from a L\'evy process. The considered generators obey a time-dependent extended monotonicity condition in the y-variable and have linear time-dependent growth. Within this setting, the results generalize those of Royer (2006), Yin and Mao (2008) and, in the $L^2$-case with linear growth, those of Kruse and Popier (2016). Moreover, we introduce an approximation technique: Given a BSDE driven by Brownian motion and Poisson random measure, we consider BSDEs where the Poisson random measure admits only jumps of size larger than $1/n$. We show con…