Zvi Galil

Commun. ACM, 2022

Efficient Graph Isomorphism Query Processing using Degree Sequences and Color-Label Distributions.

[BibT_eX]

[DOI]

Proceedings of the 38th IEEE International Conference on Data Engineering, 2022

2021

Scalable Graph Isomorphism: Combining Pairwise Color Refinement and Backtracking via Compressed Candidate Space.

[BibT_eX]

[DOI]

Proceedings of the 37th IEEE International Conference on Data Engineering, 2021

2020

OMSCS: the revolution will be digitized.

[BibT_eX]

[DOI]

Commun. ACM, 2020

2016

40 years of suffix trees.

[BibT_eX]

[DOI]

Commun. ACM, 2016

2014

Real-Time Streaming String-Matching.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2014

2013

Forty Years of Text Indexing.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Pattern Matching, 24th Annual Symposium, 2013

2010

Old and New in Stringology.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Pattern Matching, 21st Annual Symposium, 2010

2004

Three-Dimensional Periodicity and Its Application to Pattern Matching.

[BibT_eX]

[DOI]

Jong Geun Park

SIAM J. Discret. Math., 2004

Parallel two dimensional witness computation.

[BibT_eX]

[DOI]

Inf. Comput., 2004

2002

Lower Bounds for Dynamic Data Structures on Algebraic RAMs.

[BibT_eX]

[DOI]

Algorithmica, 2002

2001

Topological Lower Bounds on Algebraic Random Access Machines.

[BibT_eX]

[DOI]

SIAM J. Comput., 2001

A Generalization of a Lower Bound Technique due to Fredman and Saks.

[BibT_eX]

[DOI]

Algorithmica, 2001

2000

Eavesdropping games: a graph-theoretic approach to privacy in distributed systems.

[BibT_eX]

[DOI]

Matthew K. Franklin

J. ACM, 2000

1999

Fully Dynamic Planarity Testing with Applications.

[BibT_eX]

[DOI]

Neil Sarnak

J. ACM, 1999

Dynamic Graph Algorithms.

[BibT_eX]

[DOI]

David Eppstein

Proceedings of the Algorithms and Theory of Computation Handbook., 1999

1998

Separator-Based Sparsification II: Edge and Vertex Connectivity.

[BibT_eX]

[DOI]

SIAM J. Comput., 1998

1997

Constant-Time Randomized Parallel String Matching.

[BibT_eX]

[DOI]

SIAM J. Comput., 1997

All Pairs Shortest Paths for Graphs with Small Integer Length Edges.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1997

On the Exponent of the All Pairs Shortest Path Problem.

[BibT_eX]

[DOI]

Noga Alon

J. Comput. Syst. Sci., 1997

Sparsification - a technique for speeding up dynamic graph algorithms.

[BibT_eX]

[DOI]

J. ACM, 1997

All Pairs Shortest Distances for Graphs with Small Integer Length Edges.

[BibT_eX]

[DOI]

Inf. Comput., 1997

Three-Dimensional Pattern Matching.

[BibT_eX]

[DOI]

Jong Geun Park

Proceedings of the 9th Annual ACM Symposium on Parallel Algorithms and Architectures, 1997

Open Problems In Stringology, Thirteen years Later.

[BibT_eX]

[DOI]

Proceedings of the Compression and Complexity of SEQUENCES 1997, 1997

Off-line parallel exact string searching.

[BibT_eX]

I. Yudkiewicz

Proceedings of the Pattern Matching Algorithms, 1997

1996

Alphabet-Independent Two-Dimensional Witness Computation.

[BibT_eX]

[DOI]

SIAM J. Comput., 1996

Separator Based Sparsification. I. Planary Testing and Minimum Spanning Trees.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1996

1995

On the Power of the Shift Instruction

[BibT_eX]

[DOI]

Inf. Comput., February, 1995

Parallel Detection of all Palindromes in a String.

[BibT_eX]

[DOI]

Alberto Apostolico

Theor. Comput. Sci., 1995

A Constant-Time Optimal Parallel String-Matching Algorithm.

[BibT_eX]

[DOI]

J. ACM, 1995

On Data Structure Tradeoffs and an Application to Union-Find

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1995

Finding All Periods and Initial Palindromes of a String in Parallel.

[BibT_eX]

[DOI]

Algorithmica, 1995

Short length versions of Menger's theorem (Extended Abstract).

[BibT_eX]

[DOI]

Xiangdong Yu

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Work-time-optimal parallel algorithms for string problems.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Sensing Versus Nonsensing Automata.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

