@article{Damaschke/89,
AUTHOR = {Damaschke, Peter},
TITLE = {The Hamiltonian circuit problem for circle graphs is $NP$-complete},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {1-2},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Sarkar-Stojmenovic/89,
AUTHOR = {Sarkar, Dilip and Stojmenovi{\'c}, Ivan},
TITLE = {An optimal parallel circle-cover algorithm},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {3-6},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Gunther/89,
AUTHOR = {Gunther, Neil},
TITLE = {Path integral methods for computer performance analysis},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {7-13},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Matousek/89,
AUTHOR = {Matou{\v{s}}ek, Ji{\v{r}}i},
TITLE = {On-line computation of convolutions},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {15-16},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Sistla/89,
AUTHOR = {Sistla, A.P.},
TITLE = {On verifying that a concurrent program satisfies a nondeterministic specification},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {17-23},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Iwano/89,
AUTHOR = {Iwano, Kazuo},
TITLE = {An improvement of Goldberg, Plotkin and Vaidya's maximal node-disjoint paths algorithm},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {25-27},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Biskup/89,
AUTHOR = {Biskup, Joachim},
TITLE = {Boyce-Codd normal form and object normal forms},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {29-33},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Hagerup/89,
AUTHOR = {Hagerup, Torben},
TITLE = {Hybridsort revisited and parallelized},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {35-39},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Blass-Gurevich/89,
AUTHOR = {Blass, Andreas and Gurevich, Yuri},
TITLE = {On Matijasevich's nontraditional approach to search problems},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {41-45},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Lloyd/89,
AUTHOR = {Lloyd, Errol L.},
TITLE = {A fast algorithm for finding interlocking sets},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {47-50},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Choi-Kim/89,
AUTHOR = {Choi, Hwang Kyu and Kim, Myunghwan},
TITLE = {Hybrid join: An improved sort-based join algorithm},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {51-56},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Boxer-Miller/89,
AUTHOR = {Boxer, Laurence and Miller, Russ},
TITLE = {A parallel circle-cover minimization algorithm},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {57-60},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Chern-Chen-Liu/89,
AUTHOR = {Chern, Maw-Sheng and Chen, G.H. and Liu, P.},
TITLE = {An LC branch-and-bound algorithm for the module assignment problem},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {61-71},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Kim-Kim/89,
AUTHOR = {Kim, Young Joo and Kim, Gil Chang},
TITLE = {Coordinator: A modification to the monitor concept},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {73-80},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Feitelson-Rudolph/89,
AUTHOR = {Feitelson, Dror G. and Rudolph, Larry},
TITLE = {Implementation of a wait-free synchronization primitive that solves $n$-process consensus},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {81-83},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Wolfram/89,
AUTHOR = {Wolfram, D.A.},
TITLE = {Forward checking and intelligent backtracking},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {85-87},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Chen-Yeh-Chen/89,
AUTHOR = {Chen, Y.C. and Yeh, Z.C. and Chen, G.H.},
TITLE = {Using fewer processors to reduce time complexities of semigroup computations},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {89-93},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Laih-Lee-Harn/89,
AUTHOR = {Laih, Chi Sung and Lee, Jau Yien and Harn, Lein},
TITLE = {A new threshold scheme and its application in designing the conference key distribution cryptosystem},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {95-99},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Janiak/89,
AUTHOR = {Janiak, Adam},
TITLE = {Minimization of resource consumption under a given deadline in the two-processor flow-shop scheduling problem},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {101-112},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Huang/89a,
AUTHOR = {Huang, Shing-Tsaan},
TITLE = {Termination detection by using distributed snapshots},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {113-119},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Kochol/89,
AUTHOR = {Kochol, Martin},
TITLE = {Efficient monotone circuits for threshold functions},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {121-122},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Skiena/89a,
AUTHOR = {Skiena, Steven S.},
TITLE = {Reconstructing graphs from cut-set sizes},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {123-127},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Goscinski/89,
AUTHOR = {Goscinski, A.},
TITLE = {A synchronization algorithm for processes with dynamic priorities in computer networks with node failures},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {129-136},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Richardson-Ganapathi/89,
AUTHOR = {Richardson, Stephen and Ganapathi, Mahadevan},
TITLE = {Interprocedural analysis vs. procedure integration},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {137-142},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Cull-Holloway/89,
AUTHOR = {Cull, Paul and Holloway, James L.},
TITLE = {Computing Fibonacci numbers quickly},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {143-149},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Sagar-Sarje-Ahmed/89,
AUTHOR = {Sagar, G. and Sarje, Anil K. and Ahmed, Kamal U.},
TITLE = {On module assignment in two-processor distributed systems: a modified algorithm},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {151-153},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Morris/89,
AUTHOR = {Morris, Joseph M.},
TITLE = {Well-founded induction and the invariance theorem for loops},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {155-158},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Atallah-Chen/89,
AUTHOR = {Atallah, Mikhail J. and Chen, Danny Z.},
TITLE = {An optimal parallel algorithm for the minimum circle-cover problem},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {159-165},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Narasimhan/89,
AUTHOR = {Narasimhan, Giri},
TITLE = {A note on the Hamiltonian circuit problem on directed path graphs},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {167-170},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Bern-Plassmann/89,
AUTHOR = {Bern, Marshall and Plassmann, Paul},
TITLE = {The Steiner problem with edge lengths 1 and 2},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {171-176},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Ligozat-Bestougeff/89,
AUTHOR = {Ligozat, G{\'e}rard and Bestougeff, H{\'e}l{\`e}ne},
TITLE = {On relations between intervals},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {177-182},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Sharma-Iyengar-Mandyam/89,
AUTHOR = {Sharma, Mohan B. and Iyengar, Sitharama S. and Mandyam, Narasimha K.},
TITLE = {An efficient distributed depth-first-search algorithm},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {183-186},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
NOTE = {see Corrigendum in Inf.~Process.~Lett.~35, 55-56},
}
@article{Sharir/89,
AUTHOR = {Sharir, Micha},
TITLE = {A note on the Papadimitriou-Silverberg algorithm for planning optimal piecewise-linear motion of a ladder},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {187-190},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Lingas/89a,
AUTHOR = {Lingas, Andrzej},
TITLE = {Voronoi diagrams with barriers and the shortest diagonal problem},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {191-198},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Ellis-Mata-MacGillivray/89,
AUTHOR = {Ellis, John A. and Mata, Manrique and MacGillivray, Gary},
TITLE = {A linear time algorithm for longest $(s, t)$-paths in weighted outerplanar graphs},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {199-204},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Egecioglu-Kalantari/89,
AUTHOR = {E{\~g}ecio{\~g}lu, {\"o}mer and Kalantari, Bahman},
TITLE = {Approximating the diameter of a set of points in the Euclidean space},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {205-211},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Sandhu/89a,
AUTHOR = {Sandhu, Ravinderpal Singh},
TITLE = {The demand operation in the schematic protection model},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {213-219},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{van_den_Bos/89,
AUTHOR = {van den Bos, Jan},
TITLE = {PROCOL: A protocol-constrained concurrent object-oriented language},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {221-227},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Kemp/89,
AUTHOR = {Kemp, R.},
TITLE = {A one-to-one correspondence between two classes of ordered trees},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {229-234},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Francez/89,
AUTHOR = {Francez, Nissim},
TITLE = {Cooperating proofs for distributed programs with multiparty interactions},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {235-242},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
NOTE = {see Corrigendum in Inf.~Process.~Lett.~34, 57 and Inf.~Process.~Lett.~35, 275},
}
@article{Everett-Gupta/89,
AUTHOR = {Everett, H. and Gupta, A.},
TITLE = {Acyclic directed hypercubes may have exponential diameter},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {243-245},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Cheston-Farley-Hedetniemi-Proskurowski/89,
AUTHOR = {Cheston, Grant A. and Farley, Art and Hedetniemi, S.T. and Proskurowski, Andrzej},
TITLE = {Centering a spanning tree of a biconnected graph},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {247-250},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Barrington-Corbett/89,
AUTHOR = {Barrington, David A. Mix and Corbett, James},
TITLE = {On the relative complexity of some languages in $NC^1$},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {251-256},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Clouatre-Laliberte-Merrett/89,
AUTHOR = {Clou{\^a}tre, A. and Laliberte, N. and Merrett, T.H.},
TITLE = {A general implementation of relational recursion with speedup techniques for programmers},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {257-262},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Roberts/89,
AUTHOR = {Roberts, George H.},
TITLE = {Another note on recursive ascent},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {263-266},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Baron-Urbanek/89,
AUTHOR = {Baron, Gerd and Urbanek, Friedrich},
TITLE = {Factorial languages with quadratically upper bounded growth functions and nonlinearly upper bounded subword complexities},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {267-269},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Makinen/89,
AUTHOR = {M{\"a}kinen, Erkki},
TITLE = {On the subtree isomorphism problem for ordered trees},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {271-273},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Shiraishi/89,
AUTHOR = {Shiraishi, Shuji},
TITLE = {A parallel algorithm for the maximum 2-chain edge packing problem},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {277-279},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Abiteboul/89,
AUTHOR = {Abiteboul, Serge},
TITLE = {Boundedness is undecidable for Datalog programs with a single recursive rule},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {281-287},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Alblas/89a,
AUTHOR = {Alblas, Henk},
TITLE = {Optimal incremental simple multi-pass attribute evaluation},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {289-295},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Padberg-Sassano/89,
AUTHOR = {Padberg, Manfred and Sassano, Antonio},
TITLE = {The complexity of matching with bonds},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {297-300},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Drysdale-Jaromczyk/89,
AUTHOR = {Drysdale III, Robert L. (Scot) and Jaromczyk, Jerzy W.},
TITLE = {A note on lower bounds for the maximum area and maximum perimeter $k$-gon problems},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {301-303},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Gibbons-Srikant/89,
AUTHOR = {Gibbons, A.M. and Srikant, Y.N.},
TITLE = {A class of problems efficiently solvable on mesh-connected computers including dynamic expression evaluation},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {305-311},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Demolombe-Illarramendi/89,
AUTHOR = {Demolombe, Robert and Illarramendi, Arantza},
TITLE = {Heuristics for syntactical optimization of relational queries},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {313-316},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Abiteboul-Gyssens-Gucht/89,
AUTHOR = {Abiteboul, Serge and Gyssens, Marc and Gucht, Dirk van},
TITLE = {An alternative way to represent the cogroup of a relation in the context of nested databases},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {317-324},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}
@article{Toyama/89,
AUTHOR = {Toyama, Yoshihito},
TITLE = {Fast Knuth-Bendix completion with a term rewriting system compiler},
JOURNAL = {Inf.~Process.~Lett.},
VOLUME = {32},
PAGES = {325-328},
YEAR = {1989},
PUBLISHER = {North-Holland Publishing Company},
ADDRESS = {Amsterdam-New York-Oxford-Tokyo},
}