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 25 Next

Displaying 481 – 500 of 4962

Showing per page

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.

A weighted HP model for protein folding with diagonal contacts

Hans-Joachim Böckenhauer, Dirk Bongartz (2007)

RAIRO - Theoretical Informatics and Applications

The HP model is one of the most popular discretized models for attacking the protein folding problem, i.e., for the computational prediction of the tertiary structure of a protein from its amino acid sequence. It is based on the assumption that interactions between hydrophobic amino acids are the main force in the folding process. Therefore, it distinguishes between polar and hydrophobic amino acids only and tries to embed the amino acid sequence into a two- or three-dimensional grid lattice...

A well-posed multiscale regularization scheme for digital image denoising

V.B. Surya Prasath (2011)

International Journal of Applied Mathematics and Computer Science

We propose an edge adaptive digital image denoising and restoration scheme based on space dependent regularization. Traditional gradient based schemes use an edge map computed from gradients alone to drive the regularization. This may lead to the oversmoothing of the input image, and noise along edges can be amplified. To avoid these drawbacks, we make use of a multiscale descriptor given by a contextual edge detector obtained from local variances. Using a smooth transition from the computed edges,...

Abelian pattern avoidance in partial words

F. Blanchet-Sadri, Benjamin De Winkle, Sean Simmons (2014)

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

Pattern avoidance is an important topic in combinatorics on words which dates back to the beginning of the twentieth century when Thue constructed an infinite word over a ternary alphabet that avoids squares, i.e., a word with no two adjacent identical factors. This result finds applications in various algebraic contexts where more general patterns than squares are considered. On the other hand, Erdős raised the question as to whether there exists an infinite word that avoids abelian squares, i.e.,...

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...

Abelova cena pro Aviho Wigdersona

Pavel Pudlák (2021)

Pokroky matematiky, fyziky a astronomie

Abelovu cenu za rok 2021 získali společně László Lovász a Avi Wigderson za zásadní přínos v teoretické informatice a diskrétní matematice. V tomto článku představíme čtenářům Aviho Wigdersona a jeho práci výběrem tří důležitých výsledků z jeho mnoha publikací.

About the choice of the variable to unassign in a decision repair algorithm

Cédric Pralet, Gérard Verfaillie (2005)

RAIRO - Operations Research - Recherche Opérationnelle

The decision repair algorithm (Jussien and Lhomme, Artificial Intelligence 139 (2002) 21–45), which has been designed to solve constraint satisfaction problems (CSP), can be seen, either (i) as an extension of the classical depth first tree search algorithm with the introduction of a free choice of the variable to which to backtrack in case of inconsistency, or (ii) as a local search algorithm in the space of the partial consistent variable assignments. or (iii) as a hybridisation between local...

About the choice of the variable to unassign in a decision repair algorithm

Cédric Pralet, Gérard Verfaillie (2010)

RAIRO - Operations Research

The decision repair algorithm (Jussien and Lhomme, Artificial Intelligence139 (2002) 21–45), which has been designed to solve constraint satisfaction problems (CSP), can be seen, either (i) as an extension of the classical depth first tree search algorithm with the introduction of a free choice of the variable to which to backtrack in case of inconsistency, or (ii) as a local search algorithm in the space of the partial consistent variable assignments. or (iii) as a hybridisation between local...

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.

About the maximum information and maximum likelihood principles

Igor Vajda, Jiří Grim (1998)

Kybernetika

Neural networks with radial basis functions are considered, and the Shannon information in their output concerning input. The role of information- preserving input transformations is discussed when the network is specified by the maximum information principle and by the maximum likelihood principle. A transformation is found which simplifies the input structure in the sense that it minimizes the entropy in the class of all information-preserving transformations. Such transformation need not be unique...

Abstract Reduction Systems and Idea of Knuth-Bendix Completion Algorithm

Grzegorz Bancerek (2014)

Formalized Mathematics

Educational content for abstract reduction systems concerning reduction, convertibility, normal forms, divergence and convergence, Church- Rosser property, term rewriting systems, and the idea of the Knuth-Bendix Completion Algorithm. The theory is based on [1].

Currently displaying 481 – 500 of 4962