Juris Hartmanis

Proceedings of the How the World Computes, 2012

The Turing Computational Model.

[BibT_eX]

[DOI]

Stephen Cook

William Kahan

Andrew C. Yao

Proceedings of the ACM Turing Centenary Celebration, 2012

2003

Separation of complexity classes.

[BibT_eX]

[DOI]

J. ACM, 2003

2002

The Separation Problems and Descriptional Complexity.

[BibT_eX]

Proceedings of the Fourth International Workshop on Descriptional Complexity of Formal Systems - DCFS 2002, London, Canada, August 21, 2002

2001

Computational Complexity and Mathematical Proofs.

[BibT_eX]

[DOI]

Proceedings of the Informatics - 10 Years Back. 10 Years Ahead., 2001

2000

Undecidability and Incompleteness Results in Automata Theory.

[BibT_eX]

Proceedings of the A Half-Century of Automata Theory: Celebration and Inspiration, 2000

1999

Observations about the Nature and State of Computer Science (Keynote Address).

[BibT_eX]

[DOI]

Proceedings of the Automata, 1999

1998

Innovation and Obstacles: The Future of Computing.

[BibT_eX]

[DOI]

Computer, 1998

1995

On the Weight of Computations.

[BibT_eX]

Bull. EATCS, 1995

Response to the Essays "On Computational Complexity and the Nature of Computer Science".

[BibT_eX]

[DOI]

ACM Comput. Surv., 1995

Turing Award Lecture: On Computational Complexity and the Nature of Computer Science.

[BibT_eX]

[DOI]

ACM Comput. Surv., 1995

On the Computing Paradigm and Computational Complexity.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1995, 1995

1994

The Random Oracle Hypothesis Is False.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1994

On Hausdorff and Topological Dimensions of the Kolmogorov Complexity of the Real Line.

[BibT_eX]

[DOI]

Jin-yi Cai

J. Comput. Syst. Sci., 1994

About the Nature of the Computer Science.

[BibT_eX]

Bull. EATCS, 1994

The Structure of the Complexity of Computations: A Guided Tour Through Complexity Classes.

[BibT_eX]

Proceedings of the Technology and Foundations - Information Processing '94, Volume 1, Proceedings of the IFIP 13th World Computer Congress, Hamburg, Germany, 28 August, 1994

On the Intellectual Terrain Around NP.

[BibT_eX]

[DOI]

Suresh Chari

Proceedings of the Algorithms and Complexity, Second Italian Conference, 1994

1993

On IP = PSPACE and Theorems with Narrow Proofs.

[BibT_eX]

[DOI]

Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

Some Observations about Relativization of Space Bounded Computations.

[BibT_eX]

[DOI]

Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

Relativization: a Revisionistic Retrospective.

[BibT_eX]

[DOI]

Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

Gödel, von Neumann and the P =? NP Problem.

[BibT_eX]

[DOI]

Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

On the Importance of Being II<sub>2</sub>-Hard.

[BibT_eX]

[DOI]

Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

Collapsing Hierarchies.

[BibT_eX]

[DOI]

Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

Sparse Complete Sets for NP and the Optimal Collapse of the Polynomial Hierarchy.

[BibT_eX]

[DOI]

Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

A Retrospective on Structural Complexity.

[BibT_eX]

[DOI]

Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

Structural Complexity.

[BibT_eX]

[DOI]

Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

A Broader Research Agenda for Theory.

[BibT_eX]

Bull. EATCS, 1993

Some Observations About the Nature of Computer Science.

[BibT_eX]

[DOI]

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1993

Computing the Future: Whither Computer Science and Engineering?

[BibT_eX]

[DOI]

Proceedings of the ACM 21th Conference on Computer Science, 1993

1992

Computing the Future - Comittee to Assess the Scope and Direction of Computer Science and Technology of the National Research Council.

[BibT_eX]

[DOI]

Commun. ACM, 1992

1991

Space Bounded Computations: Review and New Separation Results.

[BibT_eX]

[DOI]

Desh Ranjan

