dblp.uni-trier.dewww.uni-trier.de

Ronald V. Book Vis

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo

*1998
122EERonald V. Book, Heribert Vollmer, Klaus W. Wagner: Probabilistic Type-2 Operators and "Almost"-Classes. Computational Complexity 7(3): 265-289 (1998)
1996
121EERonald V. Book, Heribert Vollmer, Klaus W. Wagner: On Type-2 Probabilistic Quantifiers. ICALP 1996: 369-380
120EERonald V. Book, Heribert Vollmer, Klaus W. Wagner: Probabilistic Type-2 Operators and ``Almost''-Classes Electronic Colloquium on Computational Complexity (ECCC) 3(35): (1996)
119 Ronald V. Book, Elvira Mayordomo: On the Robustness of ALMOST-R. ITA 30(2): 123-133 (1996)
118 Ronald V. Book, Osamu Watanabe: On Random Hard Sets for NP. Inf. Comput. 125(1): 70-76 (1996)
1995
117 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
116EERonald V. Book, Osamu Watanabe: On Random Hard Sets for NP. ISAAC 1994: 47-55
115EERonald V. Book, Jack H. Lutz, David M. Martin Jr.: The Global Power of Additional Queries to Random Oracles. STACS 1994: 403-414
114 Ronald V. Book: On Collapsing the Polynomial-Time Hierarchy. Inf. Process. Lett. 52(5): 235-237 (1994)
113 Ronald V. Book, Jack H. Lutz, Klaus W. Wagner: An Observation on Probability Versus Randomness with Applications to Complexity Classes. Mathematical Systems Theory 27(3): 201-209 (1994)
112 Ronald V. Book: On Languages Reducible to Algorithmically Random Languages. SIAM J. Comput. 23(6): 1275-1282 (1994)
1993
111EERonald V. Book: Relativizing Complexity Classes With Random Oracles. ISAAC 1993: 250-258
110 Ronald V. Book, Jack H. Lutz: On Languages With Very High Space-Bounded Kolmogorov Complexity. SIAM J. Comput. 22(2): 395-402 (1993)
1992
109 Ronald V. Book: Additional Queries and Algorithmically Random Languages. Complexity Theory: Current Research 1992: 69-82
108EERonald V. Book: Relativizations of the P =?NP and other Problems: Some Developments in Structural Complexity Theory. ISAAC 1992: 175-186
107EERonald V. Book, Jack H. Lutz, Klaus W. Wagner: On Complexity Classes and Algorithmically Random Languages (Extended Abstract). STACS 1992: 319-328
106 Ronald V. Book, Jack H. Lutz: On Languages with Very High Information Content. Structure in Complexity Theory Conference 1992: 255-259
1991
105 Ronald V. Book: Rewriting Techniques and Applications, 4th International Conference, RTA-91, Como, Italy, April 10-12, 1991, Proceedings Springer 1991
104 Shouwen Tang, Ronald V. Book: Reducibilities on tally and sparse sets. ITA 25: 293-304 (1991)
103 Ronald V. Book: On Random Oracle Separations. Inf. Process. Lett. 39(1): 7-10 (1991)
102 Volker Diekert, Ronald V. Book: On ``Inherently Context-Sensitive'' Languages - An Application of Complexity Cores. Inf. Process. Lett. 40(1): 21-23 (1991)
101 Ronald V. Book: Some Observations on Separating Complexity Classes. SIAM J. Comput. 20(2): 246-258 (1991)
100 Shouwen Tang, Ronald V. Book: Polynomial-Time Reducibilities and ``Almost All'' Oracle Sets. Theor. Comput. Sci. 81(1): 35-47 (1991)
1990
99EERonald V. Book, Jack H. Lutz, Shouwen Tang: Additional Queries to Random and Pseudorandom Oracles. ICALP 1990: 283-293
98 Ronald V. Book: A Note on Confluent Thue Systems. IWWERT 1990: 231-236
97 Ronald V. Book: On Separating Complexity Classes. Structure in Complexity Theory Conference 1990: 299-304
96 Ronald V. Book, Shouwen Tang: Characterizing Polynomial Complexity Classes by Reducibilities. Mathematical Systems Theory 23(3): 165-174 (1990)
1989
95 Ronald V. Book, Osamu Watanabe: A view of structural complexity theory. Bulletin of the EATCS 39: 122-138 (1989)
94 Ronald V. Book, Shouwen Tang: A Note on Sparse Sets and the Polynomial-Time Hierarchy. Inf. Process. Lett. 33(3): 141-143 (1989)
93 Ding-Zhu Du, Ronald V. Book: On Inefficient Special Cases of NP-Complete Problems. Theor. Comput. Sci. 63(3): 239-252 (1989)
1988
92EEShouwen Tang, Ronald V. Book: Separating Polynomial-Time Turing and Truth-Table Reductions by Tally Sets. ICALP 1988: 591-599
91EERonald V. Book: Sparse Sets, Tally Sets, and Polynomial Reducibilities. MFCS 1988: 1-13
90 Ronald V. Book, Pekka Orponen, David A. Russo, Osamu Watanabe: Lowness Properties of Sets in the Exponential-Time Hierarchy. SIAM J. Comput. 17(3): 504-516 (1988)
89 Ronald V. Book, Ker-I Ko: On Sets Truth-Table Reducible to Sparse Sets. SIAM J. Comput. 17(5): 903-919 (1988)
88 Ronald V. Book, Ding-Zhu Du: The Structure of Generalized Complexity Cores. Theor. Comput. Sci. 61: 103-119 (1988)
1987
87EERonald V. Book: Towards a Theory of Relativizations: Positive Relativizations. STACS 1987: 1-21
86 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)
85EERonald V. Book, Ding-Zhu Du: The existence and density of generalized complexity cores. J. ACM 34(3): 718-730 (1987)
84 Ronald V. Book: Thue Systems as Rewriting Systems. J. Symb. Comput. 3(1/2): 39-68 (1987)
1986
83EERonald V. Book, Pekka Orponen, David A. Russo, Osamu Watanabe: On Exponential Lowness. ICALP 1986: 40-49
82EEJosé L. Balcázar, Ronald V. Book: On Generalized Kolmogorov Complexity. STACS 1986: 334-340
81 José L. Balcázar, Ronald V. Book: Sets with Small Generalized Kolmogorov Complexity. Acta Inf. 23(6): 679-688 (1986)
80EEJosé L. Balcázar, Ronald V. Book, Uwe Schöning: The polynomial-time hierarchy and sparse oracles. J. ACM 33(3): 603-617 (1986)
79 Ronald V. Book, Jörg H. Siekmann: On Unification: Equational Theories Are Not Bounded. J. Symb. Comput. 2(4): 317-324 (1986)
78 José L. Balcázar, Ronald V. Book, Uwe Schöning: Sparse Sets, Lowness and Highness. SIAM J. Comput. 15(3): 739-747 (1986)
1985
77EERonald V. Book, Friedrich Otto: The Verifiability of Two-Party Protocols. EUROCRYPT 1985: 254-260
76 Ronald V. Book, Jörg H. Siekmann: On the Unification Hierarchy. GWAI 1985: 111-117
75EERonald V. Book: Thue Systems as Rewriting Systems. RTA 1985: 63-94
74 Ronald V. Book, Friedrich Otto: Cancellation Rules and Extended Word Problems. Inf. Process. Lett. 20(1): 5-11 (1985)
73 Ronald V. Book, Timothy J. Long, Alan L. Selman: Qualitative Relativizations of Complexity Classes. J. Comput. Syst. Sci. 30(3): 395-413 (1985)
72 Jean H. Gallier, Ronald V. Book: Reductions in Tree Replacement Systems. Theor. Comput. Sci. 37: 123-150 (1985)
71 Ronald V. Book, Friedrich Otto: On the Security of Name-Stamp Protocols. Theor. Comput. Sci. 39: 319-325 (1985)
70 Ronald V. Book, Friedrich Otto: On the Verifiability of Two-Party Algebraic Protocols. Theor. Comput. Sci. 40: 101-130 (1985)
69 José L. Balcázar, Ronald V. Book, Uwe Schöning: On Bounded Query Machines. Theor. Comput. Sci. 40: 237-243 (1985)
1984
68 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
67EEJosé L. Balcázar, Ronald V. Book, Uwe Schöning: Sparse Oracles, Lowness, and Highness. MFCS 1984: 185-193
66EERonald V. Book: Homogeneous Thue systems and the Church-Rosser property. Discrete Mathematics 48(2-3): 137-145 (1984)
65EERonald V. Book, Craig C. Squier: Almost all one-rule thue systems have decidable word problems. Discrete Mathematics 49(3): 237-240 (1984)
64 Jürgen Avenhaus, Ronald V. Book, Craig C. Squier: On Expressing Commutativity by Finite Church-Rosser Presentations: A Note on Commutative Monoids. ITA 18(1): 47-52 (1984)
63 Ronald V. Book, Alan L. Selman: Characterizations of Reduction Classes Modulo Oracle Conditions. Mathematical Systems Theory 17(4): 263-277 (1984)
62 Uwe Schöning, Ronald V. Book: Immunity, Relativizations, and Nondeterminism. SIAM J. Comput. 13(2): 329-337 (1984)
61 Ronald V. Book, Timothy J. Long, Alan L. Selman: Quantitative Relativizations of Complexity Classes. SIAM J. Comput. 13(3): 461-487 (1984)
1983
60EEUwe Schöning, Ronald V. Book: Immunity (Extended Abstract). ICALP 1983: 653-661
59 Ronald V. Book, Timothy J. Long, Alan L. Selman: Controlled relativizations of P and NP. Theoretical Computer Science 1983: 85-90
58EEXu Mei-Rui, John E. Donner, Ronald V. Book: Refining Nondeterminism in Relativizations of Complexity Classes J. ACM 30(3): 677-685 (1983)
57 Ronald V. Book: A Note on Special Thue Systems with a Single Defining Relation. Mathematical Systems Theory 16(1): 57-60 (1983)
56 Alan L. Selman, Xu Mei-Rui, Ronald V. Book: Positive Relativizations of Complexity Classes. SIAM J. Comput. 12(3): 565-579 (1983)
55 Ronald V. Book: Decidable Sentences of Church-Rosser Congruences. Theor. Comput. Sci. 24: 301-312 (1983)
1982
54EERonald V. Book: The Power of the Church-Rosser Property for String Rewriting Systems. CADE 1982: 360-368
53EERonald V. Book: Confluent and Other Types of Thue Systems. J. ACM 29(1): 171-182 (1982)
52 Ronald V. Book, Celia Wrathall: A Note on Complete Sets and Transitive Closure. Mathematical Systems Theory 15(4): 311-313 (1982)
51 Ronald V. Book, Christopher B. Wilson, Xu Mei-Rui: Relativizing Time, Space, and Time-Space. SIAM J. Comput. 11(3): 571-581 (1982)
50 Ronald V. Book: When is a Monoid a Group? The Church-Rosser Case is Tractable. Theor. Comput. Sci. 18: 325-331 (1982)
49 Ronald V. Book, Matthias Jantzen, Celia Wrathall: Monadic Thue Systems. Theor. Comput. Sci. 19: 231-251 (1982)
1981
48 Ronald V. Book, Christopher B. Wilson, Mei-rui Xu: Relativizing Time and Space (Preliminary Report) FOCS 1981: 254-259
47EERonald 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
46EERonald V. Book, Matthias Jantzen, Celia Wrathall: (Erasing)* Strings. Theoretical Computer Science 1981: 252-259
45 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)
44 Ronald V. Book: NTS Grammars and Church-Rosser Systems. Inf. Process. Lett. 13(2): 73-76 (1981)
43 Ronald V. Book: Bounded Query Machines: On NP and PSPACE. Theor. Comput. Sci. 15: 27-39 (1981)
42 Ronald V. Book, Celia Wrathall: Bounded Query Machines: On NP( ) and NPQERY( ). Theor. Comput. Sci. 15: 41-50 (1981)
41 Ronald V. Book, Colm Ó'Dúnlaing: Testing for the Church-Rosser Property. Theor. Comput. Sci. 16: 223-229 (1981)
1980
40 Ronald V. Book, Sai Choi Kwan: On Uniquely Decipherable Codes with Two Codewords. IEEE Trans. Computers 29(4): 324-325 (1980)
39 Ronald V. Book, Franz-Josef Brandenburg: Equality Sets and Complexity Classes. SIAM J. Comput. 9(4): 729-743 (1980)
1979
38EERonald V. Book, Franz-Josef Brandenburg: Representing Complexity Classes by Equality Sets (Preliminary Report). ICALP 1979: 49-57
37EERonald V. Book: Complexity Classes of Formal Languages (Preliminary Report). MFCS 1979: 43-56
36 Ronald V. Book: On Languages Accepted by Space-Bounded Oracle Machines. Acta Inf. 12: 177-185 (1979)
35 Ronald V. Book: A Remark on Tally Languages and Complexity Classes Information and Control 43(2): 198-201 (1979)
34 Ronald V. Book, Sheila A. Greibach, Celia Wrathall: Reset Machines. J. Comput. Syst. Sci. 19(3): 256-276 (1979)
33 Ronald V. Book: Polynomial Apace and Transitive Closure. SIAM J. Comput. 8(3): 434-439 (1979)
1978
32EERonald V. Book, Sheila A. Greibach, Celia Wrathall: Comparisons and Reset Machines (Preliminary Report). ICALP 1978: 113-124
31 Ronald V. Book: On the Complexity of Formal Grammars. Acta Inf. 9: 171-181 (1978)
30 Ronald V. Book, Sheila A. Greibach: The Independence of Certain Operations on semiAFLS. ITA 12(4): (1978)
29EERonald V. Book: Simple Representations of Certain Classes of Languages. J. ACM 25(1): 23-31 (1978)
28 Ronald V. Book, Maurice Nivat: Linear Languages and the Intersection Closures of Classes of Languages. SIAM J. Comput. 7(2): 167-177 (1978)
27 Ronald V. Book: Celia Wrathall: On Languages Specified by Relative Acceptance. Theor. Comput. Sci. 7: 185-195 (1978)
1977
26 Ronald V. Book: Language Representation Theorems: How to Generate the R. E. Sets from the Regular Sets FOCS 1977: 58-61
25EERonald V. Book, Chee-Keng Yap: On the Computational Power of Reversal-Bounded Machines. ICALP 1977: 111-119
24 Ronald V. Book: On Languages With a Certain Prefix Property. Mathematical Systems Theory 10: 229-237 (1977)
23 Ronald V. Book, Celia Wrathall, Alan L. Selman, David P. Dobkin: Inclusion Complete Tally Languages and the Hartmanis-Berman Conjecture. Mathematical Systems Theory 11: 1-8 (1977)
1976
22 Ronald V. Book, Ashok K. Chandra: Inherently Nonplanar Automata. Acta Inf. 6: 89-94 (1976)
21 Ronald V. Book: Translational Lemmas, Polynomial Time, and (log n)^j-Space. Theor. Comput. Sci. 1(3): 215-226 (1976)
1975
20 Ronald V. Book: Hauptvortrag: Formal language theory and theoretical computer science. Automata Theory and Formal Languages 1975: 1-15
1974
19EERonald V. Book: On the Structure of Complexity Classes. ICALP 1974: 437-445
18 Ronald V. Book, Maurice Nivat, Mike Paterson: Intersections of Linear Context-Free Languages and Reversal-Bounded Multipushdown Machines (Extended Abstract) STOC 1974: 290-296
17 Ronald V. Book: Tally Languages and Complexity Classes Information and Control 26(2): 186-193 (1974)
16 Brenda S. Baker, Ronald V. Book: Reversal-Bounded Multipushdown Machines. J. Comput. Syst. Sci. 8(3): 315-332 (1974)
15 Ronald V. Book: Comparing Complexity Classes. J. Comput. Syst. Sci. 9(2): 213-229 (1974)
14 Ronald V. Book, Maurice Nivat, Mike Paterson: Reversal-Bounded Acceptors and Intersections of Linear Languages. SIAM J. Comput. 3(4): 283-295 (1974)
1972
13 Brenda S. Baker, Ronald V. Book: Reversal-Bounded Multi-Pushdown Machines: Extended Abstract FOCS 1972: 207-211
12 Ronald V. Book: Complexity Classes of Formal Languages (Extended Abstract). ICALP 1972: 517-520
11 Ronald V. Book: Multi-Stack-Counter Languages. Mathematical Systems Theory 6(1): 37-48 (1972)
10 Ronald V. Book: Terminal Context in Context-Sensitive Grammars. SIAM J. Comput. 1(1): 20-30 (1972)
9 Ronald V. Book: On Languages Accepted in Polynomial Time. SIAM J. Comput. 1(4): 281-287 (1972)
1971
8 Ronald V. Book, Ben Wegbreit: A Note on AFLs and Bounding Erasing Information and Control 19(1): 18-29 (1971)
7 Ronald V. Book: Time-Bounded Grammars and Their Languages. J. Comput. Syst. Sci. 5(4): 397-429 (1971)
1970
6 Ronald V. Book, Sheila A. Greibach, Ben Wegbreit: Tape- and Time-Bounded Turing Acceptors and AFLs: Extended Abstract STOC 1970: 92-99
5 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)
4 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)
3 Ronald V. Book, Sheila A. Greibach: Quasi-Realtime Languages. Mathematical Systems Theory 4(2): 97-111 (1970)
1969
2 Ronald V. Book, Sheila A. Greibach: Quasi-Realtime Languages-Extended Abstract STOC 1969: 15-18
1968
1 Ronald V. Book: Grammars with Linear Time Functions FOCS 1968: 298-305

