Anil Nerode

TCS Journal 2009 Journal Article

Effective dimension of points visited by Brownian motion

• Bjørn Kjos-Hanssen
• Anil Nerode

We consider the individual points on a Martin-Löf random path of Brownian motion. We show that (1) Khintchine’s law of the iterated logarithm holds at almost all points; and (2) there exist points (besides the trivial example of the origin) having effective dimension < 1. The proof of (1) shows that, for almost all times t, the path f is Martin-Löf random relative to t and so the effective dimension of ( t, f ( t ) ) is 2.

TCS Journal 2002 Journal Article

Foreword

• Ker-l Ko
• Anil Nerode
• Klaus Weihrauch

TCS Journal 2001 Journal Article

Normal forms and syntactic completeness proofs for functional independencies

• Duminda Wijesekera
• M. Ganesh
• Jaideep Srivastava
• Anil Nerode

We prove normal form theorems of a complete axiom system for the inference of functional dependencies and independencies in relational databases. We also show that all proofs in our system have a normal form where the application of independency rules is limited to three levels. Our normal form results in a faster proof-search engine in deriving consequences of functional independencies. As a result, we get a new construction of an Armstrong relation for a given set of functional dependencies. It is also shown that an Armstrong relation for a set of functional dependencies and independencies do not exist in general, and this generalizes the same result valid under the closed-world assumption.

TCS Journal 1999 Journal Article

Foreword

• Anil Nerode
• Ker-I Ko
• Klaus Weihrauch

I&C Journal 1998 Journal Article

Computable Kripke Models and Intermediate Logics

• Hajime Ishihara
• Bakhadyr Khoussainov
• Anil Nerode

We introduce effectiveness considerations into model theory of intuitionistic logic. We investigate effectiveness of completeness (by Kripke) results for intermediate logics such as intuitionistic logic, classical logic, constant domain logic, directed frames logic, and Dummett's logic.

TCS Journal 1996 Journal Article

A non-ground realization of the stable and well-founded semantics

• Georg Gottlob
• Sherry Marcus
• Anil Nerode
• Gernot Salzer
• V.S Subrahmanian

The declarative semantics of nonmonotonic logic programming has largely been based on propositional programs. However, the ground instantiation of a logic program may be very large, and likewise, a ground stable model may also be very large. We develop a non-ground semantic theory for non-monotonic logic programming. Its principal advantage is that stable models and well-founded models can be represented as sets of atoms, rather than as sets of ground atoms. A set SI of atoms may be viewed as a compact representation of the Herbrand interpretation consisting of all ground instances of atoms in SI. We develop generalizations of the stable and well-founded semantics based on such non-ground interpretations SI. The key notions for our theory are those of covers and anticovers. A cover as well as its anticover are sets of substitutions — non-ground in general — representing all substitutions obtained by ground instantiating some substitution in the (anti)cover, with the additional requirement that each ground substitution is represented either by the cover or by the anticover, but not by both. We develop methods for computing anticovers for a given cover, show that membership in so-called optimal covers is decidable, and investigate the complexity in the Datalog case.

TCS Journal 1996 Journal Article

Computing minimal models by partial instantiation

• Vadim Kagan
• Anil Nerode
• V.S. Subrahmanian

Unlike sets of definite Horn clauses, logic programs with disjunctions of atoms in clause heads are often interpreted in terms of minimal models. It is also well known that the minimal models of logic programs are closely related to the so-called stable models of logic programs with nonmonotonic negation in clause bodies, as well as to circumscription. Methods to compute minimal models of logic programs are becoming increasingly important as an intermediate step in the computation of structures associated with nonmonotonic logic programs. However, to date, all these techniques have been restricted to the case of propositional logic programs which means that an ordinary disjunctive logic program must be “grounded out” prior to computation. Grounding out in this manner leads to a combinatorial explosion in the number of clauses, and hence, is unacceptable. In this paper, we show how, given any method M which correctly computes the set of minimal models of a propositional logic program, we can develop a strategy to compute truth in a minimal model of a disjunctive logic program P. The novel feature of our method is that it works on an “instantiate-by-need” basis, and thus avoids unnecessary grounding.

TCS Journal 1995 Journal Article

Viability in hybrid systems

• Wolf Kohn
• Anil Nerode
• Jeffrey B. Remmel
• Alexander Yakhnis

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.