Titlebook: Mathematical Foundations of Computer Science 2015; 40th International S Giuseppe F Italiano,Giovanni Pighizzini,Donald T. Conference proce

clarify

interior

Mathematical Foundations of Computer Science 2015978-3-662-48057-1Series ISSN 0302-9743 Series E-ISSN 1611-3349

高歌

Minimal and Monotone Minimal Perfect Hash Functionss. In the static case (i.e., when the set . is known in advance), there is a wide spectrum of solutions available, offering different trade-offs in terms of construction time, access time and size of the data structure. MPHFs have been shown to be useful to compress data in several data management t

枯萎将要

好开玩笑

埋葬

Robust Inference and Local Algorithmsmight be corrupted. We survey a new and novel approach to model such possible corruption as a zero-sum game between an adversary that selects the corruption and a leaner that predict the correct label. The corruption of the observations is done in a worse-case setting, by an adversary, where the mai

cultivated

Uniform Generation in Trace Monoidsn the boundary at infinity of the associated monoid. We obtain a product decomposition of the uniform measure at infinity if the trace monoid has several irreducible components—a case where other notions such as Parry measures, are not defined. Random generation algorithms are then examined.

使闭塞

优雅

Stochastization of Weighted Automata the sum of the weights on the transitions it traverses, and the weight of a word is the minimal weight of a run on it. In . (PWFAs), the transitions are further labeled by probabilities, and the weight of a word is the expected weight of a run on it. We define and study . of WFAs: given a WFA ., st

禁止,切断

Algebraic Synchronization Criterion and Computing Reset Wordsms of linear algebra, and obtain upper bounds for the reset thresholds of automata with a short word of a small rank. The results are applied to make several improvements in the area..We improve the best general upper bound for reset thresholds of finite prefix codes (Huffman codes): we show that an