Titlebook: Mathematical Foundations of Computer Science 2006; 31st International S Rastislav Královič,Paweł Urzyczyn Conference proceedings 2006 Sprin

使残废

The Structure of Tractable Constraint Satisfaction ProblemsWe give a survey of recent results on the complexity of constraint satisfaction problems. Our main emphasis is on tractable structural restrictions.

缓和

赔偿

生锈

Coloring Random 3-Colorable Graphs with Non-uniform Edge ProbabilitiesRandom 3-colorable graphs that are generated according to a .(.,.)-like model can be colored optimally, if . ≥./. for some large constant .. However, these methods fail in a model where the edge-probabilities are non-uniform and not bounded away from zero. We present a spectral algorithm that succeeds in such situations.

易于出错

Insatiable

The Kleene Equality for Graphs modes are equivalent, and in this case, the equational subsets form a Boolean algebra. We establish that the infinite grid and the transition graphs of deterministic pushdown automata satisfy the Kleene equality and we present families of graphs in which the free product of graphs preserves the Kleene equality.

镶嵌细工

Decompositions, Partitions, and Coverings with Convex Polygons and Pseudo-trianglesoverings. We establish some basic properties and give combinatorial bounds on their complexity. Our upper bounds depend on new Ramsey-type results concerning disjoint empty convex .-gons in point sets.

大方不好

蜿蜒而流

A Unified Construction of the Glushkov, Follow, and Antimirov Automatas to the weighted case. In particular, we extend the definition and construction of follow automata to the case of weighted regular expressions over a closed semiring and present the first algorithm to compute weighted Antimirov automata.

壕沟

Equations on Partial Wordsate equations on .. Partial words are sequences over a finite alphabet that may contain a number of “do not know” symbols. When we speak about equations on partial words, we replace the notion of equality (=) with compatibility ( ↑ ). Among other equations, we solve . ↑ ., . ↑ ., and special cases of .... ↑ .. for integers ., ., . ≥2. ...