 | 1998 |
|---|
| 122 |       | Ronald V. Book,
Heribert Vollmer,
Klaus W. Wagner:
Probabilistic Type-2 Operators and "Almost"-Classes.
Computational Complexity 7(3): 265-289 (1998) |
| 1996 |
|---|
| 121 | | Ronald V. Book,
Heribert Vollmer,
Klaus W. Wagner:
On Type-2 Probabilistic Quantifiers.
ICALP 1996: 369-380 |
| 120 | | Ronald 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 |
|---|
| 116 | | Ronald V. Book,
Osamu Watanabe:
On Random Hard Sets for NP.
ISAAC 1994: 47-55 |
| 115 | | Ronald 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 |
|---|
| 111 | | Ronald 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 |
| 108 | | Ronald V. Book:
Relativizations of the P =?NP and other Problems: Some Developments in Structural Complexity Theory.
ISAAC 1992: 175-186 |
| 107 | | Ronald 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 |
|---|
| 99 | | Ronald 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 |
|---|
| 92 | | Shouwen Tang,
Ronald V. Book:
Separating Polynomial-Time Turing and Truth-Table Reductions by Tally Sets.
ICALP 1988: 591-599 |
| 91 | | Ronald 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 |
|---|
| 87 | | Ronald 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) |
| 85 | | Ronald 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 |
|---|
| 83 | | Ronald V. Book,
Pekka Orponen,
David A. Russo,
Osamu Watanabe:
On Exponential Lowness.
ICALP 1986: 40-49 |
| 82 | | José 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) |
| 80 | | José 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 |
|---|
| 77 | | Ronald 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 |
| 75 | | Ronald 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 |
| 67 | | José L. Balcázar,
Ronald V. Book,
Uwe Schöning:
Sparse Oracles, Lowness, and Highness.
MFCS 1984: 185-193 |
| 66 | | Ronald V. Book:
Homogeneous Thue systems and the Church-Rosser property.
Discrete Mathematics 48(2-3): 137-145 (1984) |
| 65 | | Ronald 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 |
|---|
| 60 | | Uwe 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 |
| 58 | | Xu 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 |
|---|
| 54 | | Ronald V. Book:
The Power of the Church-Rosser Property for String Rewriting Systems.
CADE 1982: 360-368 |
| 53 | | Ronald 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 |
| 47 | | 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 |
| 46 | | Ronald 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 |
|---|
| 38 | | Ronald V. Book,
Franz-Josef Brandenburg:
Representing Complexity Classes by Equality Sets (Preliminary Report).
ICALP 1979: 49-57 |
| 37 | | Ronald 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 |
|---|
| 32 | | Ronald 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) |
| 29 | | Ronald 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 |
| 25 | | Ronald 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 |
|---|
| 19 | | Ronald 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 |
