default search action
Ronald V. Book
Ronald Vernon Book
Person information
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
Books and Theses
- 1993
- [b1]Ronald V. Book, Friedrich Otto:
String-Rewriting Systems. Texts and Monographs in Computer Science, Springer 1993, ISBN 978-3-540-97965-4, pp. I-VIII, 1-189
Journal Articles
- 1998
- [j88]Ronald V. Book, Heribert Vollmer
, Klaus W. Wagner:
Probabilistic Type-2 Operators and "Almost"-Classes. Comput. Complex. 7(3): 265-289 (1998) - 1996
- [j87]Ronald V. Book, Osamu Watanabe:
On Random Hard Sets for NP. Inf. Comput. 125(1): 70-76 (1996) - [j86]Ronald V. Book, Elvira Mayordomo
On the Robustness of ALMOST-R. RAIRO Theor. Informatics Appl. 30(2): 123-133 (1996) - 1995
- [j85]Ronald V. Book, Jack H. Lutz, David M. Martin Jr.:
The Global Power of Additional Queries to Random Oracles. Inf. Comput. 120(1): 49-54 (1995) - 1994
- [j84]Ronald V. Book:
On Collapsing the Polynomial-Time Hierarchy. Inf. Process. Lett. 52(5): 235-237 (1994) - [j83]Ronald V. Book, Jack H. Lutz, Klaus W. Wagner:
An Observation on Probability Versus Randomness with Applications to Complexity Classes. Math. Syst. Theory 27(3): 201-209 (1994) - [j82]Ronald V. Book:
On Languages Reducible to Algorithmically Random Languages. SIAM J. Comput. 23(6): 1275-1282 (1994) - [j81]Ronald V. Book:
Relativizations of the P =? NP and Other Problems: Developments in Structural Complexity Theory. SIAM Rev. 36(2): 157-175 (1994) - 1993
- [j80]Ronald V. Book, Jack H. Lutz:
On Languages With Very High Space-Bounded Kolmogorov Complexity. SIAM J. Comput. 22(2): 395-402 (1993) - 1991
- [j79]Ronald V. Book:
On Random Oracle Separations. Inf. Process. Lett. 39(1): 7-10 (1991) - [j78]Volker Diekert, Ronald V. Book:
On "Inherently Context-Sensitive" Languages - An Application of Complexity Cores. Inf. Process. Lett. 40(1): 21-23 (1991) - [j77]Shouwen Tang, Ronald V. Book:
Reducibilities on tally and sparse sets. RAIRO Theor. Informatics Appl. 25: 293-302 (1991) - [j76]Ronald V. Book:
Some Observations on Separating Complexity Classes. SIAM J. Comput. 20(2): 246-258 (1991) - [j75]Shouwen Tang, Ronald V. Book:
Polynomial-Time Reducibilities and "Almost All" Oracle Sets. Theor. Comput. Sci. 81(1): 35-47 (1991) - 1990
- [j74]Ronald V. Book, Shouwen Tang:
Characterizing Polynomial Complexity Classes by Reducibilities. Math. Syst. Theory 23(3): 165-174 (1990) - 1989
- [j73]Ronald V. Book, Osamu Watanabe:
A view of structural complexity theory. Bull. EATCS 39: 122-138 (1989) - [j72]Ronald V. Book, Shouwen Tang:
A Note on Sparse Sets and the Polynomial-Time Hierarchy. Inf. Process. Lett. 33(3): 141-143 (1989) - [j71]Ding-Zhu Du, Ronald V. Book:
On Inefficient Special Cases of NP-Complete Problems. Theor. Comput. Sci. 63(3): 239-252 (1989) - 1988
- [j70]Ronald V. Book, Pekka Orponen
Lowness Properties of Sets in the Exponential-Time Hierarchy. SIAM J. Comput. 17(3): 504-516 (1988) - [j69]Ronald V. Book, Ker-I Ko:
On Sets Truth-Table Reducible to Sparse Sets. SIAM J. Comput. 17(5): 903-919 (1988) - [j68]Ronald V. Book, Ding-Zhu Du:
The Structure of Generalized Complexity Cores. Theor. Comput. Sci. 61: 103-119 (1988) - 1987
- [j67]Ronald V. Book, Hai-Ning Liu:
Rewriting Systems and Word Problems in a Free Partially Commutative Monoid. Inf. Process. Lett. 26(1): 29-32 (1987) - [j66]Ronald V. Book, Ding-Zhu Du:
The existence and density of generalized complexity cores. J. ACM 34(3): 718-730 (1987) - [j65]Ronald V. Book:
Thue Systems as Rewriting Systems. J. Symb. Comput. 3(1/2): 39-68 (1987) - 1986
- [j64]José L. Balcázar, Ronald V. Book:
Sets with Small Generalized Kolmogorov Complexity. Acta Informatica 23(6): 679-688 (1986) - [j63]José L. Balcázar, Ronald V. Book, Uwe Schöning:
The polynomial-time hierarchy and sparse oracles. J. ACM 33(3): 603-617 (1986) - [j62]Ronald V. Book, Jörg H. Siekmann:
On Unification: Equational Theories Are Not Bounded. J. Symb. Comput. 2(4): 317-324 (1986) - [j61]José L. Balcázar, Ronald V. Book, Uwe Schöning:
Sparse Sets, Lowness and Highness. SIAM J. Comput. 15(3): 739-747 (1986) - 1985
- [j60]Ronald V. Book:
The base of the intersection of two free submonoids. Discret. Appl. Math. 12(1): 13-20 (1985) - [j59]Ronald V. Book, Friedrich Otto:
Cancellation Rules and Extended Word Problems. Inf. Process. Lett. 20(1): 5-11 (1985) - [j58]Ronald V. Book, Timothy J. Long, Alan L. Selman:
Qualitative Relativizations of Complexity Classes. J. Comput. Syst. Sci. 30(3): 395-413 (1985) - [j57]Jean H. Gallier, Ronald V. Book:
Reductions in Tree Replacement Systems. Theor. Comput. Sci. 37: 123-150 (1985) - [j56]Ronald V. Book, Friedrich Otto:
On the Security of Name-Stamp Protocols. Theor. Comput. Sci. 39: 319-325 (1985) - [j55]Ronald V. Book, Friedrich Otto:
On the Verifiability of Two-Party Algebraic Protocols. Theor. Comput. Sci. 40: 101-130 (1985) - [j54]José L. Balcázar, Ronald V. Book, Uwe Schöning:
On Bounded Query Machines. Theor. Comput. Sci. 40: 237-243 (1985) - 1984
- [j53]Ronald V. Book:
Homogeneous Thue systems and the Church-Rosser property. Discret. Math. 48(2-3): 137-145 (1984) - [j52]Ronald V. Book, Craig C. Squier:
Almost all one-rule thue systems have decidable word problems. Discret. Math. 49(3): 237-240 (1984) - [j51]Jürgen Avenhaus, Ronald V. Book, Craig C. Squier:
On Expressing Commutativity by Finite Church-Rosser Presentations: A Note on Commutative Monoids. RAIRO Theor. Informatics Appl. 18(1): 47-52 (1984) - [j50]Ronald V. Book, Alan L. Selman:
Characterizations of Reduction Classes Modulo Oracle Conditions. Math. Syst. Theory 17(4): 263-277 (1984) - [j49]Uwe Schöning, Ronald V. Book:
Immunity, Relativizations, and Nondeterminism. SIAM J. Comput. 13(2): 329-337 (1984) - [j48]Ronald V. Book, Timothy J. Long, Alan L. Selman:
Quantitative Relativizations of Complexity Classes. SIAM J. Comput. 13(3): 461-487 (1984) - [j47]Ronald V. Book:
Relativizations of complexity classes. SIGACT News 15(4): 61 (1984) - [j46]Ronald V. Book:
Relativizations of complexity classes. SIGACT News 16(1): 61 (1984) - 1983
- [j45]Xu Mei-Rui, John E. Donner, Ronald V. Book:
Refining Nondeterminism in Relativizations of Complexity Classes. J. ACM 30(3): 677-685 (1983) - [j44]Ronald V. Book:
A Note on Special Thue Systems with a Single Defining Relation. Math. Syst. Theory 16(1): 57-60 (1983) - [j43]Alan L. Selman, Xu Mei-Rui, Ronald V. Book:
Positive Relativizations of Complexity Classes. SIAM J. Comput. 12(3): 565-579 (1983) - [j42]Ronald V. Book:
Decidable Sentences of Church-Rosser Congruences. Theor. Comput. Sci. 24: 301-312 (1983) - 1982
- [j41]Ronald V. Book:
Confluent and Other Types of Thue Systems. J. ACM 29(1): 171-182 (1982) - [j40]Ronald V. Book, Celia Wrathall:
A Note on Complete Sets and Transitive Closure. Math. Syst. Theory 15(4): 311-313 (1982) - [j39]Ronald V. Book, Christopher B. Wilson, Xu Mei-Rui:
Relativizing Time, Space, and Time-Space. SIAM J. Comput. 11(3): 571-581 (1982) - [j38]Ronald V. Book:
When is a Monoid a Group? The Church-Rosser Case is Tractable. Theor. Comput. Sci. 18: 325-331 (1982) - [j37]Ronald V. Book, Matthias Jantzen, Celia Wrathall:
Monadic Thue Systems. Theor. Comput. Sci. 19: 231-251 (1982) - 1981
- [j36]Ronald V. Book:
The Undecidability of a Word Problem: On a Conjecture of Strong, Maggiolo-Schettini and Rosen. Inf. Process. Lett. 12(3): 121-122 (1981) - [j35]Ronald V. Book:
NTS Grammars and Church-Rosser Systems. Inf. Process. Lett. 13(2): 73-76 (1981) - [j34]Ronald V. Book:
Bounded Query Machines: On NP and PSPACE. Theor. Comput. Sci. 15: 27-39 (1981) - [j33]Ronald V. Book, Celia Wrathall:
Bounded Query Machines: On NP( ) and NPQERY( ). Theor. Comput. Sci. 15: 41-50 (1981) - [j32]Ronald V. Book, Colm Ó'Dúnlaing:
Testing for the Church-Rosser Property. Theor. Comput. Sci. 16: 223-229 (1981) - 1980
- [j31]Ronald V. Book, Franz-Josef Brandenburg:
Equality Sets and Complexity Classes. SIAM J. Comput. 9(4): 729-743 (1980) - [j30]Ronald V. Book, Sai Choi Kwan:
On Uniquely Decipherable Codes with Two Codewords. IEEE Trans. Computers 29(4): 324-325 (1980) - 1979
- [j29]Ronald V. Book:
On Languages Accepted by Space-Bounded Oracle Machines. Acta Informatica 12: 177-185 (1979) - [j28]Ronald V. Book:
A Remark on Tally Languages and Complexity Classes. Inf. Control. 43(2): 198-201 (1979) - [j27]Ronald V. Book, Sheila A. Greibach, Celia Wrathall:
Reset Machines. J. Comput. Syst. Sci. 19(3): 256-276 (1979) - [j26]Ronald V. Book:
Polynomial Space and Transitive Closure. SIAM J. Comput. 8(3): 434-439 (1979) - 1978
- [j25]Ronald V. Book:
On the Complexity of Formal Grammars. Acta Informatica 9: 171-181 (1978) - [j24]Ronald V. Book, Sheila A. Greibach:
The Independence of Certain Operations on semiAFLS. RAIRO Theor. Informatics Appl. 12(4): 369-385 (1978) - [j23]Ronald V. Book:
Simple Representations of Certain Classes of Languages. J. ACM 25(1): 23-31 (1978) - [j22]Ronald V. Book, Maurice Nivat:
Linear Languages and the Intersection Closures of Classes of Languages. SIAM J. Comput. 7(2): 167-177 (1978) - [j21]Ronald V. Book:
Celia Wrathall: On Languages Specified by Relative Acceptance. Theor. Comput. Sci. 7: 185-195 (1978) - 1977
- [j20]Ronald V. Book:
On Languages With a Certain Prefix Property. Math. Syst. Theory 10: 229-237 (1977) - [j19]Ronald V. Book, Celia Wrathall, Alan L. Selman, David P. Dobkin:
Inclusion Complete Tally Languages and the Hartmanis-Berman Conjecture. Math. Syst. Theory 11: 1-8 (1977) - 1976
- [j18]Ronald V. Book, Ashok K. Chandra:
Inherently Nonplanar Automata. Acta Informatica 6: 89-94 (1976) - [j17]Ronald V. Book:
Translational Lemmas, Polynomial Time, and (log n)^j-Space. Theor. Comput. Sci. 1(3): 215-226 (1976) - 1974
- [j16]Ronald V. Book, Michael A. Harrison:
Mutually divisible semigroups. Discret. Math. 9(4): 329-332 (1974) - [j15]Ronald V. Book:
Tally Languages and Complexity Classes. Inf. Control. 26(2): 186-193 (1974) - [j14]Brenda S. Baker, Ronald V. Book:
Reversal-Bounded Multipushdown Machines. J. Comput. Syst. Sci. 8(3): 315-332 (1974) - [j13]Ronald V. Book:
Comparing Complexity Classes. J. Comput. Syst. Sci. 9(2): 213-229 (1974) - [j12]Ronald V. Book, Maurice Nivat, Mike Paterson:
Reversal-Bounded Acceptors and Intersections of Linear Languages. SIAM J. Comput. 3(4): 283-295 (1974) - 1973
- [j11]Ronald V. Book:
Free and almost-free subsemigroups of a free semigroup. Discret. Math. 4(3): 233-241 (1973) - [j10]Ronald V. Book:
On the structure of context-sensitive grammars. Int. J. Parallel Program. 2(2): 129-139 (1973) - 1972
- [j9]Ronald V. Book, Seymour Ginsburg:
Multi-Stack-Counter Languages. Math. Syst. Theory 6(1): 37-48 (1972) - [j8]Ronald V. Book:
Terminal Context in Context-Sensitive Grammars. SIAM J. Comput. 1(1): 20-30 (1972) - [j7]Ronald V. Book:
On Languages Accepted in Polynomial Time. SIAM J. Comput. 1(4): 281-287 (1972) - 1971
- [j6]Ronald V. Book, Ben Wegbreit:
A Note on AFLs and Bounding Erasing. Inf. Control. 19(1): 18-29 (1971) - [j5]Ronald V. Book:
Time-Bounded Grammars and Their Languages. J. Comput. Syst. Sci. 5(4): 397-429 (1971) - [j4]Ronald Vernon Book, Shimon Even, Sheila A. Greibach, Gene Ott:
Ambiguity in Graphs and Expressions. IEEE Trans. Computers 20(2): 149-153 (1971) - 1970
- [j3]Ronald V. Book, Sheila A. Greibach, Ben Wegbreit:
Time- and Tape-Bounded Turing Acceptors and AFLs. J. Comput. Syst. Sci. 4(6): 606-621 (1970) - [j2]Ronald V. Book, Sheila A. Greibach, Oscar H. Ibarra, Ben Wegbreit:
Tape-Bounded Turing Acceptors and Principal AFLs. J. Comput. Syst. Sci. 4(6): 622-625 (1970) - [j1]Ronald V. Book, Sheila A. Greibach:
Quasi-Realtime Languages. Math. Syst. Theory 4(2): 97-111 (1970)
Conference and Workshop Papers
- 1996
- [c42]Ronald V. Book, Heribert Vollmer, Klaus W. Wagner:
On Type-2 Probabilistic Quantifiers. ICALP 1996: 369-380 - 1994
- [c41]Ronald V. Book, Osamu Watanabe
On Random Hard Sets for NP. ISAAC 1994: 47-55 - [c40]Ronald V. Book, Jack H. Lutz, David M. Martin Jr.:
The Global Power of Additional Queries to Random Oracles. STACS 1994: 403-414 - 1993
- [c39]Ronald V. Book:
Relativizing Complexity Classes With Random Oracles. ISAAC 1993: 250-258 - 1992
- [c38]Ronald V. Book, Jack H. Lutz:
On Languages with Very High Information Content. SCT 1992: 255-259 - [c37]Ronald V. Book:
Additional Queries and Algorithmically Random Languages. Complexity Theory: Current Research 1992: 69-82 - [c36]Ronald V. Book:
Relativizations of the P =?NP and other Problems: Some Developments in Structural Complexity Theory. ISAAC 1992: 175-186 - [c35]Ronald V. Book, Jack H. Lutz, Klaus W. Wagner:
On Complexity Classes and Algorithmically Random Languages (Extended Abstract). STACS 1992: 319-328 - 1990
- [c34]Ronald V. Book:
On Separating Complexity Classes. SCT 1990: 299-304 - [c33]Ronald V. Book, Jack H. Lutz, Shouwen Tang:
Additional Queries to Random and Pseudorandom Oracles. ICALP 1990: 283-293 - [c32]Ronald V. Book:
A Note on Confluent Thue Systems. IWWERT 1990: 231-236 - 1988
- [c31]Ronald V. Book, Ding-Zhu Du, David A. Russo:
On polynomial and generalized complexity cores. SCT 1988: 236-250 - [c30]Shouwen Tang, Ronald V. Book:
Separating Polynomial-Time Turing and Truth-Table Reductions by Tally Sets. ICALP 1988: 591-599 - [c29]Ronald V. Book:
Sparse Sets, Tally Sets, and Polynomial Reducibilities. MFCS 1988: 1-13 - 1987
- [c28]Ronald V. Book, Ker-I Ko:
On sets reducible to sparse sets. SCT 1987: 147-154 - [c27]Ronald V. Book:
Towards a Theory of Relativizations: Positive Relativizations. STACS 1987: 1-21 - 1986
- [c26]Ronald V. Book, Pekka Orponen
On Exponential Lowness. ICALP 1986: 40-49 - [c25]José L. Balcázar, Ronald V. Book:
On Generalized Kolmogorov Complexity. STACS 1986: 334-340 - 1985
- [c24]Ronald V. Book, Friedrich Otto:
The Verifiability of Two-Party Protocols. EUROCRYPT 1985: 254-260 - [c23]Ronald V. Book, Jörg H. Siekmann:
On the Unification Hierarchy. GWAI 1985: 111-117 - [c22]Ronald V. Book:
Thue Systems as Rewriting Systems. RTA 1985: 63-94 - 1984
- [c21]José L. Balcázar, Ronald V. Book, Timothy J. Long, Uwe Schöning, Alan L. Selman:
Sparse Oracles and Uniform Complexity Classes. FOCS 1984: 308-311 - [c20]José L. Balcázar, Ronald V. Book, Uwe Schöning:
Sparse Oracles, Lowness, and Highness. MFCS 1984: 185-193 - 1983
- [c19]Uwe Schöning, Ronald V. Book:
Immunity (Extended Abstract). ICALP 1983: 653-661 - [c18]Ronald V. Book, Timothy J. Long, Alan L. Selman:
Controlled relativizations of P and NP. Theoretical Computer Science 1983: 85-90 - 1982
- [c17]Ronald V. Book:
The Power of the Church-Rosser Property for String Rewriting Systems. CADE 1982: 360-368 - 1981
- [c16]Ronald V. Book, Christopher B. Wilson, Mei-rui Xu:
Relativizing Time and Space (Preliminary Report). FOCS 1981: 254-259 - [c15]Ronald V. Book, Matthias Jantzen, Burkhard Monien, Colm Ó'Dúnlaing, Celia Wrathall:
On the Complexity of Word Problems in Certain Thue Systems (Preliminary Report). MFCS 1981: 216-223 - [c14]Ronald V. Book, Matthias Jantzen, Celia Wrathall:
(Erasing)* Strings. Theoretical Computer Science 1981: 252-259 - 1979
- [c13]Ronald V. Book, Franz-Josef Brandenburg:
Representing Complexity Classes by Equality Sets (Preliminary Report). ICALP 1979: 49-57 - [c12]Ronald V. Book:
Complexity Classes of Formal Languages (Preliminary Report). MFCS 1979: 43-56 - 1978
- [c11]Ronald V. Book, Sheila A. Greibach, Celia Wrathall:
Comparisons and Reset Machines (Preliminary Report). ICALP 1978: 113-124 - 1977
- [c10]Ronald V. Book:
Language Representation Theorems: How to Generate the R. E. Sets from the Regular Sets. FOCS 1977: 58-61 - [c9]Ronald V. Book, Chee-Keng Yap:
On the Computational Power of Reversal-Bounded Machines. ICALP 1977: 111-119 - 1975
- [c8]Ronald V. Book:
Hauptvortrag: Formal language theory and theoretical computer science. Automata Theory and Formal Languages 1975: 1-15 - 1974
- [c7]Ronald V. Book:
On the Structure of Complexity Classes. ICALP 1974: 437-445 - [c6]Ronald V. Book, Maurice Nivat, Mike Paterson:
Intersections of Linear Context-Free Languages and Reversal-Bounded Multipushdown Machines (Extended Abstract). STOC 1974: 290-296 - 1972
- [c5]Brenda S. Baker, Ronald V. Book:
Reversal-Bounded Multi-Pushdown Machines: Extended Abstract. SWAT 1972: 207-211 - [c4]Ronald V. Book:
Complexity Classes of Formal Languages (Extended Abstract). ICALP 1972: 517-520 - 1970
- [c3]Ronald V. Book, Sheila A. Greibach, Ben Wegbreit:
Tape- and Time-Bounded Turing Acceptors and AFLs: Extended Abstract. STOC 1970: 92-99 - 1969
- [c2]Ronald V. Book, Sheila A. Greibach:
Quasi-Realtime Languages-Extended Abstract. STOC 1969: 15-18 - 1968
- [c1]Ronald V. Book:
Grammars with Linear Time Functions. SWAT 1968: 298-305
Parts in Books or Collections
- 1993
- [p1]Ronald V. Book, Osamu Watanabe:
A View of Structural Complexity Theory. Current Trends in Theoretical Computer Science 1993: 451-468
Editorship
- 1991
- [e1]Ronald V. Book:
Rewriting Techniques and Applications, 4th International Conference, RTA-91, Como, Italy, April 10-12, 1991, Proceedings. Lecture Notes in Computer Science 488, Springer 1991, ISBN 3-540-53904-2 [contents]
Informal and Other Publications
- 1996
- [i1]Ronald V. Book, Heribert Vollmer, Klaus W. Wagner:
Probabilistic Type-2 Operators and "Almost"-Classes. Electron. Colloquium Comput. Complex. TR96 (1996)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-04-25 05:56 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: