Ronald V. Book

According to our database1, Ronald V. Book
  • authored at least 131 papers between 1968 and 1998.
  • has a "Dijkstra number"2 of four.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

1998
Probabilistic Type-2 Operators and "Almost"-Classes.
Computational Complexity, 1998

1996
On the Robustness of ALMOST-R.
ITA, 1996

On Random Hard Sets for NP.
Inf. Comput., 1996

Probabilistic Type-2 Operators and "Almost"-Classes
Electronic Colloquium on Computational Complexity (ECCC), 1996

On Type-2 Probabilistic Quantifiers.
Proceedings of the Automata, Languages and Programming, 23rd International Colloquium, 1996

1995
The Global Power of Additional Queries to Random Oracles
Inf. Comput., July, 1995

1994
Relativizations of the P =? NP and Other Problems: Developments in Structural Complexity Theory.
SIAM Review, 1994

On Languages Reducible to Algorithmically Random Languages.
SIAM J. Comput., 1994

An Observation on Probability Versus Randomness with Applications to Complexity Classes.
Mathematical Systems Theory, 1994

On Collapsing the Polynomial-Time Hierarchy.
Inf. Process. Lett., 1994

The Global Power of Additional Queries to Random Oracles.
Proceedings of the STACS 94, 1994

On Random Hard Sets for NP.
Proceedings of the Algorithms and Computation, 5th International Symposium, 1994

1993
A View of Structural Complexity Theory.
Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

On Languages With Very High Space-Bounded Kolmogorov Complexity.
SIAM J. Comput., 1993

Relativizing Complexity Classes With Random Oracles.
Proceedings of the Algorithms and Computation, 4th International Symposium, 1993

String-Rewriting Systems.
Texts and Monographs in Computer Science, Springer, ISBN: 978-1-4613-9771-7, 1993

1992
On Complexity Classes and Algorithmically Random Languages (Extended Abstract).
Proceedings of the STACS 92, 1992

Relativizations of the P =?NP and other Problems: Some Developments in Structural Complexity Theory.
Proceedings of the Algorithms and Computation, Third International Symposium, 1992

Additional Queries and Algorithmically Random Languages.
Proceedings of the Complexity Theory: Current Research, 1992

On Languages with Very High Information Content.
Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992

1991
Polynomial-Time Reducibilities and "Almost All" Oracle Sets.
Theor. Comput. Sci., 1991

Some Observations on Separating Complexity Classes.
SIAM J. Comput., 1991

Reducibilities on tally and sparse sets.
ITA, 1991

On "Inherently Context-Sensitive" Languages - An Application of Complexity Cores.
Inf. Process. Lett., 1991

On Random Oracle Separations.
Inf. Process. Lett., 1991

1990
Characterizing Polynomial Complexity Classes by Reducibilities.
Mathematical Systems Theory, 1990

A Note on Confluent Thue Systems.
Proceedings of the Word Equations and Related Topics, First International Workshop, 1990

Additional Queries to Random and Pseudorandom Oracles.
Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990

On Separating Complexity Classes.
Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

1989
On Inefficient Special Cases of NP-Complete Problems.
Theor. Comput. Sci., 1989

A Note on Sparse Sets and the Polynomial-Time Hierarchy.
Inf. Process. Lett., 1989

A view of structural complexity theory.
Bulletin of the EATCS, 1989

1988
The Structure of Generalized Complexity Cores.
Theor. Comput. Sci., 1988

Lowness Properties of Sets in the Exponential-Time Hierarchy.
SIAM J. Comput., 1988

On Sets Truth-Table Reducible to Sparse Sets.
SIAM J. Comput., 1988

Sparse Sets, Tally Sets, and Polynomial Reducibilities.
Proceedings of the Mathematical Foundations of Computer Science 1988, 1988

Separating Polynomial-Time Turing and Truth-Table Reductions by Tally Sets.
Proceedings of the Automata, Languages and Programming, 15th International Colloquium, 1988

On polynomial and generalized complexity cores.
Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

1987
Thue Systems as Rewriting Systems.
J. Symb. Comput., 1987

The existence and density of generalized complexity cores.
J. ACM, 1987

Rewriting Systems and Word Problems in a Free Partially Commutative Monoid.
Inf. Process. Lett., 1987

Towards a Theory of Relativizations: Positive Relativizations.
Proceedings of the STACS 87, 1987

