脱离
发表于 2025-3-25 06:59:56
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
发表于 2025-3-25 08:44:54
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
神圣将军
发表于 2025-3-25 14:21:41
http://reply.papertrans.cn/87/8604/860328/860328_23.png
Audiometry
发表于 2025-3-25 17:07:26
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
发表于 2025-3-25 22:49:50
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
发表于 2025-3-26 00:18:41
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洗浴
发表于 2025-3-26 07:14:09
http://reply.papertrans.cn/87/8604/860328/860328_27.png
牲畜栏
发表于 2025-3-26 09:58:32
http://reply.papertrans.cn/87/8604/860328/860328_28.png
Felicitous
发表于 2025-3-26 14:08:12
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.(.
吞没
发表于 2025-3-26 18:39:59
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