Titlebook: Mathematical Foundations of Computer Science 2013; 38th International S Krishnendu Chatterjee,Jirí Sgall Conference proceedings 2013 Spring

大约冬季

Parity Games and Propositional Proofs,tion in the system, with respect to a given length bound. We show that if the resolution proof system is weakly automatizable, then parity games can be decided in polynomial time. We also define a combinatorial game and prove that resolution is weakly automatizable if and only if one can separate, b

残忍

A Constant Factor Approximation for the Generalized Assignment Problem with Minimum Quantities and d to be either zero (if the bin is not opened) or above a given lower bound (a .). This problem is known to be strongly .-complete and does not admit a polynomial time approximation scheme (PTAS)..By using randomized rounding, we obtain a randomized 3.93-approximation algorithm, thereby providing th

充气女

Determinacy and Rewriting of Top-Down and MSO Tree Transformations,two given tree transformations, whether one is determined by the other. If the view transformation is induced by a tree transducer that may copy, then determinacy is undecidable, even for identity queries. For a large class of non-copying views, namely compositions of functional extended linear top-

镇压

合群

Mawkish

Auctions for Partial Heterogeneous Preferences,rmalization difficulties; (ii) the preferences of auctioneers and bidders may be heterogeneous and unrelated. We tackle these generalized scenarios by introducing a few natural generalizations of second-price auctions, and by investigating which of their classical properties are preserved under whic

abysmal

New Polynomial Cases of the Weighted Efficient Domination Problem,ted by exactly one vertex of .. The . (ED) problem, which asks for the existence of an e.d. in ., is known to be .-complete even for very restricted graph classes..In particular, the ED problem remains .-complete for 2. .-free graphs and thus for . .-free graphs. We show that the weighted version of

凹室

MEAN

Jean Goubault-Larrecqnd globale Suchverfahren (Evolution) integriert werden. Die Evolution automatisiert hierbei die üblicherweise verwendete .-Suche nach einer geeigneten Topologie durch den Anwender. Bei unseren experimentellen Untersuchungen haben wir gezeigt, daß sich durch die systematische Suche drastische Verbess

NICHE