Search

Your search keyword '"Ravikumar, Bala"' showing total 116 results
Start Over Author "Ravikumar, Bala"
116 results on '"Ravikumar, Bala"'

1. On counting functions and slenderness of languages

Author

Ibarra, Oscar H., McQuillan, Ian, and Ravikumar, Bala

Subjects
Computer Science - Formal Languages and Automata Theory
Abstract

We study counting-regular languages -- these are languages $L$ for which there is a regular language $L'$ such that the number of strings of length $n$ in $L$ and $L'$ are the same for all $n$. We show that the languages accepted by unambiguous nondeterministic Turing machines with a one-way read-only input tape and a reversal-bounded worktape are counting-regular. Many one-way acceptors are a special case of this model, such as reversal-bounded deterministic pushdown automata, reversal-bounded deterministic queue automata, and many others, and therefore all languages accepted by these models are counting-regular. This result is the best possible in the sense that the claim does not hold for either $2$-ambiguous PDA's, unambiguous PDA's with no reversal-bound, and other models. We also study closure properties of counting-regular languages, and we study decidability problems in regards to counting-regularity. For example, it is shown that the counting-regularity of even some restricted subclasses of PDA's is undecidable. Lastly, $k$-slender languages -- where there are at most $k$ words of any length -- are also studied. Amongst other results, it is shown that it is decidable whether a language in any semilinear full trio is $k$-slender.

Published
2019
Full Text
View/download PDF

2. On Counting Functions of Languages

Author

Ibarra, Oscar H., McQuillan, Ian, Ravikumar, Bala, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Hoshi, Mizuho, editor, and Seki, Shinnosuke, editor

Published
2018
Full Text
View/download PDF

5. An Improved Upper-Bound for Rivest et al.’s Half-Lie Problem

Author

Ravikumar, Bala, Innes, Duncan, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Kobsa, Alfred, editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Weikum, Gerhard, editor, Gopal, T. V., editor, Agrawal, Manindra, editor, Li, Angsheng, editor, and Cooper, S. Barry, editor

Published
2014
Full Text
View/download PDF

6. On the Parikh Membership Problem for FAs, PDAs, and CMs

Author

Ibarra, Oscar H., Ravikumar, Bala, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Dediu, Adrian-Horia, editor, Martín-Vide, Carlos, editor, Sierra-Rodríguez, José-Luis, editor, and Truthe, Bianca, editor

Published
2014
Full Text
View/download PDF

8. Some Decision Problems Concerning NPDAs, Palindromes, and Dyck Languages

Author

Ibarra, Oscar H., Ravikumar, Bala, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Konstantinidis, Stavros, editor

Published
2013
Full Text
View/download PDF

9. Some Decision Questions Concerning the Time Complexity of Language Acceptors

Author

Ibarra, Oscar H., Ravikumar, Bala, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Béal, Marie-Pierre, editor, and Carton, Olivier, editor

Published
2013
Full Text
View/download PDF

10. On Bounded Languages and Reversal-Bounded Automata

Author

Ibarra, Oscar H., Ravikumar, Bala, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Dediu, Adrian-Horia, editor, Martín-Vide, Carlos, editor, and Truthe, Bianca, editor

Published
2013
Full Text
View/download PDF

11. Deterministic Simulation of a NFA with k–Symbol Lookahead

Author

Ravikumar, Bala, Santean, Nicolae, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Rangan, C. Pandu, editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, van Leeuwen, Jan, editor, Italiano, Giuseppe F., editor, van der Hoek, Wiebe, editor, Meinel, Christoph, editor, Sack, Harald, editor, and Plášil, František, editor

Published
2007
Full Text
View/download PDF

12. On Some Variations of Two-Way Probabilistic Finite Automata Models

Author

Ravikumar, Bala, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Ibarra, Oscar H., editor, and Dang, Zhe, editor

Published
2006
Full Text
View/download PDF

24. Computability

Author

Jiang, Tao, primary, Li, Ming, additional, Ravikumar, Bala, additional, and Regan, Kenneth, additional

Published
2009
Full Text
View/download PDF

29. Computability

Author

Jiang, Tao, primary, Li, Ming, additional, Ravikumar, Bala, additional, and Regan, Kenneth, additional

Published
1998
Full Text
View/download PDF

33. On some languages in NC : Extended abtract

Author

Ibarra, Oscar H., Jiang, Tao, Ravikumar, Bala, Chang, Jik H., Goos, G., editor, Hartmanis, J., editor, Barstow, D., editor, Brauer, W., editor, Brinch Hansen, P., editor, Gries, D., editor, Luckham, D., editor, Moler, C., editor, Pnueli, A., editor, Seegmüller, G., editor, Stoer, J., editor, Wirth, N., editor, and Reif, John H., editor

Published
1988
Full Text
View/download PDF

37. Quality-Aware Service Delegation in Automated Web Service Composition: An Automata-Theoretic Approach

Author

Ibarra, Oscar H., Ravikumar, Bala, and Gerede, Cagdas Evren

Abstract