On sets reducible to sparse sets.
Proceedings of the Second Annual Conference on Structure in Complexity Theory, 1987

1986
Sparse Sets, Lowness and Highness.
SIAM J. Comput., 1986

On Unification: Equational Theories Are Not Bounded.
J. Symb. Comput., 1986

The polynomial-time hierarchy and sparse oracles.
J. ACM, 1986

Sets with Small Generalized Kolmogorov Complexity.
Acta Inf., 1986

On Generalized Kolmogorov Complexity.
Proceedings of the STACS 86, 1986

On Exponential Lowness.
Proceedings of the Automata, Languages and Programming, 13th International Colloquium, 1986

1985
Reductions in Tree Replacement Systems.
Theor. Comput. Sci., 1985

On the Verifiability of Two-Party Algebraic Protocols.
Theor. Comput. Sci., 1985

On the Security of Name-Stamp Protocols.
Theor. Comput. Sci., 1985

On Bounded Query Machines.
Theor. Comput. Sci., 1985

Qualitative Relativizations of Complexity Classes.
J. Comput. Syst. Sci., 1985

Cancellation Rules and Extended Word Problems.
Inf. Process. Lett., 1985

The base of the intersection of two free submonoids.
Discrete Applied Mathematics, 1985

Thue Systems as Rewriting Systems.
Proceedings of the Rewriting Techniques and Applications, First International Conference, 1985

On the Unification Hierarchy.
Proceedings of the GWAI-85, 1985

The Verifiability of Two-Party Protocols.
Proceedings of the Advances in Cryptology, 1985

1984
Immunity, Relativizations, and Nondeterminism.
SIAM J. Comput., 1984

Quantitative Relativizations of Complexity Classes.
SIAM J. Comput., 1984

Characterizations of Reduction Classes Modulo Oracle Conditions.
Mathematical Systems Theory, 1984

On Expressing Commutativity by Finite Church-Rosser Presentations: A Note on Commutative Monoids.
ITA, 1984

Almost all one-rule thue systems have decidable word problems.
Discrete Mathematics, 1984

Homogeneous Thue systems and the Church-Rosser property.
Discrete Mathematics, 1984

Sparse Oracles, Lowness, and Highness.
Proceedings of the Mathematical Foundations of Computer Science 1984, 1984

Sparse Oracles and Uniform Complexity Classes
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

1983
Refining Nondeterminism in Relativizations of Complexity Classes
J. ACM, July, 1983

Decidable Sentences of Church-Rosser Congruences.
Theor. Comput. Sci., 1983

Positive Relativizations of Complexity Classes.
SIAM J. Comput., 1983

A Note on Special Thue Systems with a Single Defining Relation.
Mathematical Systems Theory, 1983

Controlled relativizations of P and NP.
Proceedings of the Theoretical Computer Science, 1983

Immunity (Extended Abstract).
Proceedings of the Automata, 1983

1982
Monadic Thue Systems.
Theor. Comput. Sci., 1982

When is a Monoid a Group? The Church-Rosser Case is Tractable.
Theor. Comput. Sci., 1982

Relativizing Time, Space, and Time-Space.
SIAM J. Comput., 1982

A Note on Complete Sets and Transitive Closure.
Mathematical Systems Theory, 1982

Confluent and Other Types of Thue Systems.
J. ACM, 1982

The Power of the Church-Rosser Property for String Rewriting Systems.
Proceedings of the 6th Conference on Automated Deduction, 1982

1981
Bounded Query Machines: On NP( ) and NPQERY( ).
Theor. Comput. Sci., 1981

Testing for the Church-Rosser Property.
Theor. Comput. Sci., 1981

Bounded Query Machines: On NP and PSPACE.
Theor. Comput. Sci., 1981

NTS Grammars and Church-Rosser Systems.
Inf. Process. Lett., 1981

The Undecidability of a Word Problem: On a Conjecture of Strong, Maggiolo-Schettini and Rosen.
Inf. Process. Lett., 1981

(Erasing)* Strings.
Proceedings of the Theoretical Computer Science, 1981

On the Complexity of Word Problems in Certain Thue Systems (Preliminary Report).
Proceedings of the Mathematical Foundations of Computer Science 1981, Strbske Pleso, Czechoslovakia, August 31, 1981

Relativizing Time and Space (Preliminary Report)
Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, 1981