Richard Chang

Theor. Comput. Sci., 1991

One-Way Functions and the Nonisomorphism of NP-Complete Sets.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1991

1990

Robust Machines Accept Easy Sets.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1990

New Developments in Structural Complexity Theory.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1990

On Unique Staisfiability and Randomized Reductions.

[BibT_eX]

Bull. EATCS, 1990

Structural Complexity Theory: recent Surprises.

[BibT_eX]

[DOI]

Proceedings of the SWAT 90, 1990

1989

The Boolean Hierarchy II: Applications.

[BibT_eX]

[DOI]

SIAM J. Comput., 1989

The Cornell Commission: On Morris and the Worm.

[BibT_eX]

[DOI]

Commun. ACM, 1989

Space Bounded Computations: Review And New Separation Results.

[BibT_eX]

[DOI]

Desh Ranjan

Proceedings of the Mathematical Foundations of Computer Science 1989, 1989

The Complexity Of The Real Line Is A Fractal.

[BibT_eX]

[DOI]

Jin-yi Cai

Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989

Feasible computations and provable complexity properties.

[BibT_eX]

CBMS-NSF regional conference series in applied mathematics 30, SIAM, ISBN: 978-0-89871-027-4, 1989

1988

Complexity Classes without Machines: On Complete Languages for UP.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1988

The Boolean Hierarchy I: Structural Properties.

[BibT_eX]

[DOI]

SIAM J. Comput., 1988

On Sparse Oracles Separating Feasible Complexity Classes.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1988

The Structural Complexity Column.

[BibT_eX]

Bull. EATCS, 1988

1987

Structural Complexity Columns in Sparse complete sets for NP and the optimal collpase of the polynomial hierarchy.

[BibT_eX]

Bull. EATCS, 1987

Some Observations of NP Complete Sets.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 1987

One-way functions, robustness, and the non-isomorphism of NP-complete sets.

[BibT_eX]

[DOI]

Proceedings of the Second Annual Conference on Structure in Complexity Theory, 1987

1986

Pragmatic Aspects of Complexity Theory (Panel).

[BibT_eX]

Proceedings of the Information Processing 86, 1986

Containment, Separation, Complete Sets, and Immunity of Complexity Classes.

[BibT_eX]

[DOI]

Ming Li

Yaacov Yesha

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

1985

Independence Results About Context-Free Languages and Lower Bounds.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1985

Sparse Sets in NP-P: EXPTIME versus NEXPTIME

[BibT_eX]

[DOI]

Neil Immerman

Vivian Sewelson

Inf. Control., 1985

Solvable problems with conflicting relativizations.

[BibT_eX]

Bull. EATCS, 1985

On Complete Problems for NP$\cap$CoNP.

[BibT_eX]

[DOI]

Neil Immerman

Proceedings of the Automata, 1985

1984

Computation Times of NP Sets of Different Densities.

[BibT_eX]

[DOI]

Yaacov Yesha

Theor. Comput. Sci., 1984

On non-isomorphic NP complete sets.

[BibT_eX]

Bull. EATCS, 1984

1983

On Gödel Speed-Up and Succinctness of Language Representations.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1983

On Sparse Sets in NP - P.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1983

Generalized Kolmogorov Complexity and the Structure of Feasible Computations (Preliminary Report)

[BibT_eX]

[DOI]

Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

1982

A Note on Natural Complete Sets and Gödel Numberings.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1982

1981

Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata.

[BibT_eX]

[DOI]

Stephen R. Mahaney

SIAM J. Comput., 1981

Observations About the Development of Theoretical Computer Science.

[BibT_eX]

[DOI]

IEEE Ann. Hist. Comput., 1981

1980

On the Succinctness of Different Representations of Languages.

[BibT_eX]

[DOI]

SIAM J. Comput., 1980

An Eassay about Research on Sparse NP Complete Sets.

[BibT_eX]

[DOI]

Stephen R. Mahaney