Automated Web Service Composition has gained a significant momentum in facilitating fast and efficient formation of business-to-business collaborations where an important objective is the utilization of existing services to respond to new business requirements in a timely manner. In this context, the service delegation problem can be formulated as follows: When a user poses a sequence of requests to a "service community", how to delegate the requests to the available services registered in the community so that the user requests are satisfied via a collaboration of these services. Here, we present a formal analysis of the constrained service delegation problem Where users also provides a set of quality constraints about the delegation of their requests. We follow the "Roman" service composition framework and extend it with a QoS model. We use the Presburger arithmetic to specify constraints. We show that there exists a linear time algorithm for the service delegation problem. In fact, this algorithm is a finite memory algorithm that solves two variations of the service delegation problem by reading the activity sequence in two or multiple passes. We also Show that these results are tight in the sense that the number of passes cannot be further reduced. We also prove that the constrained service delegation problem can be solved in polynomial time in the number of service requests and delegation constraints., Journal of Automata, Languages and Combinatorics, Volume 11, Number 2, 2006, 169-188

Published
2006
Full Text
View/download PDF

39. PREFACE

Author

IBARRA, OSCAR H., primary and RAVIKUMAR, BALA, additional

Published
2009
Full Text
View/download PDF

41. On Some Variations of Two-Way Probabilistic Finite Automata Models.

Author

Ibarra, Oscar, Zhe Dang, and Ravikumar, Bala

Abstract

Rabin [21] initiated the study of probabilistic finite automata (PFA). Rabin's work showed a crucial role of the gap in the error bound (for accepting and non-accepting computations) in the power of the model. Further work resulted in the identification of qualitatively different error models (one-sided error, bounded and unbounded errors, no error etc.) Karpinski and Verbeek [16] and Nisan [20] studied a model of probabilistic automaton in which the tape containing random bits can be read by a two-way head. They presented results comparing models with one-way vs. two-way access to randomness. Dwork and Stockmeyer [5] and Condon et al. [4] studied a model of 2-PFA with nondeterministic states (2-NPFA). In this paper, we present some results about the above mentioned variations of probabilistic finite automata, as well as a model of 2-PFA augmented with a pebble studied in [22]. Our observations indicate that these models exhibit subtle variations in their computational power. We also mention many open problems about these models. Complete characterizations of their power will likely provide deeper insights about the role of randomness is space-bounded computations. [ABSTRACT FROM AUTHOR]

Published
2006
Full Text
View/download PDF

42. MODEL PARTITIONS AND COMPACT TEST CASE SUITES.

Author

BONIFACIO, ADILSON LUIZ, MOURA, ARNALDO VIEIRA, SIMAO, ADENILSO, and Ravikumar, Bala

Subjects
MATHEMATICAL models, PARTITIONS (Mathematics), COMPACTIFICATION (Mathematics), EQUIVALENCE relations (Set theory), MACHINE theory, INFORMATION technology, MATHEMATICAL sequences
Abstract

We present a generalized test case generation method, called the G method. Although inspired by the W method, the G method, in contrast, allows for test case suite generation even in the absence of characterization sets for the specification models. Instead, the G method relies on knowledge about the index of certain equivalences induced at the implementation models. We show that the W method can be derived from the G method as a particular case. Moreover, we discuss some naturally occurring infinite classes of FSM models over which the G method generates test suites that are exponentially more compact than those produced by the W method. [ABSTRACT FROM AUTHOR]

Published
2012
Full Text
View/download PDF

43. On some languages in NC.

Author

Goos, G., Hartmanis, J., Barstow, D., Brauer, W., Brinch Hansen, P., Gries, D., Luckham, D., Moler, C., Pnueli, A., Seegmüller, G., Stoer, J., Wirth, N., Reif, John H., Ibarra, Oscar H., Jiang, Tao, Ravikumar, Bala, and Chang, Jik H.

Published
1988
Full Text
View/download PDF

44. ON THE EXISTENCE OF LOOKAHEAD DELEGATORS FOR NFA.

Author

RAVIKUMAR, BALA, SANTEAN, NICOLAE, and Ibarra, Oscar H.

Subjects
*SEQUENTIAL machine theory, *ROBOTS, *MACHINE theory, *ALGORITHMS, *COMPUTERS
Abstract

We investigate deterministically simulating (i.e., solving the membership problem for) nondeterministic finite automata (NFA), relying solely on the NFA's resources (states and transitions). Unlike the standard NFA simulation, involving an algorithm which stores at each step all the states reached nondeterministically while reading the input, we consider deterministic finite automata (DFA) with lookahead, which choose the “right” NFA transitions based on a fixed number of input symbols read ahead. This concept, known as lookahead delegation, arose in a formal study of web services composition and its subsequent practical applications. Here we answer several related questions, such as “when is lookahead delegation possible?” and “how hard is it to find a delegator with a given lookahead buffer size?”. In particular, we show that only finite languages have the property that all their NFA have delegators. This implies, among others, that delegation is a machine property, rather than a language property. We also prove that the existence of lookahead delegators for unambiguous NFA is decidable, thus partially solving an open problem. Finally, we show that finding delegators (even for a given buffer size) is hard in general, and is more efficient for unambiguous NFA, and we give an algorithm and a compact characterization for NFA delegation in general. [ABSTRACT FROM AUTHOR]

Published
2007
Full Text
View/download PDF

50. Hopcroft’s Minimization Technique: Queues or Stacks?

Author

Păun, Andrei, Păun, Mihaela, Rodríguez-Patón, Alfonso, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Ibarra, Oscar H., editor, and Ravikumar, Bala, editor

Published
2008
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results