@string{infcomp = "Info. Comp."}
@string{infcon = "Info. Control"}
@string{jcss = "J. Comp. Sys. Sci."}
@string{lncs = "Lect. Notes in Comp. Sci."},
@string{mathsys = "Math. Sys. Thy."}
@string{mst = "Math. Sys. Thy."}
@string{sicomp = "SIAM J. Comput."}
@string{sigact = "SIGACT News"}
@string{springer = "Springer Verlag"}
@string{tcs = "Theor. Comp. Sci."}
@string{aicalp = "Annual International Conference on Automata, Languages, and Pr
ogramming"}
@string{astacs = "Annual Symposium on Theoretical Aspects of Computer Science"}
@string{aicci = "Annual International Conference on Computers and Information"}
@string{astructures = "Annual IEEE Conference on Structure in Complexity Theory"
}
@string{ifct = "International Conference on Fundamentals of Computation Theory"}@string{icalp = aicalp}
@string{stacs = astacs}
@string{icci = aicci}
@string{structures = astructures}
@string{fct = ifct}
@string{proc1 = "Proc. 1st "}
@string{proc2 = "Proc. 2nd "}
@string{proc3 = "Proc. 3rd "}
@string{proc4 = "Proc. 4th "}
@string{proc5 = "Proc. 5th "}
@string{proc6 = "Proc. 6th "}
@string{proc11 = "Proc. 11th "}
@string{proc13 = "Proc. 13th "}
% Etc.
@inproceedings{Reg83a,
author = {K. Regan},
title = {On diagonalization methods and the structure of
language classes},
booktitle = {Proceedings, International Conference
on Foundations of Computation Theory (FCT'83), Borgholm, Sweden,
August 1983},
series = lncs,
volume = {158},
publisher = springer,
year = {1983},
pages = {368--380}
}
@inproceedings{Reg83b,
author = {K. Regan},
title = {Arithmetical degrees of index sets for
complexity classes},
booktitle = {Proceedings, Logic and Machines, M{\"u}nster,
Germany, May 1983},
series = lncs,
volume = {171},
publisher = springer,
year = {1984},
pages = {118--130}
}
@inproceedings{Reg86a,
author = {K. Regan},
title = {A topology of provability in complexity theory},
booktitle = proc1 # structures,
series = lncs,
volume = {223},
publisher = springer,
year = {1986},
pages = {291--310}
}
@inproceedings{Reg86b,
author = {K. Regan},
title = {A uniform reduction theorem, extending a result of
{J. Gorllmann} and {A. Selman}},
booktitle = proc13 # icalp,
series = lncs,
volume = {226},
publisher = springer,
year = {1986},
pages = {324--333}
}
@phdthesis{Reg86t,
author = {K. Regan},
title = {On the Separation of Complexity Classes},
school = {Oxford University},
year = {1986}
}
@article{Reg88,
author = {K. Regan},
title = {The topology of provability in complexity theory},
journal = jcss,
volume = {3},
year = {1988},
pages = {384--432}
}
@inproceedings{Reg89,
author = {K. Regan},
title = {Finitary substructure languages},
booktitle = proc4 # structures,
year = {1989},
pages = {87--96}
}
@article{Reg92d,
author = {K. Regan},
title = {Diagonalization, uniformity, and fixed-point theorems},
journal = {infcomp},
volume = {98},
year = {1992},
pages = {1--40}
}
@article{Reg92m,
author = {K. Regan},
title = {Minimum-complexity pairing functions},
journal = jcss,
volume = {45},
year = {1992},
pages = {385--395}
}
@techreport{Reg92l,
author = {K. Regan},
title = {Linear time and memory efficient computation},
institution = {Computer Science Department, State University of
NY at Buffalo, TR 92-28},
year = {1992},
}
@misc{Reg92i,
author = {K. Regan},
title = {The complexity of instance contraction},
month = {November},
year = {1992}
}
@misc{ReRo92,
author = {K. Regan and J. Royer},
title = {On closure properties of bounded {2-sided} error
complexity classes},
institution = {Dept. of Computer Science, University at Buffalo},
year = {1992},
note = {To appear in {\it Math. Sys. Thy.\/}}
}
@techreport{GKRST92,
author = {F. Green and J. K{\"o}bler and K. Regan and
T. Schwentick and J. Tor{\'a}n},
title = {The power of the middle bit of a {\#}{P} function},
institution = {Computer Science Dept., University at Buffalo},
number = {UBCS--TR 92--27},
year = {1992}
}
@techreport{JaRe92,
author = {A. Jagota and K. Regan},
title = {Performance of {MAX-CLIQUE} approximation heuristics under
description-length weighted distributions},
institution = {Computer Science Dept., University at Buffalo},
number = {UB-CS-TR 92-24},
year = {1992}
}
@inproceedings{ReSc92,
author = {K. Regan and T. Schwentick},
title = {On the power of one bit of a {\#P} function},
booktitle = proc4 # "Annual Italian Conference on Theoretical Computer S
cience",
publisher = {World Scientific, Singapore},
year = {1992},
pages = {317--329}
}
@article{Reg93s,
author = {K. Regan},
title = {Machine Models and Linear Time Complexity},
journal = sigact,
volume = {24},
month = {October},
year = {1993},
note = {Guest column, L. Hemachandra ed., ``Compelxity Theory Column''},
pages = {5--15}
}
@inproceedings{Reg93i,
author = {K. Regan},
title = {On the difference between {Turing} machine time and
random-access machine time},
booktitle = proc5 # icci,
year = {1993},
pages = {36--40}
}
@inproceedings{Reg93p,
author = {K. Regan},
title = {A new parallel vector model, with exact characterizations
of {$\NC^k$}},
booktitle = proc11 # stacs,
volume = {778},
series = lncs,
publisher = springer,
year = {1994},
pages = {289--300}
}
@inproceedings{Reg93t,
author = {K. Regan},
title = {On the difference between {Turing} machine time and
random-access machine time},
booktitle = proc5 # icci,
year = {1993},
pages = {36--40}
}
@techreport{Reg94,
author = {K. Regan},
title = {Linear time and memory efficient computation},
institution = {Computer Science Dept., University at Buffalo},
number = {UB-CS-TR 94-18},
note = {Revision of UB-CS-TR 92-28, accepted to
{\it SIAM J.~Comput.}},
year = {1994}
}
@techreport{GKRST94,
author = {F. Green and J. K{\"o}bler and K. Regan and
T. Schwentick and J. Tor{\'a}n},
title = {The power of the middle bit of a {\#}{P} function},
institution = {Computer Science Dept., University at Buffalo},
number = {UB-CS-TR 94-19},
month = {May},
year = {1992},
note = {To appear in {\it J. Comp. Sys. Sci.}}
}
@inproceedings{LOR94,
author = {L. Li and M. Ogihara and K. Regan},
title = {On information from {\#P} functions},
booktitle = proc6 # icci,
year = {1994},
note = {The proceedings will appear as the first issue of the
electronic journal, {\it Journal of Computing and Information\/}.
Also UB-CS-TR 94-20, May 1994}}
}
@techreport{NRS94,
author = {A. Naik and K. Regan and D. Sivakumar},
title = {Quasilinear time complexity theory},
institution = {Department of Computer Science, University at Buffalo},
number = {UB-CS TR 94-21},
year = {1994},
note = {Submitted to {\em Theoretical Computer Science\/}. An
earlier version appeared in the proceedings of STACS'94, LNCS 778,
pp~97--108/}
}
@techreport{CLLORS94,
author = {J.-Y. Cai and R. Lipton and L. Longpr{\'e} and
M. Ogihara and K. Regan and D. Sivakumar},
title = {Communication complexity of key agreement on limited ranges},
institution = {Computer Science Dept., University at Buffalo},
number = {UB-CS-TR 94-22},
month = {May},
year = {1994}
}
@techreport{Reg94a,
author = {K. Regan},
title = {Linear time algorithms in memory hierarchies},
institution = {Computer Science Dept., University at Buffalo},
number = {UB-CS-TR 94-23},
month = {May},
year = {1994},
note = {To appear in the proceedings of the IFIP World Computer
Congress, Hamburg, August 1994}
}
@techreport{Reg94b,
author = {K. Regan},
title = {Linear speed-up, information vicinity, and finite-state
machines},
institution = {Computer Science Dept., University at Buffalo},
number = {UB-CS-TR 94-24},
month = {May},
year = {1994},
note = {To appear in the proceedings of the IFIP World Computer
Congress, Hamburg, August 1994}
}