Coauthor Index

1Jürgen Avenhaus [64]
2Brenda S. Baker [13] [16]
3José L. Balcázar [67] [68] [69] [78] [80] [81] [82]
4Franz-Josef Brandenburg [38] [39]
5Ashok K. Chandra [22]
6Volker Diekert [102]
7David P. Dobkin [23]
8John E. Donner [58]
9Ding-Zhu Du [85] [88] [93]
10Jean H. Gallier [72]
11Sheila A. Greibach [2] [3] [4] [5] [6] [30] [32] [34]
12Oscar H. Ibarra [4]
13Matthias Jantzen [46] [47] [49]
14Ker-I Ko [89]
15Sai Choi Kwan [40]
16Hai-Ning Liu [86]
17Timothy J. Long [59] [61] [68] [73]
18Jack H. Lutz [99] [106] [107] [110] [113] [115] [117]
19David M. Martin Jr. [115] [117]
20Elvira Mayordomo [119]
21Xu Mei-Rui [51] [56] [58]
22Burkhard Monien [47]
23Maurice Nivat [14] [18] [28]
24Colm Ó'Dúnlaing [41] [47]
25Pekka Orponen [83] [90]
26Friedrich Otto [70] [71] [74] [77]
27Mike Paterson [14] [18]
28David A. Russo [83] [90]
29Uwe Schöning [60] [62] [67] [68] [69] [78] [80]
30Alan L. Selman [23] [56] [59] [61] [63] [68] [73]
31Jörg H. Siekmann [76] [79]
32Craig C. Squier [64] [65]
33Shouwen Tang [92] [94] [96] [99] [100] [104]
34Heribert Vollmer [120] [121] [122]
35Klaus W. Wagner [107] [113] [120] [121] [122]
36Osamu Watanabe [83] [90] [95] [116] [118]
37Ben Wegbreit [4] [5] [6] [8]
38Christopher B. Wilson [48] [51]
39Celia Wrathall [23] [32] [34] [42] [46] [47] [49] [52]
40Mei-rui Xu [48]
41Chee-Keng Yap (Chee Yap) [25]

Colors in the list of coauthors

Copyright © Tue Nov 3 08:52:44 2009 by Michael Ley (ley@uni-trier.de)