Arrow Research search

Author name cluster

I.V. Ramakrishnan

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.

6 papers
1 author row

Possible papers

6

KER Journal 2007 Journal Article

XcelLog: a deductive spreadsheet system

  • C.R. RAMAKRISHNAN
  • I.V. Ramakrishnan
  • DAVID S. WARREN

Abstract The promise of rule-based computing was to allow end-users to create, modify, and maintain applications without the need to engage programmers. But experience has shown that rule sets often interact in subtle ways, making them difficult to understand and reason about. This has impeded the widespread adoption of rule-based computing. This paper describes the design and implementation of XcelLog, a user-centered deductive spreadsheet system, to empower non-programmers to specify and manipulate rule-based systems. The driving idea underlying the system is to treat sets as the fundamental data type and rules as specifying relationships among sets, and use the spreadsheet metaphor to create and view the materialized sets. The fundamental feature that makes XcelLog suitable for non-programmers is that the user mainly sees the effect of the rules; when rules or basic facts change, the user sees the impact of the change immediately. This enables the user to gain confidence in the rules and their modification, and also experiment with what-if scenarios without any programming. Preliminary experience with using XcelLog indicates that it is indeed feasible to put the power of deductive spreadsheets for doing rule-based computing into the hands of end-users and do so without the requirement of programming or the constraints of canned application packages.

Details DOI

TCS Journal 2001 Journal Article

Automata-driven efficient subterm unification

  • R. Ramesh
  • I.V. Ramakrishnan
  • R.C. Sekar

Syntactic unification has widespread use in computing. There are several operations used in deductive computing such as critical pair generation, paramodulation and narrowing that require unifying a term s with every subterm of another term p. This subterm unification problem can be solved naively by repeatedly unifying s with each subterm of p in isolation. The drawback of doing unification in isolation is that commonality among subterms of p is ignored. We present an algorithm for efficient subterm unification by exploiting this commonality. The central idea used in our algorithm is to reduce the common part computation in unification into a string-matching problem and solve it efficiently using a string-matching automaton. The automaton succinctly captures the commonality between subterms of p. The string-matching approach, in conjunction with two new techniques called bidirectional-reduce and marking enables efficient unification of s with every subterm of p.

Details DOI

I&C Journal 1993 Journal Article

Programming in Equational Logic: Beyond Strong Sequentiality

  • R.C. Sekar
  • I.V. Ramakrishnan

Orthogonal term rewriting systems (also known as regular systems) provide an elegant framework for programming in equational logic. O′Donnell showed that the parallel-outermost strategy, which replaces all outermost redexes in each step, is complete for such systems. Many of the reductions performed by this strategy could be wasteful in general. A lazy normalization algorithm that completely eliminated these wasteful reductions by reducing only "needed redexes" was later developed by Huet and Levy. However, this algorithm required the input programs to be restricted to the subclass of strongly sequential systems. This is because needed redexes do not exist for all orthogonal programs, and even when they do, they may not be computable. It is therefore quite natural to ask whether it is possible to devise a complete normalization algorithm for the entire class that minimizes (rather than eliminates) the wasteful reductions. In this paper we propose a solution to this problem using the concept of a necessary set of redexes. In such a set, at least one of the redexes must be reduced to normalize a term. We devise an algorithm to compute a necessary set for any term not in normal form and show that a strategy that repeatedly reduces all redexes in such a set is complete for orthogonal programs. We also show that our algorithm is "optimal" among all normalization algorithms that are based on left-hand sides alone. This means that our algorithm is lazy (like Huet and Levy′s) on strongly sequential parts of a program and "relaxes laziness minimally" to handle the other parts and thus does not sacrifice generality for the sake of efficiency.

Details DOI

I&C Journal 1992 Journal Article

Tight complexity bounds for term matching problems

  • Rakesh M. Verma
  • I.V. Ramakrishnan

In this paper we study the sequential and parallel complexity of various important term matching problems. These problems occur frequently in applications such as term rewriting, functional programming, and logic programming. First, we obtain non-trivial lower bounds on the parallel complexity of the (uninterpreted) term matching problem. We also establish the tightness of these bounds for some representations and several models. We then characterize completely the sequential complexity of associative and commutative matching when the number of occurrences of variables is varied. Specifically, we show that even if each variable is restricted to at most two occurrences in the terms, both associative matching and commutative matching are NP-complete. Interestingly, for the important restriction of boolean terms we show that commutative matching is NP-complete whereas associative matching has a linear time sequential algorithm. For linear terms, we significantly improve the existing upper bound for associative-commutative matching, and present a new algorithm for associative matching. Designing direct parallel algorithms for associative-commutative matching of linear terms appears to be a difficult task. Despite this we have been able to resolve questions about the parallel complexity of these problems using complexity-theoretic techniques. Finally, an interesting consequence of the research reported here is the demonstration of a tighter relationship between associative-commutative matching for linear terms and bipartite matching on both sequential and parallel models.

Details DOI

I&C Journal 1991 Journal Article

Approximate algorithms for the knapsack problem on parallel computers

  • P.S. Gopalakrishnan
  • I.V. Ramakrishnan
  • L.N. Kanal

Computing an optimal solution to the knapsack problem is known to be NP-hard. Consequently, fast parallel algorithms for finding such a solution without using an exponential number of processors appear unlikely. An attractive alternative is to compute an approximate solution to this problem rapidly using a polynomial number of processors. In this paper, we present an efficient parallel algorithm for finding approximate solutions to the 0–1 knapsack problem. Our algorithm takes an ε, 0 < ε < 1, as a parameter and computes a solution such that the ratio of its deviation from the optimal solution is at most a fraction ε of the optimal solution. For a problem instance having n items, this computation uses O(n 5 2 /ε 3 2 ) processors and requires O(log 3n + log 2nlog( 1 ε )) time. The upper bound on the processor requirement of our algorithm is established by reducing it to a problem on weighted bipartite graphs. This processor complexity is a significant improvement over that of other known parallel algorithms for this problem.

Details DOI
v2026.09.13