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

indubitable

From Deduction Graphs to Proof Nets: Boxes and Sharing in the Graphical Presentation of Deductionses are used to restrict the scope of local assumptions. Proof nets for multiplicative exponential linear logic (MELL) are also graphs with boxes, but in MELL the boxes have the purpose of controlling the modal operator !. In this paper we study the apparent correspondences between deduction graphs a

modest

On the Representation of Kleene Algebras with Testsies are identified that, along with star-continuity, are sufficient for nonstandard relational representation. An algebraic condition is identified that is necessary and sufficient for the construction to produce a standard representation.

极深

Decompositions, Partitions, and Coverings with Convex Polygons and Pseudo-trianglesthan either convex decompositions or pseudo-triangulations for planar point sets and simple polygons. We also introduce pseudo-convex partitions and coverings. We establish some basic properties and give combinatorial bounds on their complexity. Our upper bounds depend on new Ramsey-type results con

encyclopedia

Approximate Shortest Path Queries on Weighted Polyhedral Surfacesof . triangular faces. We present query algorithms that compute approximate distances and/or approximate (weighted) shortest paths. Our algorithm takes as input an approximation parameter .∈(0,1) and a query time parameter . and builds a data structure which is then used for answering .-approximate

外星人

A Unified Construction of the Glushkov, Follow, and Antimirov Automata, ., or .. This paper presents a simple and unified view of all these construction methods both for unweighted and weighted regular expressions. It describes simpler algorithms with time complexities at least as favorable as that of the best previously known techniques, and provides a concise proof

Oscillate

Algebraic Characterizations of Unitary Linear Quantum Cellular Automataoth by direct combinatorial arguments, and by adding constraints into the model which do not change the quantum cellular automata’s computational power. The configurations we consider have finite but unbounded size.

令人不快

A Polynomial Time Nilpotence Test for Galois Groups and Related Resultsg time is polynomial in size(.). Also, we generalize the Landau-Miller solvability test to an algorithm that tests if Gal(.) is in Γ.: this algorithm runs in time polynomial in size(.) and .. and, moreover, if Gal(.) ∈ Γ. it computes all the prime factors of # Gal(.).

消灭

thrombus

Mirage

Concrete Multiplicative Complexity of Symmetric Functionsit representing ., when only exclusive-or, conjunction and negation gates may be used. This article explores in detail the multiplicative complexity of symmetric Boolean functions. New techniques that allow such exploration are introduced. They are powerful enough to give exact multiplicative comple