We introduce a logic of knowledge in a framework in which knowledge is treated as a kind of belief The framework is based on a standard KD45 characterization of belief, and the characterization of knowledge undergoes ...
详细信息
We introduce a logic of knowledge in a framework in which knowledge is treated as a kind of belief The framework is based on a standard KD45 characterization of belief, and the characterization of knowledge undergoes the classical tripartite analysis that knowledge is justified true belief, which has a natural link to the studies of logics of evidence and justification. The interpretation of knowledge avoids the unwanted properties of logical omniscience, independent of the choice of the base logic of belief. We axiomatize the logic, prove its soundness and completeness and study the computational complexity results of the model checking and satisfiability problems. We extend the logic to a multi-agent setting and introduce a variant in which belief is characterized in a weaker system to avoid the problem of logical omniscience.
The constraint satisfaction probem (CSP) is a well-acknowledged framework in which many combinatorial search problems can be naturally formulated. The CSP may be viewed as the problem of deciding the truth of a logica...
详细信息
The constraint satisfaction probem (CSP) is a well-acknowledged framework in which many combinatorial search problems can be naturally formulated. The CSP may be viewed as the problem of deciding the truth of a logical sentence consisting of a conjunction of constraints, in front of which all variables are existentially quantified. The quantified constraint satisfaction problem (QCSP) is the generalization of the CSP where universal quanti. cation is permitted in addition to existential quanti. cation. The general intractability of these problems has motivated research studying the complexity of these problems under a restricted constraint language, which is a set of relations that can be used to express constraints. This paper introduces collapsibility, a technique for deriving positive complexity results on the QCSP. In particular, this technique allows one to show that, for a particular constraint language, the QCSP reduces to the CSP. We show that collapsibility applies to three known tractable cases of the QCSP that were originally studied using disparate proof techniques in different decades: Quantified 2-SAT (Aspvall, Plass, and Tarjan in 1979), Quantified HORN-SAT (Karpinski, Kleine Buning, and Schmitt in 1987), and Quantified AFFINE-SAT (Creignou, Khanna, and Sudan in 2001). This reconciles and reveals common structure among these cases, which are describable by constraint languages over a two-element domain. In addition to unifying these known tractable cases, we study constraint languages over domains of larger size.
Consideration was given to minimization of the sum of weighted instants of completing servicing of n customers by a single server, provided that the duration of jobs servicing may assume any real value from a given nu...
详细信息
Consideration was given to minimization of the sum of weighted instants of completing servicing of n customers by a single server, provided that the duration of jobs servicing may assume any real value from a given numerical interval. An algorithm of complexity O(n) was developed to construct a polyhedron (parallelepiped) of the optimality of permutation of servicing of n jobs that is contained in the domain of stability of the same permutation and comprises the polyhedron of its stability. For the randomly generated problems, experimental comparison was carried out of the dimensions and relative volumes of the optimality polyhedra and stability of the optimal permutation of servicing n jobs under randomly generated scenarios.
The queue percentile formulation adopted in the 2010 Highway Capacity Manual (HCM) is empirically based. It contains an overly simplified functional form and parameters such that the accuracy of the back-of-queue perc...
详细信息
The queue percentile formulation adopted in the 2010 Highway Capacity Manual (HCM) is empirically based. It contains an overly simplified functional form and parameters such that the accuracy of the back-of-queue percentile estimates is compromised. In view of this, the author applies the Delta method to derive the uncertainty formulation of back-of-queue through the first-order Taylor expansion approximation, assuming that the source of uncertainty comes from arrival flow, saturation flow and, for actuated controller, green time variability from vehicle actuation. As multiplication of the independent, positive random variables results in a lognormal distributed outcome, the back-of-queue percentile is quantified as a lognormal predictive interval function. The simulation study shows that the proposed back-of-queue predictive interval is much more accurate than the HCM counterpart in most of the cases evaluated based on the Kolmogorov-Smirnov goodness-of-fit test. The proposed formulations can be used to quantify the back-of-queue predictive interval for both pre-timed and actuated control, whereas HCM is indifferent to the type of control. As expected, the variability of back-of-queue from the actuated control is less than the pre-timed control in unsaturated condition. The predictive interval profiles become identical when the degree of saturation approaches to unity and maxes out the green time.
Motivated by emerging resource allocation and data placement problems such as web caches and peer-to-peer systems, we consider and study a class of resource allocation problems over a network of agents (nodes). In thi...
详细信息
Motivated by emerging resource allocation and data placement problems such as web caches and peer-to-peer systems, we consider and study a class of resource allocation problems over a network of agents (nodes). In this model, which can be viewed as a homogeneous data placement problem, nodes can store only a limited number of resources while accessing the remaining ones through their closest neighbors. We consider this problem under both optimization and gametheoretic frameworks. In the case of optimal resource allocation, we will first show that when there are only k = 2 resources, the optimal allocation can be found efficiently in O(n(2) log n) steps, where n denotes the total number of nodes. However, for k >= 3 this problem becomes NP-hard with no polynomial-time approximation algorithm with a performance guarantee better than 1 + 1/102k(2) even under metric access costs. We then provide a 3-approximation algorithm for the optimal resource allocation which runs only in O(kn(2)). Subsequently, we look at this problem under a selfish setting formulated as a noncooperative game and provide a 3-approximation algorithm for obtaining its pure Nash equilibria under metric access costs. We then establish an equivalence between the set of pure Nash equilibria and flip-optimal solutions of the Max-k-Cut problem over a specific weighted complete graph. While this reduction suggests that finding a pure Nash equilibrium using best response dynamics might be PLS-hard, it allows us to use tools from complementary slackness and quadratic programming to devise systematic and more efficient algorithms towards obtaining Nash equilibrium points.
The development of an efficient deadlock avoidance policy (DAP) is a critical step in the design and operation of a flexible manufacturing system (FMS). However, even for a simple FMS, the computation of an optimal DA...
详细信息
The development of an efficient deadlock avoidance policy (DAP) is a critical step in the design and operation of a flexible manufacturing system (FMS). However, even for a simple FMS, the computation of an optimal DAP is intractable. This work addresses the optimal deadlock control problem of FMSs. Based on their Petri net models, it introduces the concept of -resources and proves that an FMS containing no -resources has only two types of reachable states: safe ones and deadlocks. It then can obtain an optimal DAP with polynomial computational complexity for a broader class of FMSs, which was never seen before. At the same time, for these FMSs, new structurally simpler optimal Petri net controllers are proposed.
In this paper, we address the problem of safe and efficient intersection crossing traffic management of autonomous and connected ground traffic. Toward this objective, we propose an algorithm called the discrete-time ...
详细信息
In this paper, we address the problem of safe and efficient intersection crossing traffic management of autonomous and connected ground traffic. Toward this objective, we propose an algorithm called the discrete-time occupancies trajectory based intersection traffic coordination algorithm (DICA). We show that the basic DICA has a computational complexity of O(n(2)L(m)(3)) where n is the number of vehicles granted to cross an intersection and L-m is the maximum length of intersection crossing routes. To improve the overall computational efficiency of the algorithm, the basic DICA is enhanced by several computational approaches that are proposed in this paper. The enhanced algorithm has the computational complexity of O(n(2)L(m) log(2) L-m). The improved computational efficiency of the enhanced algorithm is validated through simulations using an open source traffic simulator called the simulation of urban mobility (SUMO). The overall throughput, as well as the computational efficiency of the enhanced algorithm, are also compared with those of an optimized traffic light control algorithm.
作者：
Xu, NingCUNY
Grad Ctr Dept Comp Sci New York NY 10016 USA
In this paper, the complexity of minimum corridor guarding problems is discussed. These problems can be described as: given a connected orthogonal arrangement of vertical and horizontal line segments and a guard with ...
详细信息
In this paper, the complexity of minimum corridor guarding problems is discussed. These problems can be described as: given a connected orthogonal arrangement of vertical and horizontal line segments and a guard with unlimited visibility along a line segment, find a tree or a closed walk with minimum total length along edges of the arrangement, such that if the guard runs on the tree or on the closed walk, all line segments are visited by the guard. These problems are proved to be NP-complete. (c) 2012 Elsevier B.V. All rights reserved.
Many computer vision applications rely on feature detection and description, hence the need for computationally efficient and robust 4D light field (LF) feature detectors and descriptors. In this paper, we propose a n...
详细信息
Many computer vision applications rely on feature detection and description, hence the need for computationally efficient and robust 4D light field (LF) feature detectors and descriptors. In this paper, we propose a novel light field feature descriptor based on the Fourier disparity layer representation, for light field imaging applications. After the Harris feature detection in a scale-disparity space, the proposed feature descriptor is then extracted using a circular neighborhood rather than a square neighborhood. It is shown to yield more accurate feature matching, compared with the LiFF LF feature, with a lower computational complexity. In order to evaluate the feature matching performance with the proposed descriptor, we generated a synthetic stereo LF dataset with ground truth matching points. Experimental results with synthetic and real-world dataset show that our solution outperforms existing methods in terms of both feature detection robustness and feature matching accuracy.
Do complexity classes have many-one complete sets if and only if they have Turing-complete sets? We prove that there is a relativized world in which a relatively natural complexity class-namely, a downward closure of ...
详细信息
Do complexity classes have many-one complete sets if and only if they have Turing-complete sets? We prove that there is a relativized world in which a relatively natural complexity class-namely, a downward closure of NP, R-1-tt(SN)(NP)-has Turing-complete sets but has no many-one complete sets. In fact, we show that in the same relativized world this class has 2-truth-table complete sets but lacks 1-truth-table complete sets. As part of the groundwork for our result, we prove that R-1-tt(SN)(NP) has many equivalent forms having to do with ordered and parallel access to NP and NP boolean AND coNP.
暂无评论