1998
Probabilistic Type-2 Operators and "Almost"-Classes.
Comput. Complex., 1998
1996
On the Robustness of ALMOST-<i>R</i>.
RAIRO Theor. Informatics Appl., 1996
On Random Hard Sets for NP.
Inf. Comput., 1996
On Type-2 Probabilistic Quantifiers.
Proceedings of the Automata, Languages and Programming, 23rd International Colloquium, 1996
1995
The Global Power of Additional Queries to Random Oracles
Inf. Comput., July, 1995
1994
Relativizations of the P =? NP and Other Problems: Developments in Structural Complexity Theory.
SIAM Rev., 1994
On Languages Reducible to Algorithmically Random Languages.
SIAM J. Comput., 1994
An Observation on Probability Versus Randomness with Applications to Complexity Classes.
Math. Syst. Theory, 1994
On Collapsing the Polynomial-Time Hierarchy.
Inf. Process. Lett., 1994
1993
A View of Structural Complexity Theory.
Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993
On Languages With Very High Space-Bounded Kolmogorov Complexity.
SIAM J. Comput., 1993
Relativizing Complexity Classes With Random Oracles.
Proceedings of the Algorithms and Computation, 4th International Symposium, 1993
String-Rewriting Systems.
Texts and Monographs in Computer Science, Springer, ISBN: 978-1-4613-9771-7, 1993
1992
On Complexity Classes and Algorithmically Random Languages (Extended Abstract).
Proceedings of the STACS 92, 1992
Relativizations of the <i>P =?NP</i> and other Problems: Some Developments in Structural Complexity Theory.
Proceedings of the Algorithms and Computation, Third International Symposium, 1992
Additional Queries and Algorithmically Random Languages.
Proceedings of the Complexity Theory: Current Research, 1992
On Languages with Very High Information Content.
Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992
1991
Polynomial-Time Reducibilities and "Almost All" Oracle Sets.
Theor. Comput. Sci., 1991
Some Observations on Separating Complexity Classes.
SIAM J. Comput., 1991
Reducibilities on tally and sparse sets.
RAIRO Theor. Informatics Appl., 1991
On "Inherently Context-Sensitive" Languages - An Application of Complexity Cores.
Inf. Process. Lett., 1991
On Random Oracle Separations.
Inf. Process. Lett., 1991
1990
Characterizing Polynomial Complexity Classes by Reducibilities.
Math. Syst. Theory, 1990
A Note on Confluent Thue Systems.
Proceedings of the Word Equations and Related Topics, First International Workshop, 1990
Additional Queries to Random and Pseudorandom Oracles.
Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990
On Separating Complexity Classes.
Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990
1989
On Inefficient Special Cases of NP-Complete Problems.
Theor. Comput. Sci., 1989
A Note on Sparse Sets and the Polynomial-Time Hierarchy.
Inf. Process. Lett., 1989
A view of structural complexity theory.
Bull. EATCS, 1989
1988
The Structure of Generalized Complexity Cores.
Theor. Comput. Sci., 1988
Lowness Properties of Sets in the Exponential-Time Hierarchy.
SIAM J. Comput., 1988
On Sets Truth-Table Reducible to Sparse Sets.
SIAM J. Comput., 1988
Sparse Sets, Tally Sets, and Polynomial Reducibilities.
Proceedings of the Mathematical Foundations of Computer Science 1988, 1988
Separating Polynomial-Time Turing and Truth-Table Reductions by Tally Sets.
Proceedings of the Automata, Languages and Programming, 15th International Colloquium, 1988
On polynomial and generalized complexity cores.
Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988
1987
Thue Systems as Rewriting Systems.
J. Symb. Comput., 1987
The existence and density of generalized complexity cores.
J. ACM, 1987
Rewriting Systems and Word Problems in a Free Partially Commutative Monoid.
Inf. Process. Lett., 1987
Towards a Theory of Relativizations: Positive Relativizations.
Proceedings of the STACS 87, 1987
On sets reducible to sparse sets.
Proceedings of the Second Annual Conference on Structure in Complexity Theory, 1987
1986
Sparse Sets, Lowness and Highness.
SIAM J. Comput., 1986
On Unification: Equational Theories Are Not Bounded.
J. Symb. Comput., 1986
The polynomial-time hierarchy and sparse oracles.
J. ACM, 1986
Sets with Small Generalized Kolmogorov Complexity.
Acta Informatica, 1986
On Generalized Kolmogorov Complexity.
Proceedings of the STACS 86, 1986
Proceedings of the Automata, Languages and Programming, 13th International Colloquium, 1986
1985
Reductions in Tree Replacement Systems.
Theor. Comput. Sci., 1985
On the Verifiability of Two-Party Algebraic Protocols.
Theor. Comput. Sci., 1985
On the Security of Name-Stamp Protocols.
Theor. Comput. Sci., 1985
On Bounded Query Machines.
Theor. Comput. Sci., 1985
Qualitative Relativizations of Complexity Classes.
J. Comput. Syst. Sci., 1985
Cancellation Rules and Extended Word Problems.
Inf. Process. Lett., 1985
The base of the intersection of two free submonoids.
Discret. Appl. Math., 1985
On the Unification Hierarchy.
Proceedings of the GWAI-85, 1985
The Verifiability of Two-Party Protocols.
Proceedings of the Advances in Cryptology, 1985
1984
Relativizations of complexity classes.
SIGACT News, 1984
Immunity, Relativizations, and Nondeterminism.
SIAM J. Comput., 1984
Quantitative Relativizations of Complexity Classes.
SIAM J. Comput., 1984
Characterizations of Reduction Classes Modulo Oracle Conditions.
Math. Syst. Theory, 1984
On Expressing Commutativity by Finite Church-Rosser Presentations: A Note on Commutative Monoids.
RAIRO Theor. Informatics Appl., 1984
Almost all one-rule thue systems have decidable word problems.
Discret. Math., 1984
Homogeneous Thue systems and the Church-Rosser property.
Discret. Math., 1984
Sparse Oracles, Lowness, and Highness.
Proceedings of the Mathematical Foundations of Computer Science 1984, 1984
Sparse Oracles and Uniform Complexity Classes
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984
1983
Refining Nondeterminism in Relativizations of Complexity Classes
J. ACM, July, 1983
Decidable Sentences of Church-Rosser Congruences.
Theor. Comput. Sci., 1983
Positive Relativizations of Complexity Classes.
SIAM J. Comput., 1983
A Note on Special Thue Systems with a Single Defining Relation.
Math. Syst. Theory, 1983
Controlled relativizations of P and NP.
Proceedings of the Theoretical Computer Science, 1983
Immunity (Extended Abstract).
Proceedings of the Automata, 1983
1982
Theor. Comput. Sci., 1982
When is a Monoid a Group? The Church-Rosser Case is Tractable.
Theor. Comput. Sci., 1982
Relativizing Time, Space, and Time-Space.
SIAM J. Comput., 1982
A Note on Complete Sets and Transitive Closure.
Math. Syst. Theory, 1982
Confluent and Other Types of Thue Systems.
J. ACM, 1982
The Power of the Church-Rosser Property for String Rewriting Systems.
Proceedings of the 6th Conference on Automated Deduction, 1982
1981
Bounded Query Machines: On NP( ) and NPQERY( ).
Theor. Comput. Sci., 1981
Testing for the Church-Rosser Property.
Theor. Comput. Sci., 1981
Bounded Query Machines: On NP and PSPACE.
Theor. Comput. Sci., 1981
NTS Grammars and Church-Rosser Systems.
Inf. Process. Lett., 1981
The Undecidability of a Word Problem: On a Conjecture of Strong, Maggiolo-Schettini and Rosen.
Inf. Process. Lett., 1981
Proceedings of the Theoretical Computer Science, 1981
On the Complexity of Word Problems in Certain Thue Systems (Preliminary Report).
Proceedings of the Mathematical Foundations of Computer Science 1981, Strbske Pleso, Czechoslovakia, August 31, 1981
Relativizing Time and Space (Preliminary Report)
Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, 1981
1980
On Uniquely Decipherable Codes with Two Codewords.
IEEE Trans. Computers, 1980
Equality Sets and Complexity Classes.
SIAM J. Comput., 1980
1979
A Remark on Tally Languages and Complexity Classes
Inf. Control., November, 1979
Polynomial Space and Transitive Closure.
SIAM J. Comput., 1979
J. Comput. Syst. Sci., 1979
On Languages Accepted by Space-Bounded Oracle Machines.
Acta Informatica, 1979
Complexity Classes of Formal Languages (Preliminary Report).
Proceedings of the Mathematical Foundations of Computer Science 1979, 1979
Representing Complexity Classes by Equality Sets (Preliminary Report).
Proceedings of the Automata, 1979
1978
Celia Wrathall: On Languages Specified by Relative Acceptance.
Theor. Comput. Sci., 1978
Linear Languages and the Intersection Closures of Classes of Languages.
SIAM J. Comput., 1978
Simple Representations of Certain Classes of Languages.
J. ACM, 1978
The Independence of Certain Operations on semiAFLS.
RAIRO Theor. Informatics Appl., 1978
On the Complexity of Formal Grammars.
Acta Informatica, 1978
Comparisons and Reset Machines (Preliminary Report).
Proceedings of the Automata, 1978
1977
Inclusion Complete Tally Languages and the Hartmanis-Berman Conjecture.
Math. Syst. Theory, 1977
On Languages With a Certain Prefix Property.
Math. Syst. Theory, 1977
On the Computational Power of Reversal-Bounded Machines.
Proceedings of the Automata, 1977
Language Representation Theorems: How to Generate the R. E. Sets from the Regular Sets
Proceedings of the 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October, 1977
1976
Translational Lemmas, Polynomial Time, and (log n)^j-Space.
Theor. Comput. Sci., 1976
Inherently Nonplanar Automata.
Acta Informatica, 1976
1975
Hauptvortrag: Formal language theory and theoretical computer science.
Proceedings of the Automata Theory and Formal Languages, 1975
1974
Tally Languages and Complexity Classes
Inf. Control., October, 1974
Reversal-Bounded Acceptors and Intersections of Linear Languages.
SIAM J. Comput., 1974
Comparing Complexity Classes.
J. Comput. Syst. Sci., 1974
Reversal-Bounded Multipushdown Machines.
J. Comput. Syst. Sci., 1974
Mutually divisible semigroups.
Discret. Math., 1974
Intersections of Linear Context-Free Languages and Reversal-Bounded Multipushdown Machines (Extended Abstract)
Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30, 1974
On the Structure of Complexity Classes.
Proceedings of the Automata, Languages and Programming, 2nd Colloquium, University of Saarbrücken, Germany, July 29, 1974
1973
On the structure of context-sensitive grammars.
Int. J. Parallel Program., 1973
Free and almost-free subsemigroups of a free semigroup.
Discret. Math., 1973
1972
On Languages Accepted in Polynomial Time.
SIAM J. Comput., 1972
Terminal Context in Context-Sensitive Grammars.
SIAM J. Comput., 1972
Multi-Stack-Counter Languages.
Math. Syst. Theory, 1972
Complexity Classes of Formal Languages (Extended Abstract).
Proceedings of the Automata, 1972
Reversal-Bounded Multi-Pushdown Machines: Extended Abstract
Proceedings of the 13th Annual Symposium on Switching and Automata Theory, 1972
1971
A Note on AFLs and Bounding Erasing
Inf. Control., August, 1971
Ambiguity in Graphs and Expressions.
IEEE Trans. Computers, 1971
Time-Bounded Grammars and Their Languages.
J. Comput. Syst. Sci., 1971
1970
Quasi-Realtime Languages.
Math. Syst. Theory, 1970
Time- and Tape-Bounded Turing Acceptors and AFLs.
J. Comput. Syst. Sci., 1970
Tape-Bounded Turing Acceptors and Principal AFLs.
J. Comput. Syst. Sci., 1970
Tape- and Time-Bounded Turing Acceptors and AFLs: Extended Abstract
Proceedings of the 2nd Annual ACM Symposium on Theory of Computing, 1970
1969
Quasi-Realtime Languages-Extended Abstract
Proceedings of the 1st Annual ACM Symposium on Theory of Computing, 1969
1968
Grammars with Linear Time Functions
Proceedings of the 9th Annual Symposium on Switching and Automata Theory, 1968
