A Short Note on Some Tractable Cases of the Satisfiability Problem

It is shown that the tractable class of CNF formulas solvable by linear autarkies properly contains the class of q-Horn formulas and that it is incomparable with SLUR.     

An Algorithm for Approximating the Satisfiability Problem of High-level Conditions

The satisfiability problem is the fundamental problem in proving the conflict-freeness of specifications, or in finding a counterexample for an invalid statement. In this paper, we present a non-deterministic, monotone algorithm for this undecidable problem on graphical conditions that is both correct and complete, but in general not guaranteed to terminate. For a fragment of high-level conditions, the algorithm terminates, hence it is able to decide. Instead of enumerating all possible objects of a category to approach the problem, the algorithm uses the input condition in a constructive way to progress towards a solution. To this aim, programs over transformation rules with external interfaces are considered. We use the framework of weak adhesive HLR categories. Consequently, the algorithm is applicable to a number of replacement capable structures, such as Petri-Nets, graphs or hypergraphs.     

Complete Classifications for the Communication Complexity of Regular Languages

We show that every regular language L has either constant, logarithmic or linear two-party communication complexity (in a worst-case partition sense). We prove similar classifications for the communication complexity of regular languages for the simultaneous, probabilistic, simultaneous probabilistic and Mod_p-counting models of communication.     

Probabilistic Pattern Matching and the Evolution of Stochastic Regular Expressions

The use of genetic programming for probabilistic pattern matching is investigated. A stochastic regular expression language is used. The language features a statistically sound semantics, as well as a syntax that promotes efficient manipulation by genetic programming operators. An algorithm for efficient string recognition based on approaches in conventional regular language recognition is used. When attempting to recognize a particular test string, the recognition algorithm computes the probabilities of generating that string and all its prefixes with the given stochastic regular expression. To promote efficiency, intermediate computed probabilities that exceed a given cut-off value will pre-empt particular interpretation paths, and hence prune unconstructive interpretation. A few experiments in recognizing stochastic regular languages are discussed. Application of the technology in bioinformatics is in progress.     

Exact Complexity of the Winner Problem for Young Elections

In 1977 Young proposed a voting scheme that extends the Condorcet Principle based on the fewest possible number of voters whose removal yields a Condorcet winner. We prove that both the winner and the ranking problem for Young elections is complete for \p _|| ^NP , the class of problems solvable in polynomial time by parallel access to NP. Analogous results for Lewis Carroll's 1876 voting scheme were recently established by Hemaspaandra et al. In contrast, we prove that the winner and ranking problems in Fishburn's homogeneous variant of Carroll's voting scheme can be solved efficiently by linear programming.     

基于因子图求解(3,4=)-CNF公式类下可满足问题

合取范式(CNF)公式F是(3,4=)-CNF公式,如果F中每个子句的长度是3,每个变元出现的次数恰好为4次.与(3,4=)-CNF公式所关联的因子图是一类规则的二部图,即每个子句结点的度为3,每个变元结点的度为4,此类规则图被称为(3,4)-双向正则二部图.对于一个(3,4=)-CNF公式F,如果它关联的因子图GF有P7路径因子,则F可满足.     

Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem

We prove that the exact versions of the domatic number problem are complete for the levels of the boolean hierarchy over NP. The domatic number problem, which arises in the area of computer networks, is the problem of partitioning a given graph into a maximum number of disjoint dominating sets. This number is called the domatic number of the graph. We prove that the problem of determining whether or not the domatic number of a given graph is exactly one of k given values is complete for BH_2k(NP), the 2kth level of the boolean hierarchy over NP. In particular, for k = 1, it is DP-complete to determine whether or not the domatic number of a given graph equals exactly a given integer. Note that DP = BH₂(NP). We obtain similar results for the exact versions of generalized dominating set problems and of the conveyor flow shop problem. Our reductions apply Wagner's conditions sufficient to prove hardness for the levels of the boolean hierarchy over NP.     

Parameterized Complexity and Local Search Approaches for the Stable Marriage Problem with Ties

We consider the variant of the classical Stable Marriage problem where preference lists can be incomplete and may contain ties. In such a setting, finding a stable matching of maximum size is NP-hard. We study the parameterized complexity of this problem, where the parameter can be the number of ties, the maximum or the overall length of ties. We also investigate the applicability of a local search algorithm for the problem. Finally, we examine the possibilities for giving an FPT algorithm or an FPT approximation algorithm for finding an egalitarian or a minimum regret matching.     

Space Functions and Space Complexity of the Word Problem in Semigroups

We introduce the space function s(n) of a finitely presented semigroup ${S =\langle A \mid R \rangle}$ . To define s(n) we consider pairs of words w,w′ over A of length at most n equal in S and use relations from R for the derivations ${w = w_0 \rightsquigarrow \dots \rightsquigarrow w_t = w'; s(n)}$ bounds from above the lengths of the words w _i at intermediate steps, i.e., the space sufficient to implement all such transitions ${w \rightsquigarrow \dots \rightsquigarrow w'}$ . One of the results obtained is the following criterion: A finitely generated semigroup S has decidable word problem of polynomial space complexity if and only if S is a subsemigroup of a finitely presented semigroup H with polynomial space function.     

The Complexity of the Exponential Output Size Problem for Top-Down and Bottom-Up Tree Transducers,

The exponential output size problem is to determine whether the size of output trees of a tree transducer grows exponentially in the size of input trees. In this paper the complexity of this problem is studied. It is shown to be NL-complete for total top-down tree transducers, DEXPTIME-complete for general top-down tree transducers, and P-complete for bottom-up tree transducers.     

用遗传算法解带时延及时延抖动约束的组播路由优化问题

