Daniel J. Rosenkrantz

Affiliations:
  • State University at Albany, NY, USA


According to our database1, Daniel J. Rosenkrantz authored at least 146 papers between 1966 and 2024.

Collaborative distances:

Awards

ACM Fellow

ACM Fellow 1995, "For pioneering contributions to formal languages, compiler design, algorithm analysis, databases, parallel and fault-tolerant computing and for exemplary ACM service including Editorship of JACM.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Learning the Topology and Behavior of Discrete Dynamical Systems.
CoRR, 2024

2023
Finding Nontrivial Minimum Fixed Points in Discrete Dynamical Systems.
CoRR, 2023

Assigning Agents to Increase Network-Based Neighborhood Diversity.
Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, 2023

Resource Sharing through Multi-Round Matchings.
Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence, 2023

Networked Anti-coordination Games Meet Graphical Dynamical Systems: Equilibria and Convergence.
Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence, 2023

2022
Fundamental limitations on efficiently forecasting certain epidemic measures in network models.
Proc. Natl. Acad. Sci. USA, 2022

Techniques for blocking the propagation of two simultaneous contagions over networks using a graph dynamical systems framework.
Netw. Sci., 2022

Using Active Queries to Infer Symmetric Node Functions of Graph Dynamical Systems.
J. Mach. Learn. Res., 2022

Efficiently Learning the Topology and Behavior of a Networked Dynamical System Via Active Queries.
Proceedings of the International Conference on Machine Learning, 2022

Finding Nontrivial Minimum Fixed Points in Discrete Dynamical Systems: Complexity, Special Case Algorithms and Heuristics.
Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence, 2022

2021
Synchronous Dynamical Systems on Directed Acyclic Graphs: Complexity and Algorithms.
Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, 2021

2020
Evolution of Similar Configurations in Graph Dynamical Systems.
Proceedings of the Complex Networks & Their Applications IX, 2020

Blocking the Propagation of Two Simultaneous Contagions over Networks.
Proceedings of the Complex Networks & Their Applications IX, 2020

Bounds and Complexity Results for Learning Coalition-Based Interaction Functions in Networked Social Systems.
Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence, 2020

2019
Symmetry Properties of Nested Canalyzing Functions.
Discret. Math. Theor. Comput. Sci., 2019

Validating Agent-Based Models of Large Networked Systems.
Proceedings of the 2019 Winter Simulation Conference, 2019

2018
A characterization of nested canalyzing functions with maximum average sensitivity.
Discret. Appl. Math., 2018

Computational Aspects of Fault Location and Resilience Problems for Interdependent Infrastructure Networks.
Proceedings of the Complex Networks and Their Applications VII, 2018

Using Active Queries to Learn Local Stochastic Behaviors in Social Networks.
Proceedings of the Complex Networks and Their Applications VII, 2018

Inferring Probabilistic Contagion Models Over Networks Using Active Queries.
Proceedings of the 27th ACM International Conference on Information and Knowledge Management, 2018

Testing Phase Space Properties of Synchronous Dynamical Systems with Nested Canalyzing Local Functions.
Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, 2018

Learning the Behavior of a Dynamical System Via a "20 Questions" Approach.
Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, 2018

Approximation Algorithms for Facility Dispersion.
Proceedings of the Handbook of Approximation Algorithms and Metaheuristics, 2018

2017
Inferring local transition functions of discrete dynamical systems from observations of system behavior.
Theor. Comput. Sci., 2017

2015
Inhibiting diffusion of complex contagions in social networks: theoretical and experimental results.
Data Min. Knowl. Discov., 2015

Complexity of Inferring Local Transition Functions of Discrete Dynamical Systems.
Proceedings of the Implementation and Application of Automata, 2015

Analysis Problems for Graphical Dynamical Systems: A Unified Approach Through Graph Predicates.
Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, 2015

2014
Bayesian Inference in Treewidth-Bounded Graphical Models Without Indegree Constraints.
Proceedings of the Thirtieth Conference on Uncertainty in Artificial Intelligence, 2014

2011
Modeling and analyzing social network dynamics using stochastic discrete graphical dynamical systems.
Theor. Comput. Sci., 2011

A general-purpose graph dynamical system modeling framework.
Proceedings of the Winter Simulation Conference 2011, 2011

Effects of Opposition on the Diffusion of Complex Contagions in Social Networks: An Empirical Study.
Proceedings of the Social Computing, Behavioral-Cultural Modeling and Prediction, 2011

