All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 9 Next

Displaying 161 – 180 of 332

Showing per page

A survey on combinatorial optimization in dynamic environments∗

Nicolas Boria, Vangelis T. Paschos (2011)

RAIRO - Operations Research

This survey presents major results and issues related to the study of NPO problems in dynamic environments, that is, in settings where instances are allowed to undergo some modifications over time. In particular, the survey focuses on two complementary frameworks. The first one is the reoptimization framework, where an instance I that is already solved undergoes some local perturbation. The goal is then to make use of the information provided by the initial solution to compute a new solution. The...

A survey on combinatorial optimization in dynamic environments∗

Nicolas Boria, Vangelis T. Paschos (2011)

RAIRO - Operations Research

This survey presents major results and issues related to the study of NPO problems in dynamic environments, that is, in settings where instances are allowed to undergo some modifications over time. In particular, the survey focuses on two complementary frameworks. The first one is the reoptimization framework, where an instance I that is already solved undergoes some local perturbation. The goal is then to make use of the information provided by the initial solution to compute a new solution. The...

A system for deduction-based formal verification of workflow-oriented software models

Radosław Klimek (2014)

International Journal of Applied Mathematics and Computer Science

The work concerns formal verification of workflow-oriented software models using the deductive approach. The formal correctness of a model's behaviour is considered. Manually building logical specifications, which are regarded as a set of temporal logic formulas, seems to be a significant obstacle for an inexperienced user when applying the deductive approach. A system, along with its architecture, for deduction-based verification of workflow-oriented models is proposed. The process inference is...

A weighted graph polynomial from chromatic invariants of knots

Steven D. Noble, Dominic J. A. Welsh (1999)

Annales de l'institut Fourier

Motivated by the work of Chmutov, Duzhin and Lando on Vassiliev invariants, we define a polynomial on weighted graphs which contains as specialisations the weighted chromatic invariants but also contains many other classical invariants including the Tutte and matching polynomials. It also gives the symmetric function generalisation of the chromatic polynomial introduced by Stanley. We study its complexity and prove hardness results for very restricted classes of graphs.

Abelian periods, partial words, and an extension of a theorem of Fine and Wilf

Francine Blanchet-Sadri, Sean Simmons, Amelia Tebbe, Amy Veprauskas (2013)

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

Recently, Constantinescu and Ilie proved a variant of the well-known periodicity theorem of Fine and Wilf in the case of two relatively prime abelian periods and conjectured a result for the case of two non-relatively prime abelian periods. In this paper, we answer some open problems they suggested. We show that their conjecture is false but we give bounds, that depend on the two abelian periods, such that the conjecture is true for all words having length at least those bounds and show that some...

About the decision of reachability for register machines

Véronique Cortier (2002)

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

We study the decidability of the following problem: given p affine functions f 1 , ... , f p over ℕ k and two vectors v 1 , v 2 ∈ ℕ k , is v 2 reachable from v 1 by successive iterations of f 1 , ... , f p (in this given order)? We show that this question is decidable for p = 1 , 2 and undecidable for some fixed p .

About the decision of reachability for register machines

Véronique Cortier (2010)

RAIRO - Theoretical Informatics and Applications

We study the decidability of the following problem: given p affine functions ƒ1,...,ƒp over ℕ k and two vectors v 1 , v 2 ∈ ℕ k , is v2 reachable from v1 by successive iterations of ƒ1,...,ƒp (in this given order)? We show that this question is decidable for p = 1, 2 and undecidable for some fixed p.

Currently displaying 161 – 180 of 332