Titlebook: STACS 2005; 22nd Annual Symposiu Volker Diekert,Bruno Durand Conference proceedings 2005 Springer-Verlag Berlin Heidelberg 2005 Automat.alg

脱离

Counting in the Two Variable Guarded Logic with Transitivityimmediately undecidability of the extension of GF+TG by counting quantifiers. The result is optimal, since both the three-variable fragment of the guarded fragment with counting quantifiers and the two-variable guarded fragment with transitivity are undecidable..We also show that the extension of GF

SOBER

The Variable Hierarchy of the ,-Calculus Is Strictof definable operators. The number of variables occurring in a formula provides a relevant measure of its conceptual complexity. In a previous paper with Erich Grädel we have shown, for the existential fragment of L. , that this conceptual complexity is also reflected in an increase of semantic comp

神圣将军

Audiometry

How Common Can Be Universality for Cellular Automata? that captive cellular automata are almost all intrinsically universal. We show however that intrinsic universality is undecidable for captive cellular automata. Finally, we show that almost all cellular automata have no non-trivial sub-automaton.

deciduous

Cellular Automata: Real-Time Equivalence Between One-Dimensional Neighborhoodsn. However very little is known about the other neighborhoods. In this article, we prove that every one-dimensional neighborhood that is sufficient to recognize every Turing language is equivalent (in terms of real-time recognition) either to the usual neighborhood {–1,0,1} or to the one-way neighbo

Bother

On the Decidability of Temporal Properties of Probabilistic Pushdown Automata the qualitative and quantitative model-checking problem for .-regular properties and pPDA is in . and ., respectively. We also prove that model-checking the qualitative fragment of the logic PECTL. for pPDA is in ., and model-checking the qualitative fragment of PCTL for pPDA is in .. Furthermore,

V洗浴

牲畜栏

Felicitous

More Efficient Queries in PCPs for NP and Improved Approximation Hardness of Maximum CSPof this fact. The probability that the verifier accepts an input in the language given a correct proof is called the .; the probability that the verifier rejects an input not in the language given any proof is called the .. For a verifier posing . queries to the proof, the . is defined by . / log.(.

吞没

Three Optimal Algorithms for Balls of Three Colorslls and asks Carol whether the balls have the same color. Carol truthfully answers yes or no. In the Plurality problem, Paul wants to find a ball with the most common color. In the Partition problem, Paul wants to partition the balls according to their colors. He wants to ask Carol the least number