@article{Bertino-Catania-Shidlovsky/97, AUTHOR = {Bertino, E. and Catania, B. and Shidlovsky, B.}, TITLE = {Towards optimal two-dimensional indexing for constraint databases}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {1}, PAGES = {1-8}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Agrawal-Egecioglu-El_Abbadi/97, AUTHOR = {Agrawal, Divyakant and E{\u{g}}ecio{\u{g}}lu, {\"O}mer and El Abbadi, Amr}, TITLE = {Billiard quorums on the grid}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {1}, PAGES = {9-16}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Belogay-Cabrelli-Molter-Shonkwiler/97, AUTHOR = {Belogay, E. and Cabrelli, C. and Molter, U. and Shonkwiler, R.}, TITLE = {Calculating the Hausdorff distance between curves}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {1}, PAGES = {17-22}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Chang-Chen/97, AUTHOR = {Chang, Hung-Yi and Chen, Rong-Jaye}, TITLE = {Embedding cycles in IEH graphs}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {1}, PAGES = {23-27}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Kulkarni-Arora/97, AUTHOR = {Kulkarni, Sandeep S. and Arora, Anish}, TITLE = {Multitolerant barrier synchronization}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {1}, PAGES = {29-36}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Golic-Salmasizadeh-Simpson-Dawson/97, AUTHOR = {Goli{\'c}, J.Dj. and Salmasizadeh, M. and Simpson, L. and Dawson, E.}, TITLE = {Fast correlation attacks on nonlinear filter generators}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {1}, PAGES = {37-42}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Baruah-Gehrk-Plaxton-Stoica-Abdel-Wahab-Jeffay/97, AUTHOR = {Baruah, Sanjoy K. and Gehrk, Johannes E. and Plaxton, C. Greg and Stoica, Ion and Abdel-Wahab, Hussein and Jeffay, Kevin}, TITLE = {Fair on-line scheduling of a dynamic set of tasks on a single resource}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {1}, PAGES = {43-51}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Arnold-Kanta-Krob/97, AUTHOR = {Arnold, A. and Kanta, M. and Krob, D.}, TITLE = {Recognizable subsets of the two letter plactic monoid}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {2}, PAGES = {53-59}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Coffman-Flatto-Gilbert-Greenberg/97, AUTHOR = {Coffman, E.G., Jr. and Flatto, L. and Gilbert, E.N. and Greenberg, A.G.}, TITLE = {An approximate model of processor communication rings under heavy load}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {2}, PAGES = {61-67}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Kovalyov-Shafransky/97, AUTHOR = {Kovalyov, Mikhail Y. and Shafransky, Yakov M.}, TITLE = {Batch scheduling with deadlines on parallel machines: An $NP$-hard case}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {2}, PAGES = {69-74}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Lee-Kim/97, AUTHOR = {Lee, Gyung-Ok and Kim, Do-Hyung}, TITLE = {Characterization of extended $LR(k)$ grammars}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {2}, PAGES = {75-82}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Coupry/97, AUTHOR = {Coupry, Laurent}, TITLE = {A simple linear algorithm for the edge-disjoint $(s,t)$-paths problem in undirected planar graphs}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {2}, PAGES = {83-86}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Rhee-Welch/97, AUTHOR = {Rhee, Injong and Welch, Jennifer L.}, TITLE = {Time bounds on synchronization in a periodic distributed system}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {2}, PAGES = {87-93}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Chang-Yang/97, AUTHOR = {Chang, Ye-In and Yang, Bi-Yen}, TITLE = {Efficient access methods for image databases}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {2}, PAGES = {95-105}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Dehne-Guimaraes/97, AUTHOR = {Dehne, Frank and Guimar{\~a}es, Katia}, TITLE = {Exact and approximate computational geometry solutions of an unrestricted point set stereo matching problem}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {3}, PAGES = {107-114}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Aaron-Gries/97, AUTHOR = {Aaron, Eric and Gries, David}, TITLE = {Formal justification of underspecification for S5}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {3}, PAGES = {115-121}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Flouret-Laugerotte/97, AUTHOR = {Flouret, M. and Laugerotte, E.}, TITLE = {Noncommutative minimization algorithms}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {3}, PAGES = {123-126}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Aceto-Ingolfsdottir/97, AUTHOR = {Aceto, Luca and Ing{\'{o}}lfsd{\'{o}}ttir, Anna}, TITLE = {A characterization of finitary bisimulation}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {3}, PAGES = {127-134}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Mok-Embley/97, AUTHOR = {Mok, Wai Yin and Embley, David W.}, TITLE = {On improving dependency implication algorithms}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {3}, PAGES = {135-141}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Lin-Chen/97, AUTHOR = {Lin, Min-Sheng and Chen, Deng-Jyi}, TITLE = {The computational complexity of the reliability problem on distributed systems}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {3}, PAGES = {143-147}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Nardelli-Mastrobuoni-Santomo/97a, AUTHOR = {Nardelli, Enrico and Mastrobuoni, Vincenzo and Santomo, Alesiano}, TITLE = {Computing a poset from its realizer}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {3}, PAGES = {149-154}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Albers-Mitzenmacher/97, AUTHOR = {Albers, Susanne and Mitzenmacher, Michael}, TITLE = {Revisiting the COUNTER algorithms for list update}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {3}, PAGES = {155-160}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Alstrup-Secher-Spork/97, AUTHOR = {Alstrup, Stephen and Secher, Jens Peter and Spork, Maz}, TITLE = {Optimal on-line decremental connectivity in trees}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {4}, PAGES = {161-164}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Cesati-Trevisan/97, AUTHOR = {Cesati, Marco and Trevisan, Luca}, TITLE = {On the efficiency of polynomial time approximation schemes}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {4}, PAGES = {165-171}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Kabadi-Aneja/97, AUTHOR = {Kabadi, S.N. and Aneja, Y.P.}, TITLE = {An efficient, strongly polynomial, $\varepsilon$-approximation parametric optimization scheme}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {4}, PAGES = {173-177}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Domingo-Tsukiji-Watanabe/97, AUTHOR = {Domingo, Carlos and Tsukiji, Tatsuie and Watanabe, Osamu}, TITLE = {Partial Occam's razor and its applications}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {4}, PAGES = {179-185}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Tyszkiewicz/97, AUTHOR = {Tyszkiewicz, Jerzy}, TITLE = {A note on the Kolmogorov data complexity and nonuniform logical definitions}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {4}, PAGES = {187-195}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Edalat-Sharp-While/97, AUTHOR = {Edalat, Abbas and Sharp, David and While, Lyndon}, TITLE = {Bounding the attractor of an IFS}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {4}, PAGES = {197-202}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Bagchi/97, AUTHOR = {Bagchi, Anindo}, TITLE = {Route selection with multiple metrics}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {4}, PAGES = {203-205}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{di_Zenzo-Bottoni-Mussio/97, AUTHOR = {di Zenzo, Silvano and Bottoni, Paolo and Mussio, Piero}, TITLE = {A notion of information related to computation}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {4}, PAGES = {207-215}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Reingold-Urban-Gries/97, AUTHOR = {Reingold, Edward M. and Urban, Kenneth J. and Gries, David}, TITLE = {K-M-P string matching revisited}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {5}, PAGES = {217-223}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Hirata/97, AUTHOR = {Hirata, Kouichi}, TITLE = {Constructing simply recursive programs from a finite set of good examples}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {5}, PAGES = {225-230}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Veloso-Veloso/97, AUTHOR = {Veloso, Paulo A.S. and Veloso, Sheila R.M.}, TITLE = {On methods for safe introduction of operations}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {5}, PAGES = {231-238}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Rabi-Sherman/97, AUTHOR = {Rabi, Muhammad and Sherman, Alan T.}, TITLE = {An observation on associative one-way functions in complexity theory}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {5}, PAGES = {239-244}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Wierzbowska/97, AUTHOR = {Wierzbowska, Izabela}, TITLE = {Checker for data structures which sort elements}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {5}, PAGES = {245-249}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Slavik/97, AUTHOR = {Slav{\'{i}}k, Petr}, TITLE = {Improved performance of the greedy algorithm for partial cover}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {5}, PAGES = {251-254}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Dai-Iwano-Katoh/97, AUTHOR = {Dai, Yang and Iwano, Kazuo and Katoh, Naoki}, TITLE = {A new probabilistic analysis of Karger's randomized algorithm for minimum cut problems}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {5}, PAGES = {255-261}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Gupta-Janardan-Smid/97, AUTHOR = {Gupta, Prosenjit and Janardan, Ravi and Smid, Michiel}, TITLE = {A technique for adding range restrictions to generalized searching problems}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {5}, PAGES = {263-269}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Iyengar-Chakrabarty/97, AUTHOR = {Iyengar, Vikram and Chakrabarty, Krishnendu}, TITLE = {An efficient finite-state machine implementation of Huffman decoders}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {6}, PAGES = {271-275}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Mitrana/97a, AUTHOR = {Mitrana, Victor}, TITLE = {Primitive morphisms}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {6}, PAGES = {277-281}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Shokrollahi-Spielman-Stemann/97, AUTHOR = {Shokrollahi, M.A. and Spielman, D.A. and Stemann, V.}, TITLE = {A remark on matrix rigidity}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {6}, PAGES = {283-285}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Graf-Kamakoti/97, AUTHOR = {Graf, T. and Kamakoti, V.}, TITLE = {Sparse dominance queries for many points in optimal time and space}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {6}, PAGES = {287-291}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Woeginger/97, AUTHOR = {Woeginger, Gerhard J.}, TITLE = {There is no asymptotic PTAS for two-dimensional vector packing}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {6}, PAGES = {293-297}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Boldi-Vigna/97, AUTHOR = {Boldi, Paolo and Vigna, Sebastiano}, TITLE = {Minimal sense of direction and decision problems for Cayley graphs}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {6}, PAGES = {299-303}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Alonso-Remy-Schott/97a, AUTHOR = {Alonso, L. and R{\'e}my, J.L. and Schott, R.}, TITLE = {Uniform generation of a Schr{\"o}der tree}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {6}, PAGES = {305-308}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Efrat-Schwarzkopf/97, AUTHOR = {Efrat, Alon and Schwarzkopf, Otfried}, TITLE = {Separating and shattering long line segments}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {6}, PAGES = {309-314}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, } @article{Queinnec/97, AUTHOR = {Queinnec, Christian}, TITLE = {Fast and compact dispatching for dynamic object-oriented languages}, JOURNAL = {Inf.~Process.~Lett.}, VOLUME = {64}, NUMBER = {6}, PAGES = {315-321}, YEAR = {1997}, PUBLISHER = {Elsevier Science Publishers B.V. (North Holland)}, ADDRESS = {Amsterdam-Lausanne-New York-Oxford-Shannon-Tokyo}, }