@article{Chung-Ravikumar/89,
AUTHOR = {Chung, Moon Jung and Ravikumar, B.},
TITLE = {Strong nondeterministic Turing reduction - A technique for proving intractability},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {39},
PAGES = {2-20},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Abadi-Feigenbaum-Kilian/89,
AUTHOR = {Abadi, Mart{\'i}n and Feigenbaum, Joan and Kilian, Joe},
TITLE = {On hiding information from an oracle},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {39},
PAGES = {21-50},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Leivant/89,
AUTHOR = {Leivant, Daniel},
TITLE = {Descriptive characterizations of computational complexity},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {39},
PAGES = {51-83},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Schoning/89,
AUTHOR = {Sch{\"o}ning, Uwe},
TITLE = {Probabilistic complexity classes and lowness},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {39},
PAGES = {84-100},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Allender/89c,
AUTHOR = {Allender, Eric W.},
TITLE = {Some consequences of the existence of pseudorandom generators},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {39},
PAGES = {101-124},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Guibas-Hershberger/89,
AUTHOR = {Guibas, Leonidas J. and Hershberger, John},
TITLE = {Optimal shortest path queries in a simple polygon},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {39},
PAGES = {126-152},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Dadoun-Kirkpatrick/89,
AUTHOR = {Dadoun, N. and Kirkpatrick, D.G.},
TITLE = {Parallel construction of subdivision hierarchies},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {39},
PAGES = {153-165},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Culberson-Reckhow/89,
AUTHOR = {Culberson, Joseph and Reckhow, Robert A.},
TITLE = {Orthogonally convex coverings of orthogonal polygons without holes},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {39},
PAGES = {166-204},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Chew/89a,
AUTHOR = {Chew, L. Paul},
TITLE = {There are planar graphs almost as good as the complete graph},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {39},
PAGES = {205-219},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Suri/89,
AUTHOR = {Suri, Subhash},
TITLE = {Computing geodesic furthest neighbors in simple polygons},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {39},
PAGES = {220-235},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Sugihara/89,
AUTHOR = {Sugihara, Kokichi},
TITLE = {On finite-precision representations of geometric objects},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {39},
PAGES = {236-247},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Ambos-Spies/89,
AUTHOR = {Ambos-Spies, Klaus},
TITLE = {Honest polynomial time reducibilities and the $P =? NP$ problem},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {39},
PAGES = {250-281},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Kadin/89,
AUTHOR = {Kadin, Jim},
TITLE = {$P^{NP[O(\log n)]}$ and sparse Turing-complete sets for $NP$},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {39},
PAGES = {282-298},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Hemachandra/89,
AUTHOR = {Hemachandra, Lane A.},
TITLE = {The strong exponential hierarchy collapses},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {39},
PAGES = {299-322},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Greenlaw/89,
AUTHOR = {Greenlaw, Raymond},
TITLE = {Ordered vertex removal and subgraph problems},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {39},
PAGES = {323-342},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{America-Rutten/89,
AUTHOR = {America, Pierre and Rutten, Jan},
TITLE = {Solving reflexive domain equations in a category of complete metric spaces},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {39},
PAGES = {343-375},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Robinson-Goldman/89,
AUTHOR = {Robinson, A.G. and Goldman, A.J.},
TITLE = {The set coincidence game: Complexity, attainability, and symmetric strategies},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {39},
PAGES = {376-387},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Coffman-Leighton/89,
AUTHOR = {Coffman, E.G., Jr. and Leighton, F.T.},
TITLE = {A provably efficient algorithm for dynamic storage allocation},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {38},
PAGES = {2-35},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Yannakakis/89,
AUTHOR = {Yannakakis, Mihalis},
TITLE = {Embedding planar graphs in four pages},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {38},
PAGES = {36-67},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Cai/89a,
AUTHOR = {Cai, Jin-Yi},
TITLE = {With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {38},
PAGES = {68-85},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Driscoll-Sarnak-Sleator-Tarjan/89,
AUTHOR = {Driscoll, James R. and Sarnak, Neil and Sleator, Daniel D. and Tarjan, Robert E.},
TITLE = {Making data structures persistent},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {38},
PAGES = {86-124},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Ajtai-Komlos-Steiger-Szemeredi/89,
AUTHOR = {Ajtai, Mikl{\'o}s and Koml{\'o}s, J{\'a}nos and Steiger, W.L. and Szemer{\'e}di, Endre},
TITLE = {Optimal parallel selection has complexity $O(\log\log n)$},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {38},
PAGES = {125-133},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Galil-Kannan-Szemeredi/89,
AUTHOR = {Galil, Zvi and Kannan, Ravi and Szemer{\'e}di, Endre},
TITLE = {On nontrivial separators, for $k$-page graphs and simulations by nondeterministic one-tape Turing machines},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {38},
PAGES = {134-149},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Barrington/89,
AUTHOR = {Barrington, David A.},
TITLE = {Bounded-width polynomial-size branching programs recognize exactly those languages in $NC^1$},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {38},
PAGES = {150-164},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Edelsbrunner-Guibas/89,
AUTHOR = {Edelsbrunner, Herbert and Guibas, Leonidas J.},
TITLE = {Topologically sweeping an arrangement},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {38},
PAGES = {165-194},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
NOTE = {see Corrigendum in J. Comput.~Syst.~Sci.~42, 249-251},
}
@article{Halpern-Vardi/89,
AUTHOR = {Halpern, Joseph Y. and Vardi, Moshe Y.},
TITLE = {The complexity of reasoning about knowledge and time I. Lower bounds},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {38},
PAGES = {195-237},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Mannila-Raiha/89,
AUTHOR = {Mannila, Heikki and R{\"a}ih{\"a}, Kari-Jouko},
TITLE = {Automatic generation of fest data for relational queries},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {38},
PAGES = {240-258},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Naughton/89a,
AUTHOR = {Naughton, Jeffrey F.},
TITLE = {Data independent recursion in deductive databases},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {38},
PAGES = {259-289},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Bidoit-Hull/89,
AUTHOR = {Bidoit, Nicole and Hull, Richard},
TITLE = {Minimalism, justification and non-monotonicity in deductive databases},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {38},
PAGES = {290-325},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Bancilhon-Khoshafian/89,
AUTHOR = {Bancilhon, Fran{\c{c}}ois and Khoshafian, Setrag},
TITLE = {A calculus for complex objects},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {38},
PAGES = {326-340},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Afrati-Papadimitriou-Papageorgiou-Roussou-Sagiv-Ullman/89,
AUTHOR = {Afrati, Foto and Papadimitriou, Christos H. and Papageorgiou, George and Roussou, Athena and Sagiv, Yehoshua and Ullman, Jeffrey D.},
TITLE = {On the convergence of query evaluation},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {38},
PAGES = {341-359},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Hadzilacos-Yannakakis/89,
AUTHOR = {Hadzilacos, Thanasis and Yannakakis, Mihalis},
TITLE = {Deleting completed transactions},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {38},
PAGES = {360-379},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Sagiv-Shmueli/89,
AUTHOR = {Sagiv, Yehoshua and Shmueli, Oded},
TITLE = {A characterization of finite fd-acyclicity},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {38},
PAGES = {380-404},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Olken-Rotem/89,
AUTHOR = {Olken, Frank and Rotem, Doron},
TITLE = {Rearranging data to maximize the efficiency of compression},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {38},
PAGES = {405-430},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Hromkovic-Inoue-Takanami/89,
AUTHOR = {Hromkovi{\v{c}}, Juraj and Inoue, Katsushi and Takanami, Itsuo},
TITLE = {Lower bounds for language recognition on two-dimensional alternating multihead machines},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {38},
PAGES = {431-451},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Ibarra-Jiang-Chang/89,
AUTHOR = {Ibarra, Oscar H. and Jiang, Tao and Chang, Jik H.},
TITLE = {On iterative and cellular tree arrays},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {38},
PAGES = {452-473},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Fle/89,
AUTHOR = {Fl{\'e}, Marie-Paule},
TITLE = {Serialization of concurrent programs},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {38},
PAGES = {474-493},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Pan-Reif/89,
AUTHOR = {Pan, Victor and Reif, John},
TITLE = {Fast and efficient solution of path algebra problems},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {38},
PAGES = {494-510},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}
@article{Rich/89,
AUTHOR = {Rich, Craig A.},
TITLE = {Positive relativizations of the $P =? NP$ problem},
JOURNAL = {J. Comput.~Syst.~Sci.},
VOLUME = {38},
PAGES = {511-523},
YEAR = {1989},
PUBLISHER = {Academic Press},
ADDRESS = {New York-San Francisco-London-San Diego},
}