Titlebook: STACS 2001; 18th Annual Symposiu Afonso Ferreira,Horst Reichel Conference proceedings 2001 Springer-Verlag Berlin Heidelberg 2001 Automat.a

无聊的人

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

无法取消

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

单纯

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

典型

obnoxious

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

极小

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

疼死我了

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

朝圣者

Acetaldehyde

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