Displaying similar documents to “Polynomials over the reals in proofs of termination : from theory to practice”

Bottleneck Capacity Expansion Problems with General Budget Constraints

Rainer E. Burkard, Bettina Klinz, Jianzhong Zhang (2010)

RAIRO - Operations Research

Similarity:

This paper presents a unified approach for bottleneck capacity expansion problems. In the bottleneck capacity expansion problem, BCEP, we are given a finite ground set , a family of feasible subsets of and a nonnegative real capacity ĉ for all . Moreover, we are given monotone increasing cost functions for increasing the capacity of the elements as well as a budget . The task is to determine new capacities c ≥ ĉ such that the objective function given by...

Generalizing Substitution

Tarmo Uustalu (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

It is well known that, given an endofunctor on a category , the initial -algebras (if existing), , the algebras of (wellfounded) -terms over different variable supplies , give rise to a monad with substitution as the extension operation (the free monad induced by the functor ). Moss [17] and Aczel, Adámek, Milius and Velebil [12] have shown that a similar monad, which even enjoys the additional special property of having iterations for all guarded substitution rules (complete...

A note on constructing infinite binary words with polynomial subword complexity

Francine Blanchet-Sadri, Bob Chen, Sinziana Munteanu (2013)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

Most of the constructions of infinite words having polynomial subword complexity are quite complicated, , sequences of Toeplitz, sequences defined by billiards in the cube, etc. In this paper, we describe a simple method for constructing infinite words over a binary alphabet  {  }  with polynomial subword complexity . Assuming contains an infinite number of ’s, our method is based on the gap function which gives the distances between consecutive ’s. It is known that...

Differential approximation of NP-hard problems with equal size feasible solutions

Jérôme Monnot (2010)

RAIRO - Operations Research

Similarity:

In this paper, we focus on some specific optimization problems from graph theory, those for which all feasible solutions have an equal size that depends on the instance size. Once having provided a formal definition of this class of problems, we try to extract some of its basic properties; most of these are deduced from the equivalence, under differential approximation, between two versions of a problem  which only differ on a linear transformation of their objective functions. This...

Solving multi-agent scheduling problems on parallel machines with a global objective function

F. Sadi, A. Soukhal, J.-C. Billaut (2014)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

In this study, we consider a scheduling environment with ( ≥ 1) parallel machines. The set of jobs to schedule is divided into disjoint subsets. Each subset of jobs is associated with one agent. The agents compete to perform their jobs on common resources. The objective is to find a schedule that minimizes a global objective function , while maintaining the regular objective function of each agent, , at a level no greater than a fixed value, ...

One-Rule Length-Preserving Rewrite Systems and Rational Transductions

Michel Latteux, Yves Roos (2014)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We address the problem to know whether the relation induced by a one-rule length-preserving rewrite system is rational. We partially answer to a conjecture of Éric Lilin who conjectured in 1991 that a one-rule length-preserving rewrite system is a rational transduction if and only if the left-hand side and the right-hand side of the rule of the system are not quasi-conjugate or are equal, that means if and are distinct, there do not exist words , and such that  =  and  = . We prove...

New applications of the wreath product of forest algebras

Howard Straubing (2013)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We give several new applications of the wreath product of forest algebras to the study of logics on trees. These include new simplified proofs of necessary conditions for definability in and first-order logic with the ancestor relation; a sequence of identities satisfied by all forest languages definable in ; and new examples of languages outside along with an application to the question of what properties are definable in both and

Algebraic and graph-theoretic properties of infinite -posets

Zoltán Ésik, Zoltán L. Németh (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

A -labeled -poset is an (at most) countable set, labeled in the set , equipped with partial orders. The collection of all -labeled -posets is naturally equipped with binary product operations and -ary product operations. Moreover, the -ary product operations give rise to -power operations. We show that those -labeled -posets that can be generated from the singletons by the binary and -ary product operations form the free algebra on in a variety axiomatizable...

Inequality-sum: a global constraint capturing the objective function

Jean-Charles Régin, Michel Rueher (2010)

RAIRO - Operations Research

Similarity:

This paper introduces a new method to prune the domains of the variables in constrained optimization problems where the objective function is defined by a sum , and where the integer variables are subject to difference constraints of the form . An important application area where such problems occur is deterministic scheduling with the as optimality criteria. This new constraint is also more general than a sum constraint defined on a set of ordered variables. Classical...