Arrow Research search

Author name cluster

Richard Edwin Stearns

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.

8 papers
1 author row

Possible papers

8

ICML Conference 2024 Conference Paper

Efficient PAC Learnability of Dynamical Systems Over Multilayer Networks

  • Zirou Qiu
  • Abhijin Adiga
  • Madhav V. Marathe
  • S. S. Ravi
  • Daniel J. Rosenkrantz
  • Richard Edwin Stearns
  • V. S. Anil Kumar 0001

Networked dynamical systems are widely used as formal models of real-world cascading phenomena, such as the spread of diseases and information. Prior research has addressed the problem of learning the behavior of an unknown dynamical system when the underlying network has a single layer. In this work, we study the learnability of dynamical systems over multilayer networks, which are more realistic and challenging. First, we present an efficient PAC learning algorithm with provable guarantees to show that the learner only requires a small number of training examples to infer an unknown system. We further provide a tight analysis of the Natarajan dimension which measures the model complexity. Asymptotically, our bound on the Nararajan dimension is tight for almost all multilayer graphs. The techniques and insights from our work provide the theoretical foundations for future investigations of learning problems for multilayer dynamical systems.

Details

ICML Conference 2022 Conference Paper

Efficiently Learning the Topology and Behavior of a Networked Dynamical System Via Active Queries

  • Daniel J. Rosenkrantz
  • Abhijin Adiga
  • Madhav V. Marathe
  • Zirou Qiu
  • S. S. Ravi
  • Richard Edwin Stearns
  • V. S. Anil Kumar 0001

Using a discrete dynamical system model, many papers have addressed the problem of learning the behavior (i. e. , the local function at each node) of a networked system through active queries, assuming that the network topology is known. We address the problem of inferring both the topology of the network and the behavior of a discrete dynamical system through active queries. We consider two query models studied in the literature, namely the batch model (where all the queries must be submitted together) and the adaptive model (where responses to previous queries can be used in formulating a new query). Our results are for systems where the state of each node is from {0, 1} and the local functions are Boolean. We present algorithms to learn the topology and the behavior under both batch and adaptive query models for several classes of dynamical systems. These algorithms use only a polynomial number of queries. We also present experimental results obtained by running our query generation algorithms on synthetic and real-world networks.

Details

MFCS Conference 2001 Conference Paper

Analysis Problems for Sequential Dynamical Systems and Communicating State Machines

  • Christopher L. Barrett
  • Harry B. Hunt III
  • Madhav V. Marathe
  • S. S. Ravi
  • Daniel J. Rosenkrantz
  • Richard Edwin Stearns

Abstract Informally, a sequential dynamical system (SDS) consists of an undirected graph where each node v is associated with a state s v and a transition function f v. Given the state value s v and those of the neighbors of v, the function f v computes the next value of s v. The node transition functions are evaluated according to a specified total order. Such a computing device is a mathematical abstraction of a simulation system. We address the complexity of some state reachability problems for SDSs. Our main result is a dichotomy between classes of SDSs for which the state reachability problems are computationally intractable and those for which the problems are efficiently solvable. These results also allow us to obtain stronger lower bounds on the complexity of reachability problems for cellular automata and communicating state machines.

Details

FOCS Conference 1981 Conference Paper

On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Grammars, and Automata

  • Richard Edwin Stearns
  • Harry B. Hunt III

The known proofs that the equivalence and containment problems for the regular and for the linear context-free grammars are PSPACE-complete and undecidable, respecitvely, depend upon consideration of ambiguous grammars. We prove that this dependence is inherent. Deterministic polynomial time algorithms are presented for; (1) the equivalence and containment problems for the unambiguous regular grammars; (2) for all k ≥ 2, the equivalence and containment problems for the regular grammars of degree of ambiguity ≤ k; and (3) the problems of determining if an unambiguous linear context-free grammar is equivalent to or contains an arbitrary regular set. Simple extensions of the grammar classes in (1), (2), and (3) are shown to yield problems that are NP-hard or undecidable. Several new results on the relative economy of description of ambiguous versus unambiguous regular and linear contextfree grammars are also obtained. These results depend upon several observations on the solutions of systems of homogeneous linear difference equations and their relationship with the number of strings of a given length generated by an unambiguous regular or linear context-free grammar.

Details