Author name cluster
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
NMR Workshop 2004 Conference Paper
We develop an Answer Set Programming formalism based on Default Logic. We show that computing generating sets of extensions in this formalism captures all ΣP 2 search problems.
NMR Workshop 2004 Conference Paper
Quantum computers have the potential to out-perform classical computers—certain quantum algorithms run much faster than any known alternative classical algorithm. For example, Grover showed that a quantum computer can search an un√ ordered list of N items in time O( N ), providing a quadratic speed-up over the classical algorithm. In this paper, we show that we can modify Grover’s search algorithm to give an algorithm that finds stable models of an Answer Set Program with a similar quadratic improvement over the classical algorithm. Marek and Remmel showed that Answer Set Programming (ASP) programs can uniformly solve all NP-search problems, so our quantum algorithm to find stable models of ASP programs also solves all NP-search problems. It follows that Answer Set Programming could provide a programming language for quantum computation.
TCS Journal 2002 Journal Article
In this paper, we compare the computability and complexity of a continuous real function F with the computability and complexity of the graph G of the function F. A similar analysis will be carried out for functions on subspaces of the real line such as the Cantor space, the Baire space and the unit interval. In particular, we define four basic types of effectively closed sets C depending on whether (i) the set of closed intervals which with nonempty intersection with C is recursively enumerable (r. e.), (ii) the set of closed intervals with empty intersection with C is r. e. , (iii) the set of open intervals which with nonempty intersection with C is r. e. , and (iv) the set of open intervals with empty intersection with C is r. e. We study the relationships between these four types of effectively closed sets in general and the relationships between these four types of effectively closed sets for closed sets which are graphs of continuous functions.
NMR Workshop 2002 Conference Paper
We investigate cardinality-constraint (CC) logic programs as implemented in the ASP solver smodels. Niemela, Simons and collaborators in [NSS99, NS00, Syr01] defined a notion of stable model, which we call CC-stable, for CC-logic programs that differs from the usual notion of stable model of logic programs in a variety of ways. For example, it is not always the case that the set of CC-stable models of a CC-program form an anti-chain. The main result of this paper is to show that there is a natural transformation of a CClogic program P into a standard logic program Q in an extended language such that the CC-stable models of P are the projections of the stable models of Q to the original language. Niemela, Simons and Soinenen [NSS99] proved that the existence problem for CC-stable models of CC-logic programs is NP-complete. We show that the existence problem for CC-stable models for several restricted classes of CC-logic programs is also NP-complete. For example, the existence problem for CC-stable models for CC-logic programs where each clause has an empty body is already NP-complete.
TCS Journal 1999 Journal Article
Π 0 1 classes in a space X where X equals {0, 1} ω, ω ω, [0, 1], or the real line real are given an effective enumeration P e, X and the computably continuous functions are given an effective enumeration F e, X. The notion of index sets associated with Π 0 1 classes and with computably continuous functions is developed. The complexity of various problems of analysis is determined by the complexity of the associated index set.
I&C Journal 1998 Journal Article
We define a notion of a feasible Scott family of formulas for a feasible model and give various conditions on a Scott family which imply that two models with the same family are feasibly isomorphic. For example, ifAandBpossess a common strongly p-time Scott family and both have universe {1}*, then they are p-time isomorphic. These results are applied to the study of permutation structures, linear orderings, equivalence relations, and Abelian groups. For example, conditions on two permutation structures (A, f) and (B, g) are given which imply that (A, f) and (B, g) are p-time isomorphic.
MFCS Conference 1996 Invited Paper
TCS Journal 1995 Journal Article
Hybrid systems are interacting systems of digital automata and continuous plants subject to disturbances. The digital automata are used to force the state trajectory of the continuous plant to obey a performance specification. For the basic concepts and notation for hybrid systems, see Kohn and Nerode (1993), and other papers in the same volume. Here we introduce tools for analyzing enforcing viability of all possible plant state trajectories of a hybrid system by suitable choices of finite state control automata. Thus, the performance specification considered here is that the state of the plant remain in a prescribed viability set of states at all times (Aubin, 1991). The tools introduced are local viability graphs and viability graphs for hybrid systems. We construct control automata which guarantee viability as the fixpoints of certain operators on graphs. When control and state spaces are compact, the viability set is closed, and a non-empty closed subset of a viability graph is given with a sturdiness property, one can extract finite state automata guaranteeing viable trajectories. This paper is a sequel to Kohn and Nerode (1993), especially Appendix II.