Inhibiting the Diffusion of Contagions in Bi-Threshold Systems: Analytical and Experimental Results.
Proceedings of the Complex Adaptive Systems: Energy, 2011

2010
Finding Critical Nodes for Inhibiting Diffusion of Complex Contagions in Social Networks.
Proceedings of the Machine Learning and Knowledge Discovery in Databases, 2010

2009
Segmentation of Time Series Data.
Proceedings of the Encyclopedia of Data Warehousing and Mining, Second Edition (4 Volumes), 2009

Resilience Metrics for Service-Oriented Networks: A Service Allocation Approach.
IEEE Trans. Serv. Comput., 2009

2008
Errata for the paper "Predecessor existence problems for finite discrete dynamical systems" [TCS 386 (1-2) (2007) 3-37].
Theor. Comput. Sci., 2008

A segmentation-based approach for temporal analysis of software version repositories.
J. Softw. Maintenance Res. Pract., 2008

Efficient algorithms for segmentation of item-set time series.
Data Min. Knowl. Discov., 2008

A Transformation--Based Approach for the Design of Parallel/Distributed Scientific Software: the FFT
CoRR, 2008

2007
Approximation Algorithms for Facility Dispersion.
Proceedings of the Handbook of Approximation Algorithms and Metaheuristics., 2007

Predecessor existence problems for finite discrete dynamical systems.
Theor. Comput. Sci., 2007

Computational Aspects of Analyzing Social Network Dynamics.
Proceedings of the IJCAI 2007, 2007

Discovering Dynamic Developer Relationships from Software Version Histories by Time Series Segmentation.
Proceedings of the 23rd IEEE International Conference on Software Maintenance (ICSM 2007), 2007

2006
On minimizing materializations of array-valued temporaries.
ACM Trans. Program. Lang. Syst., 2006

Obtaining online approximation algorithms for facility dispersion from offline algorithms.
Networks, 2006

Complexity of reachability problems for finite discrete dynamical systems.
J. Comput. Syst. Sci., 2006

Information Preserving Time Decompositions of Time Stamped Documents<sup>*</sup>.
Data Min. Knowl. Discov., 2006

Towards a Predictive Computational Complexity Theory.
Proceedings of the Computational Complexity and Statistical Physics., 2006

2005
In memory of Seymour Ginsburg 1928 - 2004.
SIGMOD Rec., 2005

Structure-Based Resilience Metrics for Service-Oriented Networks.
Proceedings of the Dependable Computing, 2005

Efficient Algorithms for Constructing Time Decompositions of Time Stamped Documents.
Proceedings of the Database and Expert Systems Applications, 16th International Conference, 2005

2004
Local base station assignment with time intervals in mobile computing environments.
Eur. J. Oper. Res., 2004

Constructing Time Decompositions for Analyzing Time-Stamped Documents.
Proceedings of the Fourth SIAM International Conference on Data Mining, 2004

On lossy time decompositions of time stamped documents.
Proceedings of the 2004 ACM CIKM International Conference on Information and Knowledge Management, 2004

2003
Reachability problems for sequential dynamical systems with threshold functions.
Theor. Comput. Sci., 2003

JACM 1986-1990.
J. ACM, 2003

Predecessor and Permutation Existence Problems for Sequential Dynamical Systems.
Proceedings of the Discrete Models for Complex Systems, 2003

2002
Parallel Approximation Schemes for a Class of Planar and Near Planar Combinatorial Optimization Problems.
Inf. Comput., 2002

2001
Reminiscences on Influential Papers.
SIGMOD Rec., 2001

Efficient Construction of Minimum Makespan Schedules for Tasks with a Fixed Number of Distinct Execution Times.
Algorithmica, 2001

Approximation Algorithms for Degree-Constrained Minimum-Cost Network-Design Problems.
Algorithmica, 2001

Analysis Problems for Sequential Dynamical Systems and Communicating State Machines.
Proceedings of the Mathematical Foundations of Computer Science 2001, 2001

Gardens of Eden and Fixed Points in Sequential Dynamical Systems.
Proceedings of the Discrete Models: Combinatorics, Computation, and Geometry, 2001

2000
Alarm placement in systems with fault propagation.
Theor. Comput. Sci., 2000

Facility Dispersion Problems Under Capacity and Cost Constraints.
J. Comb. Optim., 2000

Algorithms for Path-Based Placement of Inspection Stations on Networks.
INFORMS J. Comput., 2000

On Materializations of Array-Valued Temporaries.
Proceedings of the Languages and Compilers for Parallel Computing, 2000

