Titlebook: Computer Science -- Theory and Applications; 10th International C Lev D. Beklemishev,Daniil V. Musatov Conference proceedings 2015 Springer

Unsaturated-Fat

INTER

A Logical Characterization of Timed Pushdown Languages,In this paper, we introduce a quantitative logic on timed words which is expressively equivalent to timed pushdown automata. This logic is an extension of Wilke’s relative distance logic by quantitative matchings. To show the expressive equivalence result, we prove a decomposition theorem which esta

体贴

An In-Place Priority Queue with ,(1) Time for Push and , Comparisons for Pop,, . (.), and . (.-.). In this paper we introduce an in-place priority queue, for which . and . take .(1) worst-case time, and . takes . worst-case time and involves at most . element comparisons, where . denotes the number of elements currently in the data structure. The achieved bounds are optimal

wreathe

Resolution Complexity of Perfect Matching Principles for Sparse Graphs,nse graphs. We construct a constant degree bipartite graph . such that the resolution complexity of the perfect matching principle for . is ., where . is the number of vertices in .. This lower bound is tight up to some polynomial. Our result implies the . lower bounds for the complete graph . and t

infinite

guardianship

ectropion

使无效

Making Randomness Public in Unbounded-Round Information Complexity,d communication complexity . can be converted into a public-coin protocol with the same behavior so that it’s information complexity does not exceed .. “Same behavior” means that the transcripts of these two protocols are identically distributed on each pair of inputs. Such a conversion was previous

摇晃

Resolution Complexity of Perfect Matching Principles for Sparse Graphs,owing properties. There exists a constant . such that the degree of the .-th vertex is at least .(.) and at most ., and it is impossible to make all degrees equal to .(.) by removing the graph’s edges. Moreover, any proof of this statement in the resolution proof system has size .. This result impli

HACK