无聊的人
发表于 2025-3-25 03:33:23
On the Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional. As a first example we consider the 3-Satisfiability problem (3SAT) with two different distributions on 3CNF formulas. We show that 3SAT using a version of the standard distribution is truth-table reducible but not many-one reducible to 3SAT using a less redundant distribution unless . = ...We ext
orient
发表于 2025-3-25 10:27:28
http://reply.papertrans.cn/87/8604/860324/860324_22.png
无法取消
发表于 2025-3-25 13:12:18
On the Class of Languages Recognizable by 1-Way Quantum Finite Automataent conditions for a (regular) language to be recog- nizable by a QFA. For a subclass of regular languages we get a condition which is necessary and sufficient..Also, we prove that the class of languages recognizable by a QFA is not closed under union or any other binary Boolean operation where both
单纯
发表于 2025-3-25 19:49:15
Star-Free Open Languages and Aperiodic Loopse sets closed under a binary operation. A loop is a groupoid with a neutral element and in which each element has a left and a right inverse. It has been shown that finite loops recognize exactly those regular languages that are open in the group topology. In this paper, we study the class of aperio
典型
发表于 2025-3-25 21:17:06
http://reply.papertrans.cn/87/8604/860324/860324_25.png
obnoxious
发表于 2025-3-26 00:08:55
Evasiveness of Subgraph Containment and Related Propertiestaining a subgraph isomorphic to a fixed graph, and a fairly large class of related .-vertex graph properties, we show evasiveness for an arithmetic progression of values of .. This implies a 1/2.. - .(.) lower bound on the decision tree complexity of these properties..We prove that properties that
极小
发表于 2025-3-26 06:31:42
On the Complexity of Computing Minimum Energy Consumption Broadcast Subgraphst operation. In particular, we consider this problem as a special case of the following more general combinatorial optimization problem, called Minimum Energy Consumption Broadcast Subgraph (in short, MECBS): Given a weighted directed graph and a specified source node, find a minimum cost range assi
疼死我了
发表于 2025-3-26 11:32:07
On Presburger Liveness of Discrete Timed Automata configurations are allowed. While the general problem of checking a temporal logic such as TPTL augmented with Presburger clock constraints is undecidable, we show that there are various classes of Presburger liveness properties which are decidable for . timed automata. For instance, it is decid- a
朝圣者
发表于 2025-3-26 14:21:21
http://reply.papertrans.cn/87/8604/860324/860324_29.png
Acetaldehyde
发表于 2025-3-26 19:27:20
Deterministic Radio Broadcasting at Low Costn round if and only if exactly one of its neighbors transmits. The source message has to reach all nodes. We assume that nodes do not know network topology or even their immediate neighbor- hood. We are concerned with two efficiency measures of broadcasting algorithms: its execution . (number of rou