Ronald V. Book

133 papers A* 17A 5B 7Journal 88Unranked 13
YearRankTypeTitle / Venue / Authors
1998 J jnl
Probabilistic Type-2 Operators and "Almost"-Classes.
Comput. Complex.
Ronald V. Book, Heribert Vollmer, Klaus W. Wagner
1996 J jnl
On Random Hard Sets for NP.
Inf. Comput.
Ronald V. Book, Osamu Watanabe
1996 A* conf
On Type-2 Probabilistic Quantifiers.
ICALP
Ronald V. Book, Heribert Vollmer, Klaus W. Wagner
1996 J jnl
On the Robustness of ALMOST-
RAIRO Theor. Informatics Appl.
Ronald V. Book, Elvira Mayordomo
1996 J jnl
Probabilistic Type-2 Operators and "Almost"-Classes
Electron. Colloquium Comput. Complex.
Ronald V. Book, Heribert Vollmer, Klaus W. Wagner
1995 J jnl
The Global Power of Additional Queries to Random Oracles
Inf. Comput.
Ronald V. Book, Jack H. Lutz, David M. Martin Jr.
1994 J jnl
An Observation on Probability Versus Randomness with Applications to Complexity Classes.
Math. Syst. Theory
Ronald V. Book, Jack H. Lutz, Klaus W. Wagner
1994 J jnl
On Collapsing the Polynomial-Time Hierarchy.
Inf. Process. Lett.
Ronald V. Book
1994 J jnl
On Languages Reducible to Algorithmically Random Languages.
SIAM J. Comput.
Ronald V. Book
1994 B conf
On Random Hard Sets for NP.
ISAAC
Ronald V. Book, Osamu Watanabe
1994 J jnl
Relativizations of the P =? NP and Other Problems: Developments in Structural Complexity Theory.
SIAM Rev.
Ronald V. Book
1994 A conf
The Global Power of Additional Queries to Random Oracles.
STACS
Ronald V. Book, Jack H. Lutz, David M. Martin Jr.
1993 — ch.
A View of Structural Complexity Theory.
Current Trends in Theoretical Computer Science
Ronald V. Book, Osamu Watanabe
1993 J jnl
On Languages With Very High Space-Bounded Kolmogorov Complexity.
SIAM J. Comput.
Ronald V. Book, Jack H. Lutz
1993 B conf
Relativizing Complexity Classes With Random Oracles.
ISAAC
Ronald V. Book
1993 — book
String-Rewriting Systems.
Ronald V. Book, Friedrich Otto
1992 — conf
Additional Queries and Algorithmically Random Languages.
Complexity Theory: Current Research
Ronald V. Book
1992 A conf
On Complexity Classes and Algorithmically Random Languages (Extended Abstract).
STACS
Ronald V. Book, Jack H. Lutz, Klaus W. Wagner
1992 — conf
On Languages with Very High Information Content.
SCT
Ronald V. Book, Jack H. Lutz
1992 B conf
Relativizations of the
ISAAC
Ronald V. Book
1991 J jnl
On "Inherently Context-Sensitive" Languages - An Application of Complexity Cores.
Inf. Process. Lett.
Volker Diekert, Ronald V. Book
1991 J jnl
On Random Oracle Separations.
Inf. Process. Lett.
Ronald V. Book
1991 J jnl
Polynomial-Time Reducibilities and "Almost All" Oracle Sets.
Theor. Comput. Sci.
Shouwen Tang, Ronald V. Book
1991 J jnl
Reducibilities on tally and sparse sets.
RAIRO Theor. Informatics Appl.
Shouwen Tang, Ronald V. Book
1991 — ed.
Rewriting Techniques and Applications, 4th International Conference, RTA-91, Como, Italy, April 10-12, 1991, Proceedings
RTA
Ronald V. Book
1991 J jnl
Some Observations on Separating Complexity Classes.
SIAM J. Comput.
Ronald V. Book
1990 — conf
A Note on Confluent Thue Systems.
IWWERT
Ronald V. Book
1990 A* conf
Additional Queries to Random and Pseudorandom Oracles.
ICALP
Ronald V. Book, Jack H. Lutz, Shouwen Tang
1990 J jnl
Characterizing Polynomial Complexity Classes by Reducibilities.
Math. Syst. Theory
Ronald V. Book, Shouwen Tang
1990 — conf
On Separating Complexity Classes.
SCT
Ronald V. Book
1989 J jnl
A Note on Sparse Sets and the Polynomial-Time Hierarchy.
Inf. Process. Lett.
Ronald V. Book, Shouwen Tang
1989 J jnl
A view of structural complexity theory.
Bull. EATCS
Ronald V. Book, Osamu Watanabe
1989 J jnl
On Inefficient Special Cases of NP-Complete Problems.
Theor. Comput. Sci.
Ding-Zhu Du, Ronald V. Book
1988 J jnl
Lowness Properties of Sets in the Exponential-Time Hierarchy.
SIAM J. Comput.
Ronald V. Book, Pekka Orponen, David A. Russo, Osamu Watanabe
1988 J jnl
On Sets Truth-Table Reducible to Sparse Sets.
SIAM J. Comput.
Ronald V. Book, Ker-I Ko
1988 — conf
On polynomial and generalized complexity cores.
SCT
Ronald V. Book, Ding-Zhu Du, David A. Russo
1988 A* conf
Separating Polynomial-Time Turing and Truth-Table Reductions by Tally Sets.
ICALP
Shouwen Tang, Ronald V. Book
1988 B conf
Sparse Sets, Tally Sets, and Polynomial Reducibilities.
MFCS
Ronald V. Book
1988 J jnl
The Structure of Generalized Complexity Cores.
Theor. Comput. Sci.
Ronald V. Book, Ding-Zhu Du
1987 — conf
On sets reducible to sparse sets.
SCT
Ronald V. Book, Ker-I Ko
1987 J jnl
Rewriting Systems and Word Problems in a Free Partially Commutative Monoid.
Inf. Process. Lett.
Ronald V. Book, Hai-Ning Liu
1987 J jnl
The existence and density of generalized complexity cores.
J. ACM
Ronald V. Book, Ding-Zhu Du
1987 J jnl
Thue Systems as Rewriting Systems.
J. Symb. Comput.
Ronald V. Book
1987 A conf
Towards a Theory of Relativizations: Positive Relativizations.
STACS
Ronald V. Book
1986 A* conf
On Exponential Lowness.
ICALP
Ronald V. Book, Pekka Orponen, David A. Russo, Osamu Watanabe
1986 A conf
On Generalized Kolmogorov Complexity.
STACS
José L. Balcázar, Ronald V. Book
1986 J jnl
On Unification: Equational Theories Are Not Bounded.
J. Symb. Comput.
Ronald V. Book, Jörg H. Siekmann
1986 J jnl
Sets with Small Generalized Kolmogorov Complexity.
Acta Informatica
José L. Balcázar, Ronald V. Book
1986 J jnl
Sparse Sets, Lowness and Highness.
SIAM J. Comput.
José L. Balcázar, Ronald V. Book, Uwe Schöning
1986 J jnl
The polynomial-time hierarchy and sparse oracles.
J. ACM
José L. Balcázar, Ronald V. Book, Uwe Schöning
1985 J jnl
Cancellation Rules and Extended Word Problems.
Inf. Process. Lett.
Ronald V. Book, Friedrich Otto
1985 J jnl
On Bounded Query Machines.
Theor. Comput. Sci.
José L. Balcázar, Ronald V. Book, Uwe Schöning
1985 J jnl
On the Security of Name-Stamp Protocols.
Theor. Comput. Sci.
Ronald V. Book, Friedrich Otto
1985 — conf
On the Unification Hierarchy.
GWAI
Ronald V. Book, Jörg H. Siekmann
1985 J jnl
On the Verifiability of Two-Party Algebraic Protocols.
Theor. Comput. Sci.
Ronald V. Book, Friedrich Otto
1985 J jnl
Qualitative Relativizations of Complexity Classes.
J. Comput. Syst. Sci.
Ronald V. Book, Timothy J. Long, Alan L. Selman
1985 J jnl
Reductions in Tree Replacement Systems.
Theor. Comput. Sci.
Jean H. Gallier, Ronald V. Book
1985 A* conf
The Verifiability of Two-Party Protocols.
EUROCRYPT
Ronald V. Book, Friedrich Otto
1985 J jnl
The base of the intersection of two free submonoids.
Discret. Appl. Math.
Ronald V. Book
1985 — conf
Thue Systems as Rewriting Systems.
RTA
Ronald V. Book
1984 J jnl
Almost all one-rule thue systems have decidable word problems.
Discret. Math.
Ronald V. Book, Craig C. Squier
1984 J jnl
Characterizations of Reduction Classes Modulo Oracle Conditions.
Math. Syst. Theory
Ronald V. Book, Alan L. Selman
1984 J jnl
Homogeneous Thue systems and the Church-Rosser property.
Discret. Math.
Ronald V. Book
1984 J jnl
Immunity, Relativizations, and Nondeterminism.
SIAM J. Comput.
Uwe Schöning, Ronald V. Book
1984 J jnl
On Expressing Commutativity by Finite Church-Rosser Presentations: A Note on Commutative Monoids.
RAIRO Theor. Informatics Appl.
Jürgen Avenhaus, Ronald V. Book, Craig C. Squier
1984 J jnl
Quantitative Relativizations of Complexity Classes.
SIAM J. Comput.
Ronald V. Book, Timothy J. Long, Alan L. Selman
1984 J jnl
Relativizations of complexity classes.
SIGACT News
Ronald V. Book
1984 J jnl
Relativizations of complexity classes.
SIGACT News
Ronald V. Book
1984 A* conf
Sparse Oracles and Uniform Complexity Classes
FOCS
José L. Balcázar, Ronald V. Book, Timothy J. Long, Uwe Schöning, Alan L. Selman
1984 B conf
Sparse Oracles, Lowness, and Highness.
MFCS
José L. Balcázar, Ronald V. Book, Uwe Schöning
1983 J jnl
A Note on Special Thue Systems with a Single Defining Relation.
Math. Syst. Theory
Ronald V. Book
1983 — conf
Controlled relativizations of P and NP.
Theoretical Computer Science
Ronald V. Book, Timothy J. Long, Alan L. Selman
1983 J jnl
Decidable Sentences of Church-Rosser Congruences.
Theor. Comput. Sci.
Ronald V. Book
1983 A* conf
Immunity (Extended Abstract).
ICALP
Uwe Schöning, Ronald V. Book
1983 J jnl
Positive Relativizations of Complexity Classes.
SIAM J. Comput.
Alan L. Selman, Xu Mei-Rui, Ronald V. Book
1983 J jnl
Refining Nondeterminism in Relativizations of Complexity Classes
J. ACM
Xu Mei-Rui, John E. Donner, Ronald V. Book
1982 J jnl
A Note on Complete Sets and Transitive Closure.
Math. Syst. Theory
Ronald V. Book, Celia Wrathall
1982 J jnl
Confluent and Other Types of Thue Systems.
J. ACM
Ronald V. Book
1982 J jnl
Monadic Thue Systems.
Theor. Comput. Sci.
Ronald V. Book, Matthias Jantzen, Celia Wrathall
1982 J jnl
Relativizing Time, Space, and Time-Space.
SIAM J. Comput.
Ronald V. Book, Christopher B. Wilson, Xu Mei-Rui
1982 A conf
The Power of the Church-Rosser Property for String Rewriting Systems.
CADE
Ronald V. Book
1982 J jnl
When is a Monoid a Group? The Church-Rosser Case is Tractable.
Theor. Comput. Sci.
Ronald V. Book
1981 — conf
(Erasing)* Strings.
Theoretical Computer Science
Ronald V. Book, Matthias Jantzen, Celia Wrathall
1981 J jnl
Bounded Query Machines: On NP and PSPACE.
Theor. Comput. Sci.
Ronald V. Book
1981 J jnl
Bounded Query Machines: On NP( ) and NPQERY( ).
Theor. Comput. Sci.
Ronald V. Book, Celia Wrathall
1981 J jnl
NTS Grammars and Church-Rosser Systems.
Inf. Process. Lett.
Ronald V. Book
1981 B conf
On the Complexity of Word Problems in Certain Thue Systems (Preliminary Report).
MFCS
Ronald V. Book, Matthias Jantzen, Burkhard Monien, Colm Ó'Dúnlaing, Celia Wrathall
1981 A* conf
Relativizing Time and Space (Preliminary Report)
FOCS
Ronald V. Book, Christopher B. Wilson, Mei-rui Xu
1981 J jnl
Testing for the Church-Rosser Property.
Theor. Comput. Sci.
Ronald V. Book, Colm Ó'Dúnlaing
1981 J jnl
The Undecidability of a Word Problem: On a Conjecture of Strong, Maggiolo-Schettini and Rosen.
Inf. Process. Lett.
Ronald V. Book
1980 J jnl
Equality Sets and Complexity Classes.
SIAM J. Comput.
Ronald V. Book, Franz-Josef Brandenburg
1980 J jnl
On Uniquely Decipherable Codes with Two Codewords.
IEEE Trans. Computers
Ronald V. Book, Sai Choi Kwan
1979 J jnl
A Remark on Tally Languages and Complexity Classes
Inf. Control.
Ronald V. Book
1979 B conf
Complexity Classes of Formal Languages (Preliminary Report).
MFCS
Ronald V. Book
1979 J jnl
On Languages Accepted by Space-Bounded Oracle Machines.
Acta Informatica
Ronald V. Book
1979 J jnl
Polynomial Space and Transitive Closure.
SIAM J. Comput.
Ronald V. Book
1979 A* conf
Representing Complexity Classes by Equality Sets (Preliminary Report).
ICALP
Ronald V. Book, Franz-Josef Brandenburg
1979 J jnl
Reset Machines.
J. Comput. Syst. Sci.
Ronald V. Book, Sheila A. Greibach, Celia Wrathall
1978 J jnl
Celia Wrathall: On Languages Specified by Relative Acceptance.
Theor. Comput. Sci.
Ronald V. Book
1978 A* conf
Comparisons and Reset Machines (Preliminary Report).
ICALP
Ronald V. Book, Sheila A. Greibach, Celia Wrathall
1978 J jnl
Linear Languages and the Intersection Closures of Classes of Languages.
SIAM J. Comput.
Ronald V. Book, Maurice Nivat
1978 J jnl
On the Complexity of Formal Grammars.
Acta Informatica
Ronald V. Book
1978 J jnl
Simple Representations of Certain Classes of Languages.
J. ACM
Ronald V. Book
1978 J jnl
The Independence of Certain Operations on semiAFLS.
RAIRO Theor. Informatics Appl.
Ronald V. Book, Sheila A. Greibach
1977 J jnl
Inclusion Complete Tally Languages and the Hartmanis-Berman Conjecture.
Math. Syst. Theory
Ronald V. Book, Celia Wrathall, Alan L. Selman, David P. Dobkin
1977 A* conf
Language Representation Theorems: How to Generate the R. E. Sets from the Regular Sets
FOCS
Ronald V. Book
1977 J jnl
On Languages With a Certain Prefix Property.
Math. Syst. Theory
Ronald V. Book
1977 A* conf
On the Computational Power of Reversal-Bounded Machines.
ICALP
Ronald V. Book, Chee-Keng Yap
1976 J jnl
Inherently Nonplanar Automata.
Acta Informatica
Ronald V. Book, Ashok K. Chandra
1976 J jnl
Translational Lemmas, Polynomial Time, and (log n)^j-Space.
Theor. Comput. Sci.
Ronald V. Book
1975 — conf
Hauptvortrag: Formal language theory and theoretical computer science.
Automata Theory and Formal Languages
Ronald V. Book
1974 J jnl
Comparing Complexity Classes.
J. Comput. Syst. Sci.
Ronald V. Book
1974 A* conf
Intersections of Linear Context-Free Languages and Reversal-Bounded Multipushdown Machines (Extended Abstract)
STOC
Ronald V. Book, Maurice Nivat, Mike Paterson
1974 J jnl
Mutually divisible semigroups.
Discret. Math.
Ronald V. Book, Michael A. Harrison
1974 A* conf
On the Structure of Complexity Classes.
ICALP
Ronald V. Book
1974 J jnl
Reversal-Bounded Acceptors and Intersections of Linear Languages.
SIAM J. Comput.
Ronald V. Book, Maurice Nivat, Mike Paterson
1974 J jnl
Reversal-Bounded Multipushdown Machines.
J. Comput. Syst. Sci.
Brenda S. Baker, Ronald V. Book
1974 J jnl
Tally Languages and Complexity Classes
Inf. Control.
Ronald V. Book
1973 J jnl
Free and almost-free subsemigroups of a free semigroup.
Discret. Math.
Ronald V. Book
1973 J jnl
On the structure of context-sensitive grammars.
Int. J. Parallel Program.
Ronald V. Book
1972 A* conf
Complexity Classes of Formal Languages (Extended Abstract).
ICALP
Ronald V. Book
1972 J jnl
Multi-Stack-Counter Languages.
Math. Syst. Theory
Ronald V. Book, Seymour Ginsburg
1972 J jnl
On Languages Accepted in Polynomial Time.
SIAM J. Comput.
Ronald V. Book
1972 — conf
Reversal-Bounded Multi-Pushdown Machines: Extended Abstract
SWAT
Brenda S. Baker, Ronald V. Book
1972 J jnl
Terminal Context in Context-Sensitive Grammars.
SIAM J. Comput.
Ronald V. Book
1971 J jnl
A Note on AFLs and Bounding Erasing
Inf. Control.
Ronald V. Book, Ben Wegbreit
1971 J jnl
Time-Bounded Grammars and Their Languages.
J. Comput. Syst. Sci.
Ronald V. Book
1970 J jnl
Quasi-Realtime Languages.
Math. Syst. Theory
Ronald V. Book, Sheila A. Greibach
1970 A* conf
Tape- and Time-Bounded Turing Acceptors and AFLs: Extended Abstract
STOC
Ronald V. Book, Sheila A. Greibach, Ben Wegbreit
1970 J jnl
Tape-Bounded Turing Acceptors and Principal AFLs.
J. Comput. Syst. Sci.
Ronald V. Book, Sheila A. Greibach, Oscar H. Ibarra, Ben Wegbreit
1970 J jnl
Time- and Tape-Bounded Turing Acceptors and AFLs.
J. Comput. Syst. Sci.
Ronald V. Book, Sheila A. Greibach, Ben Wegbreit
1969 A* conf
Quasi-Realtime Languages-Extended Abstract
STOC
Ronald V. Book, Sheila A. Greibach
1968 — conf
Grammars with Linear Time Functions
SWAT
Ronald V. Book