@article{Droste-Pech-Vogler/05,
AUTHOR = {Droste, Manfred and Pech, Christian and Vogler, Heiko},
TITLE = {A Kleene theorem for weighted tree automata},
JOURNAL = {Theory of Computing Systems},
VOLUME = {38},
NUMBER = {1},
PAGES = {1-38},
YEAR = {2005},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&id=doi:10.1007/s00224-004-1096-z},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
}
@article{Kuske-Lohrey/05,
AUTHOR = {Kuske, Dietrich and Lohrey, Markus},
TITLE = {Decidable first-order theories of one-step rewriting in trace monoids},
JOURNAL = {Theory of Computing Systems},
VOLUME = {38},
NUMBER = {1},
PAGES = {39-81},
YEAR = {2005},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&id=doi:10.1007/s00224-004-1099-9},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
}
@article{Kosub/05a,
AUTHOR = {Kosub, Sven},
TITLE = {$NP$-partitions over posets with an application to reducing the set of solutions of $NP$ problems},
JOURNAL = {Theory of Computing Systems},
VOLUME = {38},
NUMBER = {1},
PAGES = {83-113},
YEAR = {2005},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&id=doi:10.1007/s00224-004-1114-1},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
}
@article{Pontelli-Ranjan/05,
AUTHOR = {Pontelli, Enrico and Ranjan, Desh},
TITLE = {A simple optimal solution for the temporal precedence problem on pure pointer machines},
JOURNAL = {Theory of Computing Systems},
VOLUME = {38},
NUMBER = {1},
PAGES = {115-130},
YEAR = {2005},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&id=doi:10.1007/s00224-004-1118-x},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
}
@article{Tesson-Therien/05a,
AUTHOR = {Tesson, Pascal and Th{\'e}rien, Denis},
TITLE = {Complete classifications for the communication complexity of regular languages},
JOURNAL = {Theory of Computing Systems},
VOLUME = {38},
NUMBER = {2},
PAGES = {135-159},
YEAR = {2005},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&id=doi:10.1007/s00224-004-1190-2},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
}
@article{Karhumaki-Latteux-Petre/05a,
AUTHOR = {Karhum{\"a}ki, Juhani and Latteux, Michel and Petre, Ion},
TITLE = {Commutation with ternary sets of words},
JOURNAL = {Theory of Computing Systems},
VOLUME = {38},
NUMBER = {2},
PAGES = {161-169},
YEAR = {2005},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&id=doi:10.1007/s00224-004-1191-1},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
}
@article{Szeider/05,
AUTHOR = {Szeider, Stefan},
TITLE = {The complexity of resolution with generalized symmetry rules},
JOURNAL = {Theory of Computing Systems},
VOLUME = {38},
NUMBER = {2},
PAGES = {171-188},
YEAR = {2005},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&id=doi:10.1007/s00224-004-1192-0},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
}
@article{Zheng-Rettinger/05,
AUTHOR = {Zheng, Xizhong and Rettinger, Robert},
TITLE = {Effective Jordan decomposition},
JOURNAL = {Theory of Computing Systems},
VOLUME = {38},
NUMBER = {2},
PAGES = {189-209},
YEAR = {2005},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&id=doi:10.1007/s00224-004-1193-z},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {see Reference correction in Theory of Computing Systems, Vol. 39, 2006, No. 2, 385-385},
}
@article{Buhrman-Fortnow-Pavan/05,
AUTHOR = {Buhrman, Harry and Fortnow, Lance and Pavan, A.},
TITLE = {Some results on derandomization},
JOURNAL = {Theory of Computing Systems},
VOLUME = {38},
NUMBER = {2},
PAGES = {211-227},
YEAR = {2005},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&id=doi:10.1007/s00224-004-1194-y},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
}
@article{Fotakis-Pagh-Sanders-Spirakis/05,
AUTHOR = {Fotakis, Dimitris and Pagh, Rasmus and Sanders, Peter and Spirakis, Paul},
TITLE = {Space efficient hash tables with worst case constant access time},
JOURNAL = {Theory of Computing Systems},
VOLUME = {38},
NUMBER = {2},
PAGES = {229-248},
YEAR = {2005},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&id=doi:10.1007/s00224-004-1195-x},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
}
@article{Biedl-Wilkinson/05,
AUTHOR = {Biedl, Therese and Wilkinson, Dana F.},
TITLE = {Bounded-degree independent sets in planar graphs},
JOURNAL = {Theory of Computing Systems},
VOLUME = {38},
NUMBER = {3},
PAGES = {253-278},
YEAR = {2005},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&id=doi:10.1007/s00224-005-1139-0},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
}
@article{Ambuhl-Wagner/05,
AUTHOR = {Amb{\"u}hl, Christoph and Wagner, Uli},
TITLE = {The clique problem in intersection graphs of ellipses and triangles},
JOURNAL = {Theory of Computing Systems},
VOLUME = {38},
NUMBER = {3},
PAGES = {279-292},
YEAR = {2005},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&id=doi:10.1007/s00224-005-1141-6},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
}
@article{Buchheim-Hong/05,
AUTHOR = {Buchheim, Christoph and Hong, Seok-Hee},
TITLE = {Crossing minimization for symmetries},
JOURNAL = {Theory of Computing Systems},
VOLUME = {38},
NUMBER = {3},
PAGES = {293-311},
YEAR = {2005},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&id=doi:10.1007/s00224-005-1142-5},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
}
@article{Erten-Kobourov/05,
AUTHOR = {Erten, Cesim and Kobourov, Stephen G.},
TITLE = {Simultaneous embedding of a planar graph and its dual on the grid},
JOURNAL = {Theory of Computing Systems},
VOLUME = {38},
NUMBER = {3},
PAGES = {313-327},
YEAR = {2005},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&id=doi:10.1007/s00224-005-1143-4},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
}
@article{Avidor-Zwick/05,
AUTHOR = {Avidor, Adi and Zwick, Uri},
TITLE = {Approximating MIN 2-SAT and MIN 3-SAT},
JOURNAL = {Theory of Computing Systems},
VOLUME = {38},
NUMBER = {3},
PAGES = {329-345},
YEAR = {2005},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&id=doi:10.1007/s00224-005-1140-7},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
}
@article{Jurdzinski-Stachowiak/05,
AUTHOR = {Jurdzi{\'n}ski, Tomasz and Stachowiak, Grzegorz},
TITLE = {Probabilistic algorithms for the wake-up problem in single-hop radio networks},
JOURNAL = {Theory of Computing Systems},
VOLUME = {38},
NUMBER = {3},
PAGES = {347-367},
YEAR = {2005},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&id=doi:10.1007/s00224-005-1144-3},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
}
@article{Gramm-Guo-Huffner-Niedermeier/05,
AUTHOR = {Gramm, Jens and Guo, Jiong and H{\"u}ffner, Falk and Niedermeier, Rolf},
TITLE = {Graph-modeled data clustering: Fixed-parameter algorithms for clique generation},
JOURNAL = {Theory of Computing Systems},
VOLUME = {38},
NUMBER = {4},
PAGES = {373-392},
YEAR = {2005},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&id=doi:10.1007/s00224-004-1178-y},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
}
@article{Kalyanasundaram-Velauthapillai-Waclawsky/05,
AUTHOR = {Kalyanasundaram, Bala and Velauthapillai, Mahe and Waclawsky, John},
TITLE = {Unlocking the advantages of dynamic service selection and pricing},
JOURNAL = {Theory of Computing Systems},
VOLUME = {38},
NUMBER = {4},
PAGES = {393-410},
YEAR = {2005},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&id=doi:10.1007/s00224-004-1179-x},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
}
@article{Bruce-Hoffmann-Krizanc-Raman/05,
AUTHOR = {Bruce, Richard and Hoffmann, Michael and Krizanc, Danny and Raman, Rajeev},
TITLE = {Efficient update strategies for geometric computing with uncertainty},
JOURNAL = {Theory of Computing Systems},
VOLUME = {38},
NUMBER = {4},
PAGES = {411-423},
YEAR = {2005},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&id=doi:10.1007/s00224-004-1180-4},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
}
@article{Koukopoulos-Mavronicolas-Nikoletseas-Spirakis/05,
AUTHOR = {Koukopoulos, Dimitrios and Mavronicolas, Marios and Nikoletseas, Sotiris and Spirakis, Paul},
TITLE = {The impact of network structure on the stability of greedy protocols},
JOURNAL = {Theory of Computing Systems},
VOLUME = {38},
NUMBER = {4},
PAGES = {425-460},
YEAR = {2005},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&id=doi:10.1007/s00224-004-1181-3},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
}
@article{Chan-Lam-Ting-Wong/05,
AUTHOR = {Chan, Wun-Tat and Lam, Tak-Wah and Ting, Hing-Fung and Wong, Prudence W.H.},
TITLE = {On-line stream merging with max span and min coverage},
JOURNAL = {Theory of Computing Systems},
VOLUME = {38},
NUMBER = {4},
PAGES = {461-479},
YEAR = {2005},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&id=doi:10.1007/s00224-004-1182-2},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
}
@article{Bongiovanni-Penna/05,
AUTHOR = {Bongiovanni, Giancarlo and Penna, Paolo},
TITLE = {XOR-based schemes for fast parallel IP lookups},
JOURNAL = {Theory of Computing Systems},
VOLUME = {38},
NUMBER = {4},
PAGES = {481-501},
YEAR = {2005},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&id=doi:10.1007/s00224-004-1183-1},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
}
@article{Gottlieb-Savage-Yerukhimovich/05,
AUTHOR = {Gottlieb, Lee-Ad J. and Savage, John E. and Yerukhimovich, Arkady},
TITLE = {Efficient data storage in large nanoarrays},
JOURNAL = {Theory of Computing Systems},
VOLUME = {38},
NUMBER = {4},
PAGES = {503-536},
YEAR = {2005},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&id=doi:10.1007/s00224-004-1196-9},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
}
@article{Prencipe/05,
AUTHOR = {Prencipe, Giuseppe},
TITLE = {The effect of synchronicity on the behavior of autonomous mobile robots},
JOURNAL = {Theory of Computing Systems},
VOLUME = {38},
NUMBER = {5},
PAGES = {539-558},
YEAR = {2005},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&id=doi:10.1007/s00224-005-1101-1},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
}
@article{Hitchcock/05,
AUTHOR = {Hitchcock, John M.},
TITLE = {Correspondence principles for effective dimensions},
JOURNAL = {Theory of Computing Systems},
VOLUME = {38},
NUMBER = {5},
PAGES = {559-571},
YEAR = {2005},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&id=doi:10.1007/s00224-004-1122-1},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
}
@article{Magniez/05,
AUTHOR = {Magniez, Fr{\'e}d{\'e}ric},
TITLE = {Multi-linearity self-testing with relative error},
JOURNAL = {Theory of Computing Systems},
VOLUME = {38},
NUMBER = {5},
PAGES = {573-591},
YEAR = {2005},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&id=doi:10.1007/s00224-004-1125-y},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
}
@article{Bruyere-Carton/05,
AUTHOR = {Bruy{\`e}re, V{\'e}ronique and Carton, Olivier},
TITLE = {Hierarchy among automata on linear orderings},
JOURNAL = {Theory of Computing Systems},
VOLUME = {38},
NUMBER = {5},
PAGES = {593-621},
YEAR = {2005},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&id=doi:10.1007/s00224-005-1129-2},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
}
@article{Brandstadt-Dragan-Le-Mosca/05,
AUTHOR = {Brandst{\"a}dt, Andreas and Dragan, Feodor F. and Le, Ho{\`a}ng-Oanh and Mosca, Raffaele},
TITLE = {New graph classes of bounded clique-width},
JOURNAL = {Theory of Computing Systems},
VOLUME = {38},
NUMBER = {5},
PAGES = {623-645},
YEAR = {2005},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&id=doi:10.1007/s00224-004-1154-6},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
}
@article{Subramani/05a,
AUTHOR = {Subramani, K.},
TITLE = {Tractable fragments of Presburger arithmetic},
JOURNAL = {Theory of Computing Systems},
VOLUME = {38},
NUMBER = {5},
PAGES = {647-668},
YEAR = {2005},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&id=doi:10.1007/s00224-004-1220-0},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
}
@article{Bollig-Woelfel/05,
AUTHOR = {Bollig, Beate and Woelfel, Philipp},
TITLE = {A lower bound technique for nondeterministic graph-driven read-once-branching programs and its applications},
JOURNAL = {Theory of Computing Systems},
VOLUME = {38},
NUMBER = {6},
PAGES = {671-685},
YEAR = {2005},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&id=doi:10.1007/s00224-004-1130-1},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
}
@article{Finocchi-Petreschi/05,
AUTHOR = {Finocchi, Irene and Petreschi, Rossella},
TITLE = {Structure-preserving hierarchical decompositions},
JOURNAL = {Theory of Computing Systems},
VOLUME = {38},
NUMBER = {6},
PAGES = {687-700},
YEAR = {2005},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&id=doi:10.1007/s00224-004-1132-z},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
}
@article{Zheng-Rettinger-Gengler/05,
AUTHOR = {Zheng, Xizhong and Rettinger, Robert and Gengler, Romain},
TITLE = {Closure properties of real number classes under CBV functions},
JOURNAL = {Theory of Computing Systems},
VOLUME = {38},
NUMBER = {6},
PAGES = {701-729},
YEAR = {2005},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&id=doi:10.1007/s00224-004-1159-1},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
}
@article{Stearns-Hunt/05,
AUTHOR = {Stearns, Richard E. and Hunt III, Harry B.},
TITLE = {Resource bounds and subproblem independence},
JOURNAL = {Theory of Computing Systems},
VOLUME = {38},
NUMBER = {6},
PAGES = {731-761},
YEAR = {2005},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&id=doi:10.1007/s00224-004-1160-8},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
}
@article{Demange-Paschos/05a,
AUTHOR = {Demange, Marc and Paschos, Vangelis},
TITLE = {Improved approximations for weighted and unweighted graph problems},
JOURNAL = {Theory of Computing Systems},
VOLUME = {38},
NUMBER = {6},
PAGES = {763-787},
YEAR = {2005},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&id=doi:10.1007/s00224-004-1162-6},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
}