Ronald V. Book

Ronald V. Book's AcademicInfluence.com Rankings

Ronald V. Book

Computer Science

#10106

World Rank

#10600

Historical Rank

Database

#7063

World Rank

#7307

Historical Rank

computer-science Degrees

Download Badge

Computer Science

Ronald V. Book's Degrees

PhD Computer Science University of California, Berkeley
Masters Computer Science University of California, Berkeley
Bachelors Mathematics University of California, Berkeley

Similar Degrees You Can Earn

Why Is Ronald V. Book Influential?

(Suggest an Edit or Addition)

(See a Problem?)

Ronald V. Book's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

String-Rewriting Systems (1993) (575)
Reversal-Bounded Multipushdown Machines (1974) (207)
Review: Michael R. Garey and David S. Johnson, Computers and intractability: A guide to the theory of $NP$-completeness (1980) (168)
Confluent and Other Types of Thue Systems (1982) (168)
Quantitative Relativizations of Complexity Classes (1984) (144)
Formal language theory : perspectives and open problems (1980) (144)
Tally Languages and Complexity Classes (1974) (133)
Currents In The Theory Of Computing (1973) (109)
Thue Systems as Rewriting Systems (1985) (109)
Monadic Thue Systems (1982) (105)
Ambiguity in Graphs and Expressions (1971) (94)
The polynomial-time hierarchy and sparse oracles (1986) (78)
Sparse Sets, Lowness and Highness (1986) (71)
On Sets Truth-Table Reducible to Sparse Sets (1988) (71)
Time- and Tape-Bounded Turing Acceptors and AFLs (1970) (69)
On Languages Accepted in Polynomial Time (1972) (58)
Decidable Sentences of Church-Rosser Congruences (1983) (55)
Reductions in Tree Replacement Systems (1985) (55)
Comparing Complexity Classes (1974) (50)
Algol-like Languages (1997) (47)
Qualitative Relativizations of Complexity Classes (1985) (45)
Quasi-realtime languages (1970) (44)
Reversal-Bounded Acceptors and Intersections of Linear Languages (1974) (42)
Positive Relativizations of Complexity Classes (1983) (41)
Time-Bounded Grammars and Their Languages (1971) (41)
Immunity, Relativizations, and Nondeterminism (1984) (41)
Testing for the Church-Rosser Property (1981) (38)
Bounded Query Machines: On NP and PSPACE (1981) (37)
Bounded Query Machines: On NP( ) and NPQERY( ) (1981) (35)
Rewriting Techniques and Applications (1991) (34)
Translational Lemmas, Polynomial Time, and (log n)^j-Space (1976) (33)
On Complexity Classes and Algorithmically Random Languages (Extended Abstract) (1992) (33)
The existence and density of generalized complexity cores (1987) (33)
Simple Representations of Certain Classes of Languages (1978) (32)
On Type-2 Probabilistic Quantifiers (1996) (32)
What is Structural Complexity Theory (1989) (30)
On Random Oracle Separations (1991) (27)
Terminal Context in Context-Sensitive Grammars (1972) (25)
On polynomial and generalized complexity cores (1988) (24)
THUE SYSTEMS AND THE CHURCH-ROSSER PROPERTY: REPLACEMENT SYSTEMS, SPECIFICATION OF FORMAL LANGUAGES, AND PRESENTATIONS OF MONOIDS† (1983) (24)
Polynomial-Time Reducibilities and "Almost All" Oracle Sets (1991) (24)
Relativizing Time, Space, and Time-Space (1982) (23)
Rewriting Systems and Word Problems in a Free Partially Commutative Monoid (1987) (20)
On Languages Reducible to Algorithmically Random Languages (1994) (20)
Linear Languages and the Intersection Closures of Classes of Languages (1978) (19)
Cancellation Rules and Extended Word Problems (1985) (18)
When is a Monoid a Group? The Church-Rosser Case is Tractable (1982) (18)
Reversal-Bounded Multi-Pushdown Machines: Extended Abstract (1972) (17)
Homogeneous Thue systems and the Church-Rosser property (1984) (17)
Lowness Properties of Sets in the Exponential-Time Hierarchy (1988) (17)
Equality Sets and Complexity Classes (1980) (17)
Tape-Bounded Turing Acceptors and Principal AFLs (1970) (16)
Sets with small generalized Kolmogorov complexity (1986) (16)
Thue congruences and the Church-Rosser property (1981) (15)
On Collapsing the Polynomial-Time Hierarchy (1994) (14)
On the Complexity of Word Problems in Certain Thue Systems (Preliminary Report) (1981) (14)
On Bounded Query Machines (1985) (13)
On Generalized Kolmogorov Complexity (1986) (12)
On Expressing Commutativity by Finite Church-Rosser Presentations: A Note on Commutative Monoids (1984) (12)
On Inefficient Special Cases of NP-Complete Problems (1989) (12)
On Languages With Very High Space-Bounded Kolmogorov Complexity (1993) (11)
The Global Power of Additional Queries to Random Oracles (1994) (11)
On sets reducible to sparse sets (1987) (11)
Sparse Oracles and Uniform Complexity Classes (1984) (11)
The Power of the Church-Rosser Property for String Rewriting Systems (1982) (11)
Reset Machines (1979) (11)
Reducibilities on tally and sparse sets (1991) (11)
Separating Polynomial-Time Turing and Truth-Table Reductions by Tally Sets (1988) (10)
An observation on probability versus randomness with applications to complexity classes (1994) (9)
On the structure of context-sensitive grammars (1973) (9)
Inherently nonplanar automata (1976) (9)
Celia Wrathall: On Languages Specified by Relative Acceptance (1978) (9)
Polynomial Space and Transitive Closure (1979) (9)
Towards a Theory of Relativizations: Positive Relativizations (1987) (8)
Some Observations on Separating Complexity Classes (1991) (8)
On Unification: Equational Theories Are Not Bounded (1986) (8)
Studies in complexity theory (1986) (8)
Almost all one-rule thue systems have decidable word problems (1984) (7)
Sparse Oracles, Lowness, and Highness (1984) (7)
A Note on AFLs and Bounding Erasing (1971) (7)
Refining Nondeterminism in Relativizations of Complexity Classes (1983) (7)
On Sets with Small Information Content (1992) (7)
NTS Grammars and Church-Rosser Systems (1981) (6)
The Verifiability of Two-Party Protocols (1985) (6)
A Note on Sparse Sets and the Polynomial-Time Hierarchy (1989) (6)
Comparisons and Reset Machines (Preliminary Report) (1978) (6)
The Independence of Certain Operations on semiAFLS (1978) (6)
On the Security of Name-Stamp Protocols (1985) (6)
On the Verifiability of Two-Party Algebraic Protocols (1985) (6)
Probabilistic Type-2 Operators and “Almost”-Classes (1998) (5)
Dehn's algorithm and the complexity of word problems (1988) (5)
Relativizations of the P =? NP and Other Problems: Developments in Structural Complexity Theory (1994) (5)
The Structure of Generalized Complexity Cores (1988) (5)
Reversal-bounded multipushdown machines. [Turing acceptors for context free languages] (1974) (5)
Intersections of linear context-free languages and reversal-bounded multipushdown machines (Extended Abstract) (1974) (5)
A note on special thue systems with a single defining relation (1983) (5)
On languages with very high information content (1992) (5)
Comparative Metric Semantics of Programming (1997) (5)
On languages with a certain prefix property (1976) (5)
Inclusion complete tally languages and the Hartmanis-Berman conjecture (1977) (5)
On separating complexity classes (1990) (5)
On the Robustness of ALMOST-R (1996) (4)
On the Unification Hierarchy (1985) (4)
Representing Complexity Classes by Equality Sets (Preliminary Report) (1979) (4)
Sparse Sets, Tally Sets, and Polynomial Reducibilities (1988) (4)
On Random Hard Sets for NP (1994) (4)
Multi-stack-counter languages (1972) (4)
On Uniquely Decipherable Codes with Two Codewords (1980) (4)
Relativizing time and space (1981) (3)
Controlled relativizations of P and NP (1983) (3)
The base of the intersection of two free submonoids (1985) (3)
The Undecidability of a Word Problem: On a Conjecture of Strong, Maggiolo-Schettini and Rosen (1981) (3)
(Erasing)* Strings (1981) (3)
Grammars with Linear Time Functions (1968) (3)
On the Structure of Complexity Classes (1974) (3)
Complexity Classes of Formal Languages (Preliminary Report) (1979) (2)
On Exponential Lowness (1986) (2)
Additional Queries to Random and Pseudorandom Oracles (1990) (2)
Monadic String-Rewriting Systems (1993) (2)
Hauptvortrag: Formal language theory and theoretical computer science (1975) (2)
Tape- and time-bounded Turing acceptors and AFLs (Extended Abstract) (1970) (2)
A view of structural complexity theory (1989) (2)
Free and almost-free subsemigroups of a free semigroup (1973) (2)
On the Computational Power of Reversal-Bounded Machines (1977) (2)
Quasi-realtime languages (Extended Abstract) (1969) (2)
Additional Queries and Algorithmically Random Languages (1993) (1)
Relativizations of complexity classes (1984) (1)
Relativizations of the P =?NP and other Problems: Some Developments in Structural Complexity Theory (1992) (1)
Review: Richard M. Karp, Raymond E. Miller, James W. Thatcher, Reducibility Among Combinatorial Problems (1975) (1)
Comparing complexity classes of formal languages (1972) (1)
On languages accepted by space-bounded oracle machines (1979) (1)
Language representation theorems: How to generate the R. E. sets from the regular sets (1977) (1)
Rewriting techniques and applications : 4th International Conference, RTA-91, Como, Italy, April 10-12, 1991, proceedings (1991) (1)
Foreword [to Special Issue] (1981) (1)
A Note on Confluent Thue Systems (1990) (1)
Relativizing Complexity Classes With Random Oracles (1993) (0)
Descriptional Complexity (Dagstuhl Seminar 9318) (2021) (0)
Complexity Classes of Formal Languages (Extended Abstract) (1972) (0)
A Remark on Tally Languages and Complexity Classes (1979) (0)
A NOTE ON LANGUAGES ACCEPTED BY TIME-BOUNDED NONDETERMINISTIC MACHINES. (1969) (0)
Proceedings of the 4th international conference on Rewriting techniques and applications (1991) (0)
Characterizations of reduction classes modulo oracle conditions (1984) (0)
Characterizing polynomial complexity classes by reducibilities (1990) (0)
Mutually divisible semigroups (1974) (0)
Immunity (Extended Abstract) (1983) (0)
Length as the Basis for Reduction (1993) (0)
On "Inherently Context-Sensitive" Languages - An Application of Complexity Cores (1991) (0)
A note on complete sets and transitive closure (1981) (0)
Length-Reducing Non-Monadic String-Rewriting Systems (1993) (0)
Relativizations of complexity classes (1984) (0)
Relativizing Time and Space (Preliminary Report) (1981) (0)
ON SEPARATING COMPLEXITY CLASSES* (Extended Abstract) (1990) (0)
On the complexity of formal grammars (1978) (0)
Algebraic and Automata-Theoretic Properties of Formal Languages (Seymour Ginsburg) (1979) (0)
The complexity of matrix transposition on one-tape off-line Turing machines with output tape * (2001) (0)

This paper list is powered by the following services:

What Schools Are Affiliated With Ronald V. Book?

Ronald V. Book is affiliated with the following schools:

University of California, Santa Barbara

Ronald V. Book's Academic­Influence.com Rankings