1999
Path problems in networks with vector-valued edge weights.
Networks, 1999

Using Data Flow Information to Obtain Efficient Check Sets for Algorithm-Based Fault Tolerance.
Int. J. Parallel Program., 1999

1998
Bicriteria Network Design Problems.
J. Algorithms, 1998

NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs.
J. Algorithms, 1998

Theory of Periodically Specified Problems: Complexity and Approximability.
Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998

1997
Compact Location Problems.
Theor. Comput. Sci., 1997

Multi-site distributed database transactions utilizing deferred update.
Proceedings of the 1997 ACM symposium on Applied Computing, 1997

1996
Spanning Trees - Short or Small.
SIAM J. Discret. Math., 1996

I/O Automata Based Verification of Finite State Distributed Systems: Complexity Issues (Abstract).
Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, 1996

Deferred Updates and Data Placement in Distributed Databases.
Proceedings of the Twelfth International Conference on Data Engineering, February 26, 1996

On the Complexity of Relational Problems for Finite State Processes (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 23rd International Colloquium, 1996

A simulation and validation tool for self-stabilizing protocols.
Proceedings of the Spin Verification System, 1996

The polynomial time decidability of simulation relations for finite processes: A HORNSAT based approach.
Proceedings of the Satisfiability Problem: Theory and Applications, 1996

HORNSAT, Model Checking, Verification and games (Extended Abstract).
Proceedings of the Computer Aided Verification, 8th International Conference, 1996

1995
On the Size of Binary Decision Diagrams Representing Boolean Functions.
Theor. Comput. Sci., 1995

Simple heuristics for unit disk graphs.
Networks, 1995

Active Client Primary-Backup Protocols (Abstract).
Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, 1995

Efficient algorithms for analyzing and synthesizing fault-tolerant datapaths.
Proceedings of the 1995 IEEE International Symposium on Defect and Fault Tolerance in VLSI and Nanotechnology Systems, 1995

1994
Partitioning Message Patterns for Bundled Omega Networks.
IEEE Trans. Parallel Distributed Syst., 1994

A Linear-Time Scheme for Version Reconstruction.
ACM Trans. Program. Lang. Syst., 1994

Construction of Check Sets for Algorithm-Based Fault Tolerance.
IEEE Trans. Computers, 1994

Heuristic and Special Case Algorithms for Dispersion Problems.
Oper. Res., 1994

Geometry based heuristics for unit disk graphs.
CoRR, 1994

Interactive control restructuring.
Proceedings of the Second International Symposium on Environments and Tools for Ada, 1994

Approximation Schemes Using L-Reductions.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1994

A Unified Approach to Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs.
Proceedings of the Algorithms, 1994

1993
Ancestor Controlled Submodule Inclusion in Design Databases.
IEEE Trans. Knowl. Data Eng., 1993

Improved Bounds for Algorithm-Based Fault Tolerance.
IEEE Trans. Computers, 1993

The Complexity of Processing Hierarchical Specifications.
SIAM J. Comput., 1993

Determining Performance Measures of Algorithm-Based Fault Tolerant Systems.
J. Parallel Distributed Comput., 1993

Many birds with one stone: multi-objective approximation algorithms.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Exploiting Data Flow Information in Algorithm-Based Fault Tolerance.
Proceedings of the Digest of Papers: FTCS-23, 1993

Compact Location Problems.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1993

1992
Representability of Design Objects by Ancestor-Controlled Hierarchical Specifications.
SIAM J. Comput., 1992

The Complexity of STructural Containment and Equivalence.
Proceedings of the Theoretical Studies in Computer Science, 1992

1991
Using the Dual Path Property of Omega Networks to Obtain Conflict-Free Message Routing.
IEEE Trans. Parallel Distributed Syst., 1991

An Efficient Method for Representing and Transmitting Message Patterns on Multiprocessor Interconnection Networks.
J. Parallel Distributed Comput., 1991

Compaction of Message Patterns into Succinct Representations for Multiprocessor Interconnection Networks.
J. Parallel Distributed Comput., 1991

Sufficient-Completeness, Ground-Reducibility and their Complexity.
Acta Informatica, 1991

A Linear-Time Scheme for Version Reconstruction (Extended Abstract).
Proceedings of the Algorithms and Data Structures, 1991

Facility Dispersion Problems: Heuristics and Special Cases (Extended Abstract).
Proceedings of the Algorithms and Data Structures, 1991

Construction and Analysis of Fault-Secure Multiprocessor Schedules.
Proceedings of the 1991 International Symposium on Fault-Tolerant Computing, 1991

1990
Half-Hot State Assignments for Finite State Machines.
IEEE Trans. Computers, 1990

Minimizing Time-Space Cost for Database Version Control.
Acta Informatica, 1990

Design and analysis of test schemes for algorithm-based fault tolerance.
Proceedings of the 20th International Symposium on Fault-Tolerant Computing, 1990

1989
The Complexity of Generating Minimum Test Sets for PLA's and Monotone Combinational Circuits.
IEEE Trans. Computers, 1989

Compaction of Message Patterns into Space-Efficient Representations for Multiprocessor Interconnection Networks.
Proceedings of the International Conference on Parallel Processing, 1989

1988
Matrix Multiplication for Finite Algebraic Systems.
Inf. Process. Lett., 1988

1987
Efficient Algorithms for Automatic Construction and Compactification of Parsing Grammars.
ACM Trans. Program. Lang. Syst., 1987

On the Computational Complexity of Algebra on Lattices.
SIAM J. Comput., 1987

1986
Recursion Schemes and Recursive Programs are Exponentially Hard to Analyze.
SIAM J. Comput., 1986

1985
Testing for Grammatical Coverings.
Theor. Comput. Sci., 1985

1984
Consistency and Serializability in Concurrent Database Systems.
SIAM J. Comput., 1984

The Complexity of Monadic Recursion Schemes: Exponential Time Bounds.
J. Comput. Syst. Sci., 1984

Algebraic Structures with Hard Equivalence and Minimization Problems.
J. ACM, 1984

1983
The Complexity of Monadic Recursion Schemes: Executability Problems, Nesting Depth, and Applications.
Theor. Comput. Sci., 1983

1981
Distributed Database Concurrency Controls Using Before-Values.
Proceedings of the 1981 ACM SIGMOD International Conference on Management of Data, Ann Arbor, Michigan, USA, April 29, 1981

1980
Processing Conjunctive Predicates and Queries.
Proceedings of the Sixth International Conference on Very Large Data Bases, 1980

Efficient Algorithms for Structural Similarity of Grammars.
Proceedings of the Conference Record of the Seventh Annual ACM Symposium on Principles of Programming Languages, 1980

The Complexity of Recursion Schemes and Recursive Programming Languages (Extended Abstract)
Proceedings of the 21st Annual Symposium on Foundations of Computer Science, 1980

1979
The Complexity of Testing Predicate Locks.
Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data, Boston, Massachusetts, USA, May 30, 1979

1978
System Level Concurrency Control for Distributed Database Systems.
ACM Trans. Database Syst., 1978

Polynomial Algorithms for Deterministic Pushdown Automata.
SIAM J. Comput., 1978

Computational Parallels Between the Regular and Context-Free Languages.
SIAM J. Comput., 1978

Dynamic Database Dumping.
Proceedings of the 1978 ACM SIGMOD International Conference on Management of Data, Austin, Texas, USA, May 31, 1978

1977
An Analysis of Several Heuristics for the Traveling Salesman Problem.
SIAM J. Comput., 1977

On Equivalence and Containment Problems for Formal Languages.
J. ACM, 1977

1976
The Covering Problem for Linear Context-Free Grammars.
Theor. Comput. Sci., 1976

On the Equivalence, Containment, and Covering Problems for the Regular and Context-Free Languages.
J. Comput. Syst. Sci., 1976

Concurrency Control for Database Systems
Proceedings of the 17th Annual Symposium on Foundations of Computer Science, 1976

1974
Attributed Translations.
J. Comput. Syst. Sci., 1974

Approximate Algorithms for the Traveling Salesperson Problem
Proceedings of the 15th Annual Symposium on Switching and Automata Theory, 1974

1970
Properties of Deterministic Top-Down Grammars
Inf. Control., October, 1970

Deterministic Left Corner Parsing (Extended Abstract)
Proceedings of the 11th Annual Symposium on Switching and Automata Theory, 1970

1969
Programmed Grammars and Classes of Formal Languages.
J. ACM, 1969

Table Machine Simulation
Proceedings of the 10th Annual Symposium on Switching and Automata Theory, 1969

1967
Matrix Equations and Normal Forms for Context-Free Grammars.
J. ACM, 1967

Programmed Grammars: A New Device for Generating Formal Languages
Proceedings of the 8th Annual Symposium on Switching and Automata Theory, 1967

1966
Synchronizing Sequences for Incompletely Specified Flow Tables.
IEEE Trans. Electron. Comput., 1966


  Loading...