Lower Bounds on Algebraic Random Access Machines (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

Resolving Message Complexity of Byzantine Agreement and beyond.

[BibT_eX]

[DOI]

Alain J. Mayer

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

Efficient Dynamic-Resharing "Verifiable Secret Sharing" Against Mobile Adversary.

[BibT_eX]

[DOI]

Noga Alon

Proceedings of the Algorithms, 1995

1994

Parallel Algorithms for Dynamic Programming Recurrences with More than O(1) Dependency.

[BibT_eX]

[DOI]

J. Parallel Distributed Comput., 1994

Dynamic Dictionary Matching.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1994

Faster Tree Pattern Matching.

[BibT_eX]

[DOI]

Moshe Dubiner

Edith Magen

J. ACM, 1994

1993

On the Power of Multiple Reads in a Chip

[BibT_eX]

[DOI]

Inf. Comput., June, 1993

Maintaining the 3-Edge-Connected Components of a Graph On-Line.

[BibT_eX]

[DOI]

SIAM J. Comput., 1993

Witnesses for Boolean Matrix Multiplication and for Transitive Closure.

[BibT_eX]

[DOI]

J. Complex., 1993

Efficient Comparison Based String Matching.

[BibT_eX]

[DOI]

J. Complex., 1993

Separator based sparsification for dynamic planar graph algorithms.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions

[BibT_eX]

[DOI]

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

When can we sort in o(n log n) time?

[BibT_eX]

[DOI]

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1992

On the Space Complexity of Some Algorithms for Sequence Comparison.

[BibT_eX]

[DOI]

Yuval Rabani

Theor. Comput. Sci., 1992

Dynamic Programming with Convexity, Concavity, and Sparsity.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1992

Renato Capocelli.

[BibT_eX]

[DOI]

SIGACT News, 1992

Fully Dynamic Algorithms for 2-Edge Connectivity.

[BibT_eX]

[DOI]

SIAM J. Comput., 1992

On the Exact Complexity of String Matching: Upper Bounds.

[BibT_eX]

[DOI]

SIAM J. Comput., 1992

A Lower Bound for Parallel String Matching.

[BibT_eX]

[DOI]

SIAM J. Comput., 1992

Sparse Dynamic Programming II: Convex and Concave Cost Functions.

[BibT_eX]

[DOI]

J. ACM, 1992

Sparse Dynamic Programming I: Linear Cost Functions.

[BibT_eX]

[DOI]

J. ACM, 1992

On Pointers versus Addresses.

[BibT_eX]

[DOI]

J. ACM, 1992

Fully Dynamic Planarity Testing (Extended Abstract)

[BibT_eX]

[DOI]

Neil Sarnak

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Optimal Parallel Algorithms for Periods, Palindromes and Squares (Extended Abstract).

[BibT_eX]

[DOI]

Alberto Apostolico

Proceedings of the Automata, Languages and Programming, 19th International Colloquium, 1992

Truly Alphabet-Independent Two-Dimensional Pattern Matching

[BibT_eX]

[DOI]

Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

Sparsification-A Technique for Speeding up Dynamic Graph Algorithms (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

Witnesses for Boolean Matrix Multiplication and for Shortest Paths

[BibT_eX]

[DOI]

Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

1991

Classification of All the Minimal Bilinear Algorithms for Computing the Coefficients of the Product of Two Polynomials Modulo a Polynomial. Part II: The Algebra G[u]/<u^n>.

[BibT_eX]

[DOI]

Amir Averbuch

Shmuel Winograd

Theor. Comput. Sci., 1991

Reducing edge connectivity to vertex connectivity.

[BibT_eX]

[DOI]

SIGACT News, 1991

An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem.

[BibT_eX]

[DOI]

SIAM J. Comput., 1991

On the Exact Complexity of String Matching: Lower Bounds.

[BibT_eX]

[DOI]

SIAM J. Comput., 1991

Two Lower Bounds in Asynchronous Distributed Computation.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1991

A Note on Set Union with Arbitrary Deunions.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1991

Data Structures and Algorithms for Disjoint Set Union Problems.

[BibT_eX]

[DOI]

ACM Comput. Surv., 1991

Fully Dynamic Algorithms for Edge-Connectivity Problems (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Maintaining Biconnected Components of Dynamic Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 18th International Colloquium, 1991

Lower Bounds for Data Structure Problems on RAMs (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

1990

An Improved Algorithm for Approximate String Matching.

[BibT_eX]

[DOI]

SIAM J. Comput., 1990

An Optimal O(log log n) Time Parallel String Matching Algorithm.

[BibT_eX]

[DOI]

SIAM J. Comput., 1990

A Linear-Time Algorithm for Concave One-Dimensional Dynamic Programming.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1990

Sparse Dynamic Programming.

[BibT_eX]

[DOI]

Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990

Recent Progress in String Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 1990

On the Exact Complexity of String Matching (Extended Abstract)

[BibT_eX]

[DOI]

Livio Colussi

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1989

Speeding up Dynamic Programming with Applications to Molecular Biology.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1989

Minimum-Knowledge Interactive Proofs for Decision Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 1989

On Nontrivial Separators for k-Page Graphs and Simulations by Nondeterministic One-Tape Turing Machines.

[BibT_eX]

[DOI]

Ravi Kannan

Endre Szemerédi

J. Comput. Syst. Sci., 1989

Solving dense subset-sum problems by using analytical number theory.

[BibT_eX]

[DOI]

Mark Chaimovich

Gregory Freiman

J. Complex., 1989

Efficient implementation of graph algorithms using contraction.

[BibT_eX]

[DOI]

Harold N. Gabow

Thomas H. Spencer

J. ACM, 1989

Parallel Evaluation of the Determinant and of the Inverse of a Matrix.

[BibT_eX]

[DOI]

Victor Y. Pan

Inf. Process. Lett., 1989

On 3-pushdown graphs with large separators.

[BibT_eX]

[DOI]

Ravi Kannan

Endre Szemerédi

Comb., 1989

Highly Parallelizable Problems (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

Speech Recognition in Parallel.

[BibT_eX]

[DOI]

Proceedings of the Speech and Natural Language: Proceedings of a Workshop Held at Cape Cod, 1989

Parallel Algorithmic Techniques for Combinatorial Computation.

[BibT_eX]

[DOI]

David Eppstein

Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

A Secure Public-key Authentication Scheme.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 1989

Security against Replay Chosen-Ciphertext Attack.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing And Cryptography, 1989

1988

Classification of All the Minimal Bilinear Algorithms for Computing the Coefficients of the Product of Two Polynomials Modulo a Polynomial, Part I: The Algeabra G[u] / < Q(u)^l >, l > 1.

[BibT_eX]

[DOI]

Amir Averbuch

Shmuel Winograd

Theor. Comput. Sci., 1988

Data structures and algorithms for approximate string matching.

[BibT_eX]

[DOI]

J. Complex., 1988

An O(n²(m + n log n)log n) min-cost flow algorithm.

[BibT_eX]

[DOI]

Éva Tardos

J. ACM, 1988

On finding most uniform spanning trees.

[BibT_eX]

[DOI]

Baruch Schieber

Discret. Appl. Math., 1988

Improved processor bounds for combinatorial problems in RNC.

[BibT_eX]

[DOI]

Victor Y. Pan

Comb., 1988

Speeding up Dynamic Programming

[BibT_eX]

[DOI]

David Eppstein

Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

On Pointers versus Addresses (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

1987

Lower Bounds on Communication Complexity

[BibT_eX]

[DOI]

Georg Schnitger

Inf. Comput., April, 1987

Distributed Algorithms in Synchronous Broadcasting Networks.

[BibT_eX]

[DOI]

Gad M. Landau

Mordechai M. Yung

Theor. Comput. Sci., 1987

Parallel String Matching with k Mismatches.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1987

Better Expanders and Superconcentrators.

[BibT_eX]

[DOI]

Noga Alon

V. D. Milman

J. Algorithms, 1987

An O(n³log n) deterministic and an O(n³) Las Vegs isomorphism test for trivalent graphs.

[BibT_eX]

[DOI]

Christoph M. Hoffmann

Eugene M. Luks

Claus-Peter Schnorr

Andreas Weber

J. ACM, 1987

Partitioned Encryption and Achieving Simultaneity by Partitioning.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1987

Two Lower Bounds in Asynchronous Distributed Computation (Preliminary Version)

[BibT_eX]

[DOI]

Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

Cryptographic Computation: Secure Faut-Tolerant Protocols and the Public-Key Model.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 1987

1986

Improved string matching with k mismatches.

[BibT_eX]

[DOI]

SIGACT News, 1986

An O(EV log V) Algorithm for Finding a Maximal Weighted Matching in General Graphs.

[BibT_eX]

[DOI]

Silvio Micali

Harold N. Gabow

SIAM J. Comput., 1986

Efficient Algorithms for Finding Maximum Matching in Graphs.

[BibT_eX]

[DOI]

ACM Comput. Surv., 1986

Efficient algorithms for finding minimum spanning trees in undirected and directed graphs.

[BibT_eX]

[DOI]

Comb., 1986

Classification of all the Minimal Bilinear Algorithms for Computing the Coefficients of the Product of Two Polynomials Modulo a Polynomial.

[BibT_eX]

[DOI]

Amir Averbuch

Shmuel Winograd

Proceedings of the Automata, Languages and Programming, 13th International Colloquium, 1986

An O(n^2 (m + n log n) log n) Min-Cost Flow Algorithm

[BibT_eX]

[DOI]

Éva Tardos

Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

1985

Optimal Parallel Algorithms for String Matching

[BibT_eX]

[DOI]

Inf. Control., 1985

Distributed Algorithms in Synchronous Broadcasting Networks (Extended Abstract).

[BibT_eX]

[DOI]

Gad M. Landau

Mordechai M. Yung

Proceedings of the Automata, 1985

Improved Processor Bounds for Algebraic and Combinatorial Problems in RNC

[BibT_eX]

[DOI]

Victor Y. Pan

Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

A Private Interactive Test of a Boolean Predicate and Minimum-Knowledge Public-Key Cryptosystems (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

Symmetric Public-Key Encryption.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 1985

1984

Two Tapes are Better than One for Nondeterministic Machines.

[BibT_eX]

[DOI]

SIAM J. Comput., 1984

A Time-Space Tradeoff for Language Recognition.

[BibT_eX]

[DOI]

Math. Syst. Theory, 1984

Two Nonlinear Lower Bounds for On-Line Computations

[BibT_eX]

[DOI]

Inf. Control., 1984

1983

An Efficient General-Purpose Parallel Computer

[BibT_eX]

[DOI]

Wolfgang J. Paul

J. ACM, April, 1983

Time-Space-Optimal String Matching.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1983

NP Completeness of Finding the Chromatic Index of Regular Graphs.

[BibT_eX]

[DOI]

Daniel Leven

J. Algorithms, 1983

Two Nonlinear Lower Bounds

[BibT_eX]

[DOI]

Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

Efficient Algorithms for Finding Maximal Matching in Graphs.

[BibT_eX]

[DOI]

Proceedings of the CAAP'83, 1983

1982

On Reversal-Bounded Counter Machines and on Pushdown Automata with a Bound on the Size of their Pushdown Store

[BibT_eX]

[DOI]

Inf. Control., September, 1982

Fooling a two Way Automaton or one Pushdown Store is better than one Counter for two Way Machines.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1982

An Almost Linear-Time Algorithm for Computing a Dependency Basis in a Relational Database.

[BibT_eX]

[DOI]

J. ACM, 1982

Efficient Parallel Algorithms for Linear Recurrence Computation.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1982

On Reversal-Bounded Counter Machines and on Pushdown Automata with a Bound on the Size of the Pushdown Store.

[BibT_eX]

[DOI]

Proceedings of the Automata, 1982

Priority Queues with Variable Priority and an O(EV log V) Algorithm for Finding a Maximal Weighted Matching in General Graphs

[BibT_eX]

[DOI]

Silvio Micali

Harold N. Gabow

Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982

An O(n^3 log n) Deterministic and an O(n^3) Probabilistic Isomorphism Test for Trivalent Graphs

[BibT_eX]

[DOI]

Christoph M. Hoffmann

Eugene M. Luks

Claus-Peter Schnorr

Andreas Weber

Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982

1981

Linear-Time String-Matching Using only a Fixed Number of Local Storage Locations.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1981

On the Theoretical Efficiency of Various Network Flow Algorithms.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1981

Explicit Constructions of Linear-Sized Superconcentrators.

[BibT_eX]

[DOI]

Ofer Gabber

J. Comput. Syst. Sci., 1981

String Matching in Real Time.

[BibT_eX]

[DOI]

J. ACM, 1981

Fooling a Two-Way Automaton or One Pushdown Store Is Better Than One Counter for Two Way Machines (Preliminary Version)

[BibT_eX]

[DOI]

Proceedings of the 13th Annual ACM Symposium on Theory of Computing, 1981

1980

Saving Space in Fast String-Matching.

[BibT_eX]

[DOI]

SIAM J. Comput., 1980

Finding the Vertex Connectivity of Graphs.

[BibT_eX]

[DOI]

SIAM J. Comput., 1980

An O(EVlog²V) Algorithm for the Maximal Flow Problem.

[BibT_eX]

[DOI]

Amnon Naamad

J. Comput. Syst. Sci., 1980

An <i> O(V5/3 E2/3) </i> Algorithm for the Maximal Flow Problem.

[BibT_eX]

[DOI]

Acta Informatica, 1980

Applications of Efficient Mergeable Heaps for Optimization Problems on Trees.

[BibT_eX]

[DOI]

Acta Informatica, 1980

An Almost Linaer Time Algorithm for Computing a Dependency Basis in a Relational Data Base.

[BibT_eX]

[DOI]

Proceedings of the Automata, 1980

Effizienz Paralleler Rechner.

[BibT_eX]

[DOI]

Wolfgang J. Paul

Proceedings of the GI - 10. Jahrestagung, Saarbrücken, 30. September, 1980

1979

Storage Representations for Tree-Like Data Structures.

[BibT_eX]

[DOI]

Arnold L. Rosenberg

Derick Wood

Math. Syst. Theory, 1979

On Fulkerson's Conjecture About Consistent Labeling Processes.

[BibT_eX]

[DOI]

Nimrod Megiddo

Math. Oper. Res., 1979

A Fast Selection Algorithm and the Problem of Optimum Distribution of Effort.

[BibT_eX]

[DOI]

Nimrod Megiddo

J. ACM, 1979

On Improving the Worse Case Running Time of the Boyer-Moore String Matching Algorithm.

[BibT_eX]

[DOI]

Commun. ACM, 1979

Network Flow and Generalized Path Compression

[BibT_eX]

[DOI]

Amnon Naamad

Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30, 1979

Explicit Constructions of Linear Size Superconcentrators

[BibT_eX]

[DOI]

Ofer Gabber

Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979

1978

Killing two birds with one stone.

[BibT_eX]

[DOI]

SIGACT News, 1978

Palindrome Recognition in Real Time by a Multitape Turing Machine.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1978

A Linear-Time On-Line Recognition Algorithm for "Palstar".

[BibT_eX]

[DOI]

J. ACM, 1978

On Improving the Worst Case Running Time of the Boyer-Moore String Matching Algorithm.

[BibT_eX]

[DOI]

Proceedings of the Automata, 1978

A New Algorithm for the Maximal Flow Problem

[BibT_eX]

[DOI]

Proceedings of the 19th Annual Symposium on Foundations of Computer Science, 1978

1977

Cyclic Ordering is NP-Complete.

[BibT_eX]

[DOI]

Nimrod Megiddo

Theor. Comput. Sci., 1977

On the Complexity of Regular Resolution and the Davis-Putnam Procedure.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1977

On Resolution with Clauses of Bounded Size.

[BibT_eX]

[DOI]

SIAM J. Comput., 1977

Real-Time Recognition of Substring Repetition and Reversal.

[BibT_eX]

[DOI]

Math. Syst. Theory, 1977

Some Open Problems in the Theory of Computation as Questions about Two-Way Deterministic Pushdown Automaton Languages.

[BibT_eX]

[DOI]

Math. Syst. Theory, 1977

1976

A Note on Multiple-Entry Finite Automata.

[BibT_eX]

[DOI]

Janos Simon

J. Comput. Syst. Sci., 1976

Two Fast Simulations Which Imply Some Fast String Matching and Palindrome-Recognition Algorithms.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1976

Monotone switching circuits and boolean matrix product.

[BibT_eX]

[DOI]

Kurt Mehlhorn

Computing, 1976

Hierarchies of Complete Problems.

[BibT_eX]

[DOI]

Acta Informatica, 1976

Real-Time Algorithms for String-Matching and Palindrome Recognition

[BibT_eX]

[DOI]

Proceedings of the 8th Annual ACM Symposium on Theory of Computing, 1976

On Enumeration Procedures for Theorem Proving and for Integer Programming.

[BibT_eX]

Proceedings of the Third International Colloquium on Automata, 1976

Recognizing Certain Repetitions and Reversals Within Strings

[BibT_eX]

[DOI]

Proceedings of the 17th Annual Symposium on Foundations of Computer Science, 1976

1975

Functional Schemas with Nested Predicates

[BibT_eX]

[DOI]

Inf. Control., April, 1975

The Complexity of Resolution Procedures for Theorem Proving in the Propositional Calculus.

[BibT_eX]

PhD thesis, 1975

On converting on-line algorithms into real-time and on real-time algorithms for string-matching and palindrome recognition.

[BibT_eX]

[DOI]

SIGACT News, 1975

On the Validity and Complexity of Bounded Resolution

[BibT_eX]

[DOI]

Proceedings of the 7th Annual ACM Symposium on Theory of Computing, 1975

1974

On some direct encodings of nondeterministic Turing machines operating in polynomial time into p-complete problems.

[BibT_eX]

[DOI]

SIGACT News, 1974

Two Way Deterministic Pushdown Automaton Languages and Some Open Problems in the Theory of Computation

[BibT_eX]

[DOI]