Daniel J. Rosenkrantz

According to our database1, Daniel J. Rosenkrantz
  • authored at least 130 papers between 1966 and 2017.
  • has a "Dijkstra number"2 of four.

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 
Other 

Links

On csauthors.net:

Bibliography

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. Services Computing, 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.
Journal of Software Maintenance, 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*.
Data Min. Knowl. Discov., 2006

2005
In memory of Seymour Ginsburg 1928 - 2004.
SIGMOD Record, 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.
European Journal of Operational Research, 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 Record, 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 Journal on Computing, 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.
International Journal of Parallel Programming, 1999

1998
Bicriteria Network Design Problems.
J. Algorithms, 1998

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

Bicriteria Network Design Problems
CoRR, 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. Discrete 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

Bicriteria Network Design Problems.
Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 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 Distrib. 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.
Operations Research, 1994

Geometry based heuristics for unit disk graphs.
CoRR, 1994

Spanning Trees Short or Small.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 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 Distrib. 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 Distrib. Syst., 1991

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

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

Sufficient-Completeness, Ground-Reducibility and their Complexity.
Acta Inf., 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 Inf., 1990

Representability of Design Objects by Ancestor-Controlled Hierarchical Specifications.
Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 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

Minimizing Time-Space Cost For Database Version Control.
Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 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, 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, 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, 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

A System Level Concurrency Control for Distributed Database Systems.
Berkeley Workshop, 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

Computational Parallels between the Regular and Context-Free Languages
Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30, 1974

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

1973
Attributed Translations
Proceedings of the 5th Annual ACM Symposium on Theory of Computing, April 30, 1973

1970
Properties of Deterministic Top-Down Grammars
Information and 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

Properties of Deterministic Top Down Grammars
Proceedings of the 1st Annual ACM Symposium on Theory of Computing, 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. Electronic Computers, 1966


  Loading...