带约束条件的组播路由是网络应用的发展所提出的新的问题,根据不同的约束条件有不同的变种,该文讨论了带时延及时延抖动约束的组播路由优化问题,给出了该问题的数学模型,提出了求解该问题的一种基于候选路由库的遗传算法,并对该算法的仿真结果与前人的结果进行了比较。结果证明,用遗传算法解决这类问题是有效的。     

Bisimulation, the Supervisory Control Problem and Strong Model Matching for Finite State Machines

A fundamental relationship between the controllability of a language with respect to another language and a set of uncontrollable events in the Supervisory Control Theory initiated by (Ramadge and Wonham, 1989) and bisimulation of automata models is derived. The theoretical results relating bisimulation to controllability support an efficient solution to the Basic Supervisory Control Problem. Using (Fernandez, 1990) generalization of the partition refinement algorithm of (Paige and Tarjan, 1987), it is possible to find a partition which represents the supremal controllable sublanguage of an automaton with respect to the language of another automaton and a set of events in a worst-case running time of O( m log(n)), where m is the number of transitions and n is the number of states. Utilizing the bisimulation property of language controllability and derived relationships between automata languages and input/output finite-state machine behaviors, a precise relationship is formally derived between Supervisory Control Theory and the system-theoretic problem posed by (DiBenedetto et al., 1994) called Strong Input/Output FSM Model Matching. Specifically, it is proven that in deterministic settings instances of each problem can be mapped to the other framework and solved.     

Mixed Covering of Trees and the Augmentation Problem with Odd Diameter Constraints

In this paper we present a polynomial time algorithm for solving the problem of partial covering of trees with n₁ balls of radius R₁ and n₂ balls of radius R₂ (R₁ < R₂) to maximize the total number of covered vertices. The solutions provided by this algorithm in the particular case R₁ = R – 1, R₂ = R can be used to obtain for any integer δ > 0 a factor (2+1/δ) approximation algorithm for solving the following augmentation problem with odd diameter constraints D = 2R + 1: Given a tree T, add a minimum number of new edges such that the augmented graph has diameter ≤ D. The previous approximation algorithm of Ishii, Yamamoto, and Nagamochi (2003) has factor 8.     

A Dual Approach for Solving the Combined Distribution and Assignment Problem with Link Capacity Constraints

In this paper, we consider the combined distribution and assignment (CDA) problem with link capacity constraints modeled as a hierarchical logit choice problem based on random utility theory. The destination and route choices are calculated based on the multi-nominal logit probability function, which forms the basis for constructing the side constrained CDA (SC-CDA) problem as an equivalent mathematical programming (MP) formulation. A dual MP formulation of the SC-CDA problem is developed as a solution algorithm, which consists of an iterative balancing scheme and a column generation scheme, for solving the SC-CDA problem. Due to the entropy-type objective function, the dual formulation has a simple nonlinear constrained optimization structure, where the feasible set only consists of nonnegative orthants. The iterative balancing scheme explicitly makes use of the optimality conditions of the dual formulation to analytically adjust the dual variables and update the primal variables, while a column generation scheme is used to iteratively generate routes to the working route set as needed to satisfy the side constraints. Two numerical experiments are conducted to demonstrate the features of the SC-CDA model and the computational performance of the solution algorithm. The results reveal that imposing link capacity constraints can have a significant impact on the network equilibrium flow allocations, and the dual approach is a practical solution algorithm for solving the complex SC-CDA problem.     

模型的固有复杂度和泛化能力与几何曲率的关系

从微分几何角度考察与参数化形式无关的统计模型流形的固有复杂度,指出模型流形的Gauss-Kroneker曲率可以完全刻画模型流形在一点处的全部性质,进而分析了曲率与体积的关系;给出了基于参数估计量邻域附近的解轨迹方法的曲率计算方法;证明了用于衡量泛化能力的未来残差可以用模型的曲率来表示,由此给出一种新的以曲率度量模型复杂度的模型选择准则GKCIC;对几何方法和统计学习理论进行了分析比较.在人工数据集和真实数据集上的比较实验结果表明了文中提出的方法的有效性.     

Knowledge-Based Integration Between Virtual and Physical Prototyping for Identifying Behavioral Constraints of Embedded Real-Time Systems

Rapid prototyping methods are in need of autonomous decision making and analysis during the product development stages so that the ldquotime-to-marketrdquo can be reduced faster than traditional product development methodologies. Therefore, new methods of prototyping are inevitably essential. This paper proposes an approach to utilize the benefits of virtual prototyping (VP) and physical prototyping (PP) methodologies by integrating them into knowledge-based systems (KBSs) by providing seamless connection. This approach is termed autonomous integrated prototyping. The main contribution of this paper is the development of an intelligent system architecture to facilitate and guide the product development autonomously and simultaneously in both VP and PP environments. The seamless connection between VP and PP, along with KBSs, enables the exploration of new behaviors of developing systems and analyzing different behaviors. The architecture is applicable to embedded real-time systems (ERTSs), sensor applications, robotics, and ubiquitous applications where system interaction with the external environment is necessary.     

A Stronger Complexity Result for the Single Machine Multi-Operation Jobs Scheduling Problem to Minimize the Number of Tardy Jobs

We consider the single machine multi-operation jobs scheduling problem to minimize the number of tardy jobs. Each job consists of several operations that belong to different families. In a schedule, each family of job operations may be processed in batches with each batch incurring a setup time. A job completes when all of its operations have been processed. The objective is to minimize the number of tardy jobs. In the literature, this problem has been proved to be strongly NP-hard for arbitrary due-dates. We show in this paper that the problem remains strongly NP-hard even when the due-dates are common and all jobs have the same processing time.