1980
On Uniquely Decipherable Codes with Two Codewords.
IEEE Trans. Computers, 1980

Equality Sets and Complexity Classes.
SIAM J. Comput., 1980

1979
A Remark on Tally Languages and Complexity Classes
Information and Control, November, 1979

Polynomial Space and Transitive Closure.
SIAM J. Comput., 1979

Reset Machines.
J. Comput. Syst. Sci., 1979

On Languages Accepted by Space-Bounded Oracle Machines.
Acta Inf., 1979

Complexity Classes of Formal Languages (Preliminary Report).
Proceedings of the Mathematical Foundations of Computer Science 1979, 1979

Representing Complexity Classes by Equality Sets (Preliminary Report).
Proceedings of the Automata, 1979

1978
Celia Wrathall: On Languages Specified by Relative Acceptance.
Theor. Comput. Sci., 1978

Linear Languages and the Intersection Closures of Classes of Languages.
SIAM J. Comput., 1978

Simple Representations of Certain Classes of Languages.
J. ACM, 1978

The Independence of Certain Operations on semiAFLS.
ITA, 1978

On the Complexity of Formal Grammars.
Acta Inf., 1978

Comparisons and Reset Machines (Preliminary Report).
Proceedings of the Automata, 1978

1977
Inclusion Complete Tally Languages and the Hartmanis-Berman Conjecture.
Mathematical Systems Theory, 1977

On Languages With a Certain Prefix Property.
Mathematical Systems Theory, 1977

On the Computational Power of Reversal-Bounded Machines.
Proceedings of the Automata, 1977

Language Representation Theorems: How to Generate the R. E. Sets from the Regular Sets
Proceedings of the 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October, 1977

1976
Translational Lemmas, Polynomial Time, and (log n)^j-Space.
Theor. Comput. Sci., 1976

Inherently Nonplanar Automata.
Acta Inf., 1976

1975
Hauptvortrag: Formal language theory and theoretical computer science.
Proceedings of the Automata Theory and Formal Languages, 1975

1974
Tally Languages and Complexity Classes
Information and Control, October, 1974

Reversal-Bounded Acceptors and Intersections of Linear Languages.
SIAM J. Comput., 1974

Comparing Complexity Classes.
J. Comput. Syst. Sci., 1974

Reversal-Bounded Multipushdown Machines.
J. Comput. Syst. Sci., 1974

Mutually divisible semigroups.
Discrete Mathematics, 1974

Intersections of Linear Context-Free Languages and Reversal-Bounded Multipushdown Machines (Extended Abstract)
Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30, 1974

On the Structure of Complexity Classes.
Proceedings of the Automata, Languages and Programming, 2nd Colloquium, University of Saarbrücken, July 29, 1974

1973
On the structure of context-sensitive grammars.
International Journal of Parallel Programming, 1973

Free and almost-free subsemigroups of a free semigroup.
Discrete Mathematics, 1973

1972
On Languages Accepted in Polynomial Time.
SIAM J. Comput., 1972

Terminal Context in Context-Sensitive Grammars.
SIAM J. Comput., 1972

Multi-Stack-Counter Languages.
Mathematical Systems Theory, 1972

Complexity Classes of Formal Languages (Extended Abstract).
ICALP, 1972

Reversal-Bounded Multi-Pushdown Machines: Extended Abstract
Proceedings of the 13th Annual Symposium on Switching and Automata Theory, 1972

1971
A Note on AFLs and Bounding Erasing
Information and Control, August, 1971

Ambiguity in Graphs and Expressions.
IEEE Trans. Computers, 1971

Time-Bounded Grammars and Their Languages.
J. Comput. Syst. Sci., 1971

1970
Quasi-Realtime Languages.
Mathematical Systems Theory, 1970

Time- and Tape-Bounded Turing Acceptors and AFLs.
J. Comput. Syst. Sci., 1970

Tape-Bounded Turing Acceptors and Principal AFLs.
J. Comput. Syst. Sci., 1970

Tape- and Time-Bounded Turing Acceptors and AFLs: Extended Abstract
Proceedings of the 2nd Annual ACM Symposium on Theory of Computing, 1970

1969
Quasi-Realtime Languages-Extended Abstract
Proceedings of the 1st Annual ACM Symposium on Theory of Computing, 1969

1968
Grammars with Linear Time Functions
Proceedings of the 9th Annual Symposium on Switching and Automata Theory, 1968


  Loading...