James S. Royer

CoRR, 2022

2016

Program Size Complexity of Correction Grammars in the Ershov Hierarchy.

[BibT_eX]

[DOI]

John Case

Proceedings of the Pursuit of the Universal - 12th Conference on Computability in Europe, 2016

2013

A static cost analysis for a higher-order language.

[BibT_eX]

[DOI]

Jennifer Paykin

Proceedings of the 7th Workshop on Programming languages meets program verification, 2013

2012

Semi-automatic complexity analysis of a higher-order language

[BibT_eX]

[DOI]

Jennifer Paykin

CoRR, 2012

Ramified Structural Recursion and Corecursion

[BibT_eX]

[DOI]

CoRR, 2012

2011

Axiomatizing Resource Bounds for Measure.

[BibT_eX]

[DOI]

Proceedings of the Models of Computation in Context, 2011

2009

Two Algorithms in Search of a Type-System.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2009

2007

Adventures in time and space.

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2007

Time-complexity semantics for feasible affine recursions (extended abstract)

[BibT_eX]

[DOI]

CoRR, 2007

Time-Complexity Semantics for Feasible Affine Recursions.

[BibT_eX]

[DOI]

Proceedings of the Computation and Logic in the Real World, 2007

2006

Generality's price: Inescapable deficiencies in machine-learned programs.

[BibT_eX]

[DOI]

Ann. Pure Appl. Log., 2006

2004

On the computational complexity of Longley's H functional.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2004

Every polynomial-time 1-degree collapses if and only if P = PSPACE.

[BibT_eX]

[DOI]

Stephen A. Fenner

J. Symb. Log., 2004

2001

On characterizations of the basic feasible functionals (Part I).

[BibT_eX]

[DOI]

Robert J. Irwin

Bruce M. Kapron

J. Funct. Program., 2001

1998

A Hierarchy Based on Output Multiplicity.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1998

1997

Semantics vs Syntax vs Computations: Machine Models for Type-2 Polynomial-Time Bounded Functionals.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1997

1996

Active transport in biological computing.

[BibT_eX]

[DOI]

Proceedings of the DNA Based Computers, 1996

1995

On Closure Properties of Bounded Two-Sided Error Complexity Classes.

[BibT_eX]

[DOI]

Kenneth W. Regan

Math. Syst. Theory, 1995

The Isomorphism Conjecture Fails Relative to a Random Oracle.

[BibT_eX]

[DOI]

J. ACM, 1995

Semantics versus Syntax versus Computations.

[BibT_eX]

[DOI]

Proceedings of the Tenth Annual Structure in Complexity Theory Conference, 1995

1994

Subrecursive programming systems - complexity and succinctness.

[BibT_eX]

John Case

Progress in theoretical computer science, Birkhäuser, ISBN: 978-3-7643-3767-4, 1994

1993

On A-Truth-Table-Hard Languages.

[BibT_eX]

[DOI]

Steven Homer

Theor. Comput. Sci., 1993

1992

Average Dependence and Random Oracles.

[BibT_eX]

[DOI]

Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992

1989

Two Recursion Theoretic Characterizations of Proof Speed-Ups.

[BibT_eX]

[DOI]

J. Symb. Log., 1989

The Isomorphism Conjecture Fails Relative to a Random Oracle (Extended Abstract)

[BibT_eX]

[DOI]

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

Every Polynomial-Time 1-Degree Collapses iff P=PSPACE

[BibT_eX]

[DOI]

Stephen A. Fenner

Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

The Isomorphism Conjecture Fails Relative to a Random Oracle (abstract).

[BibT_eX]

[DOI]

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

1988

Collapsing Degrees.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1988

On the Power of 1-way Functions (Abstract).

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 1988

Prudence in Language Learning.

[BibT_eX]

[DOI]

Proceedings of the First Annual Workshop on Computational Learning Theory, 1988

1987

How to Prove Representation-Independent Independence Results.

[BibT_eX]

[DOI]

Michael J. O'Donnell

Inf. Process. Lett., 1987

Progress on collapsing degrees.

[BibT_eX]

[DOI]

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

A Connotational Theory of Program Structure

[BibT_eX]

[DOI]

Lecture Notes in Computer Science 273, Springer, ISBN: 3-540-18253-5, 1987

1986

Inductive Inference of Approximations

[BibT_eX]

[DOI]

Inf. Control., 1986

Collapsing Degrees (Extended Abstract)

[BibT_eX]

[DOI]