Proceedings of the Mathematical Foundations of Computer Science 1980 (MFCS'80), 1980

1979

Relations Between Diagonalization, Proof Systems, and Complexity Gaps.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1979

Relative Succinctness of Representations of Languages and Separation of Complexity Classes.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1979, 1979

On the Succintness of Different Representations of Languages.

[BibT_eX]

[DOI]

Proceedings of the Automata, 1979

Succinctness, Verifiability and Determinism in Representations of Polynomial-Time Languages

[BibT_eX]

[DOI]

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

1978

On Log-Tape Isomorphisms of Complete Sets.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1978

On Polynomial Time Isomorphisms of Some New Complete Sets.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1978

One-Way Log-Tape Reductions

[BibT_eX]

[DOI]

Neil Immerman

Stephen R. Mahaney

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

1977

On Isomorphisms and Density of NP and Other Complete Sets.

[BibT_eX]

[DOI]

SIAM J. Comput., 1977

On polynomial time isomorphisms of complete sets.

[BibT_eX]

[DOI]

Proceedings of the Theoretical Computer Science, 1977

Relations Between Diagonalization, Proof Systems, and Complexity Gaps (Preliminary Version)

[BibT_eX]

[DOI]

Proceedings of the 9th Annual ACM Symposium on Theory of Computing, 1977

1976

On Tape Bounds for Single Letter Alphabet Language Processing.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1976

Independence results in computer science.

[BibT_eX]

[DOI]

SIGACT News, 1976

On Effective Speed-Up and Long Proofs of Trivial Theorems in Formal Theories.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 1976

On the Structure of Feasible Computations.

[BibT_eX]

[DOI]

Janos Simon

Adv. Comput., 1976

1975

On Simple Gödel Numberings and Translations.

[BibT_eX]

[DOI]

SIAM J. Comput., 1975

Computational Complexity of Formal Translations.

[BibT_eX]

[DOI]

Math. Syst. Theory, 1975

A Note on Tape Bounds for SLA Language Processing

[BibT_eX]

[DOI]

Proceedings of the 16th Annual Symposium on Foundations of Computer Science, 1975

1974

On Simple Goedel Numberings and Translations.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 2nd Colloquium, University of Saarbrücken, Germany, July 29, 1974

On the Structure of Feasible Computation.

[BibT_eX]

[DOI]

Janos Simon

Proceedings of the GI - 4. Jahrestagung, Berlin, 9.-12. Oktober 1974, 1974

On the Power of Multiplication in Random Access Machines

[BibT_eX]

[DOI]

Janos Simon

Proceedings of the 15th Annual Symposium on Switching and Automata Theory, 1974

1973

Group Theoretic Characterization of Linear Permutation Automata.

[BibT_eX]

[DOI]

H. Walter

J. Comput. Syst. Sci., 1973

On the Problem of Finding Natural Computational Complexity Measures.

[BibT_eX]

Proceedings of the Mathematical Foundations of Computer Science: Proceedings of Symposium and Summer School, 1973

1972

On Non-Determinancy in Simple Computing Devices.

[BibT_eX]

[DOI]

Acta Informatica, 1972

1971

Computational Complexity of Random Acess Stored Program Machines.

[BibT_eX]

[DOI]

Math. Syst. Theory, 1971

The use of Lists in the Study of Undecidable Problems in Automata Theory.

[BibT_eX]

[DOI]

Forbes D. Lewis

J. Comput. Syst. Sci., 1971

An Overview of the Theory of Computational Complexity.

[BibT_eX]

[DOI]

J. ACM, 1971

Complexity of Formal Translations and Speed-Up Results

[BibT_eX]

[DOI]

Robert L. Constable

Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, 1971

1970

R70-1 A Note on Computing Time for the Recognition of Context- Free Languages by a Single-Tape Turing Machine.

[BibT_eX]

[DOI]

IEEE Trans. Computers, 1970

Computer science and mathematics.

[BibT_eX]

[DOI]

ACM SIGCSE Bull., 1970

A Note on One-Way and Two-Way Automata.

[BibT_eX]

[DOI]

Math. Syst. Theory, 1970

What makes Some Language Theory Problems Undecidable.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1970

1969

Two Memory Bounds for the Recognition of Primes by Automata.

[BibT_eX]

[DOI]

H. Shank

Math. Syst. Theory, 1969

On the Complexity of Undecidable Problems in Automata Theory.

[BibT_eX]

[DOI]

J. ACM, 1969

Automata-based computational complexity.

[BibT_eX]

[DOI]

Inf. Sci., 1969

1968

Tape-Reversal Bounded Turing Machine Computations.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1968

On the Recognition of Primes by Automata.

[BibT_eX]

[DOI]

H. Shank

J. ACM, 1968

Computational Complexity of One-Tape Turing Machine Computations.

[BibT_eX]

[DOI]

J. ACM, 1968

Structure of Undecidable Problems in Automata Theory

[BibT_eX]

[DOI]

Proceedings of the 9th Annual Symposium on Switching and Automata Theory, 1968

Tape Reversal Complexity Hierarchies

[BibT_eX]

[DOI]

Patrick C. Fischer

Manuel Blum

Proceedings of the 9th Annual Symposium on Switching and Automata Theory, 1968

1967

Homomorphic Images of Linear Sequential Machines.

[BibT_eX]

[DOI]

Wayne A. Davis

J. Comput. Syst. Sci., 1967

On Memory Requirements for Context-Free Language Recognition.

[BibT_eX]

[DOI]

J. ACM, 1967

1966

Minimal Feedback Realizations of Sequential Machines.

[BibT_eX]

[DOI]

IEEE Trans. Electron. Comput., 1966

1965

Two Tests for the Linearity of Sequential Machines.

[BibT_eX]

[DOI]

IEEE Trans. Electron. Comput., 1965

Hierarchies of memory limited computations

[BibT_eX]

[DOI]

Philip M. Lewis II

Proceedings of the 6th Annual Symposium on Switching Circuit Theory and Logical Design, 1965

Memory bounds for recognition of context-free and context-sensitive languages

[BibT_eX]

[DOI]

Philip M. Lewis II

Proceedings of the 6th Annual Symposium on Switching Circuit Theory and Logical Design, 1965

1964

Pair Algebra and Its Application to Automata Theory

[BibT_eX]

[DOI]

Inf. Control., December, 1964

On the application of pair algebra to automata theory

[BibT_eX]

[DOI]

Proceedings of the 5th Annual Symposium on Switching Circuit Theory and Logical Design, 1964

Computational complexity of recursive sequences

[BibT_eX]

[DOI]

Proceedings of the 5th Annual Symposium on Switching Circuit Theory and Logical Design, 1964

1963

Regularity Preserving Modifications of Regular Expressions

[BibT_eX]

[DOI]

Inf. Control., March, 1963

A Study of Feedback and Errors in Sequential Machines.

[BibT_eX]

[DOI]

IEEE Trans. Electron. Comput., 1963

Further Results on the Structure of Sequential Machines.

[BibT_eX]

[DOI]

J. ACM, 1963

1962

Some Dangers in State Reduction of Sequential Machines

[BibT_eX]

[DOI]

Inf. Control., September, 1962

Loop-Free Structure of Sequential Machines

[BibT_eX]

[DOI]

Inf. Control., March, 1962

Maximal Autonomous Clocks of Sequential Machines.

[BibT_eX]

[DOI]

IRE Trans. Electron. Comput., 1962

1961

On the State Assignment Problem for Sequential Machines II.

[BibT_eX]

[DOI]

IRE Trans. Electron. Comput., 1961

On the State Assignment Problem for Sequential Machines. I.

[BibT_eX]

[DOI]

IRE Trans. Electron. Comput., 1961

1960

Symbolic Analysis of a Decomposition of Information Processing Machines

[BibT_eX]

[DOI]

Inf. Control., June, 1960

1959

The Applications of Some Basic Inequalities for Entropy

[BibT_eX]

[DOI]