@article{Finkel-McKenzie-Picaronny/04,
AUTHOR = {Finkel, Alain and McKenzie, Pierre and Picaronny, Claudine},
TITLE = {A well-structured framework for analysing Petri net extensions},
JOURNAL = {Inf.~Comput.},
VOLUME = {195},
NUMBER = {1-2},
PAGES = {1-29},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
URL = {http://dx.doi.org/10.1016/j.ic.2004.01.005},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Diekert-Gastin/04,
AUTHOR = {Diekert, Volker and Gastin, Paul},
TITLE = {Local temporal logic is expressively complete for cograph dependence alphabets},
JOURNAL = {Inf.~Comput.},
VOLUME = {195},
NUMBER = {1-2},
PAGES = {30-52},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {temporal logics, mazurkiewicz traces, concurrency},
URL = {http://dx.doi.org/10.1016/j.ic.2004.08.001},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Epstein-van_Stee/04,
AUTHOR = {Epstein, Leah and van Stee, Rob},
TITLE = {Minimizing the maximum starting time on-line},
JOURNAL = {Inf.~Comput.},
VOLUME = {195},
NUMBER = {1-2},
PAGES = {53-65},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
URL = {http://dx.doi.org/10.1016/j.ic.2004.09.001},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Luttik-Rodenburg-Verma/04,
AUTHOR = {Luttik, Bas and Rodenburg, Piet and Verma, Rakesh},
TITLE = {Remarks on Thatte's transformation of term rewriting systems},
JOURNAL = {Inf.~Comput.},
VOLUME = {195},
NUMBER = {1-2},
PAGES = {66-87},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {term rewriting, thatte's transformation, constructor-based system},
URL = {http://dx.doi.org/10.1016/j.ic.2003.09.006},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Bustan-Grumberg/04,
AUTHOR = {Bustan, Doron and Grumberg, Orna},
TITLE = {Applicability of fair simulation},
JOURNAL = {Inf.~Comput.},
VOLUME = {194},
NUMBER = {1},
PAGES = {1-18},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {fair simulation, minimization, branching time logics, preorder, assume-guarantee},
URL = {http://dx.doi.org/10.1016/j.ic.2004.02.005},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Okhotin/04,
AUTHOR = {Okhotin, Alexander},
TITLE = {Boolean grammars},
JOURNAL = {Inf.~Comput.},
VOLUME = {194},
NUMBER = {1},
PAGES = {19-48},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {context-free grammar, intersection, complement, language equation, parsing, conjunctive grammar, trellis automaton, cellular automaton},
URL = {http://dx.doi.org/10.1016/j.ic.2004.03.006},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Duris-Hromkovic-Jukna-Sauerhoff-Schnitger/04,
AUTHOR = {{\v{D}}uri{\v{s}}, Pavol and Hromkovi{\v{c}}, Juraj and Jukna, Stasys and Sauerhoff, Martin and Schnitger, Georg},
TITLE = {On multi-partition communication complexity},
JOURNAL = {Inf.~Comput.},
VOLUME = {194},
NUMBER = {1},
PAGES = {49-75},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {computational complexity, multi-partition communication complexity, non-obliviousness, lower bounds, complexity hierarchy, read-once branching programs},
URL = {http://dx.doi.org/10.1016/j.ic.2004.05.002},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Grahne-Kiricenko/04,
AUTHOR = {Grahne, G{\"o}sta and Kiricenko, Victoria},
TITLE = {Towards an algebraic theory of information integration},
JOURNAL = {Inf.~Comput.},
VOLUME = {194},
NUMBER = {2},
PAGES = {79-100},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {information integration, incomplete information, query rewriting},
URL = {http://dx.doi.org/10.1016/j.ic.2004.07.003},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Goldin-Smolka-Attie-Sonderegger/04,
AUTHOR = {Goldin, Dina Q. and Smolka, Scott A. and Attie, Paul C. and Sonderegger, Elaine L.},
TITLE = {Turing machines, transition systems, and interaction},
JOURNAL = {Inf.~Comput.},
VOLUME = {194},
NUMBER = {2},
PAGES = {101-128},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {models of interactive computation, persistent turing machine, persistent stream language, interactive transition system, sequential interactive computation},
URL = {http://dx.doi.org/10.1016/j.ic.2004.07.002},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Moller-Smolka-Srba/04,
AUTHOR = {Moller, Faron and Smolka, Scott and Srba, Ji{\v{r}}{\'{\i}}},
TITLE = {On the computational complexity of bisimulation, redux},
JOURNAL = {Inf.~Comput.},
VOLUME = {194},
NUMBER = {2},
PAGES = {129-143},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {one-counter machines, equivalence-checking, model-checking, automata, formal languages, bisimulation equivalence, complexity},
URL = {http://dx.doi.org/10.1016/j.ic.2004.06.003},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Chatterjee-Ma-Majumdar-Zhao-Henzinger-Palsberg/04,
AUTHOR = {Chatterjee, Krishnendu and Ma, Di and Majumdar, Rupak and Zhao, Tian and Henzinger, Thomas A. and Palsberg, Jens},
TITLE = {Stack size analysis for interrupt-driven programs},
JOURNAL = {Inf.~Comput.},
VOLUME = {194},
NUMBER = {2},
PAGES = {144-174},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {program analysis, stack bounds, interrupt programs},
URL = {http://dx.doi.org/10.1016/j.ic.2004.06.001},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Anagnostopoulos-Bent-Upfal-van_Hentenryck/04,
AUTHOR = {Anagnostopoulos, Aris and Bent, Russell and Upfal, Eli and van Hentenryck, Pascal},
TITLE = {A simple and deterministic competitive algorithm for online facility location},
JOURNAL = {Inf.~Comput.},
VOLUME = {194},
NUMBER = {2},
PAGES = {175-202},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {online facility location, stochastic analysis, competitive ratio},
URL = {http://dx.doi.org/10.1016/j.ic.2004.06.002},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Goldin-Millstein-Kutlu/04,
AUTHOR = {Goldin, Dina Q. and Millstein, Todd D. and Kutlu, Ayferi},
TITLE = {Bounded similarity querying for time-series data},
JOURNAL = {Inf.~Comput.},
VOLUME = {194},
NUMBER = {2},
PAGES = {203-241},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {bounded similarity querying, similarity transformation, shift, scale, fingerprint, normalization parameter},
URL = {http://dx.doi.org/10.1016/j.ic.2004.07.001},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Yamagata/04,
AUTHOR = {Yamagata, Yoriyuki},
TITLE = {Strong normalization of the second-order symmetric $\lambda\mu$-calculus},
JOURNAL = {Inf.~Comput.},
VOLUME = {193},
NUMBER = {1},
PAGES = {1-20},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
URL = {http://dx.doi.org/10.1016/j.ic.2004.04.002},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Asperti-Coppola-Martini/04,
AUTHOR = {Asperti, Andrea and Coppola, Paolo and Martini, Simone},
TITLE = {(Optimal) duplication is not elementary recursive},
JOURNAL = {Inf.~Comput.},
VOLUME = {193},
NUMBER = {1},
PAGES = {21-56},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {complexity, elementary affine logic, graph rewriting, optimal reduction},
URL = {http://dx.doi.org/10.1016/j.ic.2004.05.001},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Servedio/04,
AUTHOR = {Servedio, Rocco A.},
TITLE = {On learning monotone DNF under product distributions},
JOURNAL = {Inf.~Comput.},
VOLUME = {193},
NUMBER = {1},
PAGES = {57-74},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {computational learning theory, pac learning, dnf formula, monotone boolean function},
URL = {http://dx.doi.org/10.1016/j.ic.2004.04.003},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Alstrup-Husfeldt-Rauhe/04,
AUTHOR = {Alstrup, Stephen and Husfeldt, Thore and Rauhe, Theis},
TITLE = {Dynamic nested brackets},
JOURNAL = {Inf.~Comput.},
VOLUME = {193},
NUMBER = {2},
PAGES = {75-83},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
URL = {http://dx.doi.org/10.1016/j.ic.2004.04.006},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Bagnara-Gori-Hill-Zaffanella/04,
AUTHOR = {Bagnara, Roberto and Gori, Roberta and Hill, Patricia M. and Zaffanella, Enea},
TITLE = {Finite-tree analysis for constraint logic-based languages},
JOURNAL = {Inf.~Comput.},
VOLUME = {193},
NUMBER = {2},
PAGES = {84-116},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {static analysis, abstract interpretation, rational unification, occurs-check},
URL = {http://dx.doi.org/10.1016/j.ic.2004.04.005},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Badouel-Darondeau/04,
AUTHOR = {Badouel, E. and Darondeau, Ph.},
TITLE = {The synthesis of Petri nets from path-automatic specifications},
JOURNAL = {Inf.~Comput.},
VOLUME = {193},
NUMBER = {2},
PAGES = {117-135},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {specifications, modal transitions, automatic graphs, petri nets, synthesis},
URL = {http://dx.doi.org/10.1016/j.ic.2004.04.004},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Duris/04,
AUTHOR = {{\v{D}}uri{\v{s}}, Pavol},
TITLE = {Multiparty communication complexity and very hard functions},
JOURNAL = {Inf.~Comput.},
VOLUME = {192},
NUMBER = {1},
PAGES = {1-14},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
URL = {http://dx.doi.org/10.1016/j.ic.2004.03.002},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Case-Kinber-Sharma-Stephan/04,
AUTHOR = {Case, John and Kinber, Efim and Sharma, Arun and Stephan, Frank},
TITLE = {On the classification of recursive languages},
JOURNAL = {Inf.~Comput.},
VOLUME = {192},
NUMBER = {1},
PAGES = {15-40},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
URL = {http://dx.doi.org/10.1016/j.ic.2004.03.001},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Cachin/04,
AUTHOR = {Cachin, Christian},
TITLE = {An information-theoretic model for steganography},
JOURNAL = {Inf.~Comput.},
VOLUME = {192},
NUMBER = {1},
PAGES = {41-56},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {information hiding, covert channel, subliminal channel, perfect security, one-time pad, universal data compression},
URL = {http://dx.doi.org/10.1016/j.ic.2004.02.003},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Lecomte-Rigo/04,
AUTHOR = {Lecomte, P. and Rigo, M.},
TITLE = {Real numbers having ultimately periodic representations in abstract numeration systems},
JOURNAL = {Inf.~Comput.},
VOLUME = {192},
NUMBER = {1},
PAGES = {57-83},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {numeration system, regular language, representation of real numbers, ultimately periodic word},
URL = {http://dx.doi.org/10.1016/j.ic.2003.12.006},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Denecker-Marek-Truszczynski/04,
AUTHOR = {Denecker, Marc and Marek, Victor W. and Truszczy{\'n}ski, Miros{\l}aw},
TITLE = {Ultimate approximation and its application in nonmonotonic knowledge representation systems},
JOURNAL = {Inf.~Comput.},
VOLUME = {192},
NUMBER = {1},
PAGES = {84-121},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {knowledge representation, bilattices, approximation},
URL = {http://dx.doi.org/10.1016/j.ic.2004.02.004},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Ellis-Markov/04,
AUTHOR = {Ellis, John and Markov, Minko},
TITLE = {Computing the vertex separation of unicyclic graphs},
JOURNAL = {Inf.~Comput.},
VOLUME = {192},
NUMBER = {2},
PAGES = {123-161},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {algorithms, unicyclic graphs, trees, vertex separation, search number, pathwidth, linear layouts, layout extensibility},
URL = {http://dx.doi.org/10.1016/j.ic.2004.03.005},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Cleve/04,
AUTHOR = {Cleve, Richard},
TITLE = {The query complexity of order-finding},
JOURNAL = {Inf.~Comput.},
VOLUME = {192},
NUMBER = {2},
PAGES = {162-171},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
URL = {http://dx.doi.org/10.1016/j.ic.2004.04.001},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Nederhof-Satta/04,
AUTHOR = {Nederhof, Mark-Jan and Satta, Giorgio},
TITLE = {The language intersection problem for non-recursive context-free grammars},
JOURNAL = {Inf.~Comput.},
VOLUME = {192},
NUMBER = {2},
PAGES = {172-184},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {formal languages, context-free grammars, computational complexity, parsing algorithms},
URL = {http://dx.doi.org/10.1016/j.ic.2004.03.004},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Jain-Kinber-Wiehagen/04,
AUTHOR = {Jain, Sanjay and Kinber, Efim and Wiehagen, Rolf},
TITLE = {Learning all subfunctions of a function},
JOURNAL = {Inf.~Comput.},
VOLUME = {192},
NUMBER = {2},
PAGES = {185-215},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
URL = {http://dx.doi.org/10.1016/j.ic.2004.03.003},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Halpern-Shore/04,
AUTHOR = {Halpern, Joseph Y. and Shore, Richard A.},
TITLE = {Reasoning about common knowledge with infinitely many agents},
JOURNAL = {Inf.~Comput.},
VOLUME = {191},
NUMBER = {1},
PAGES = {1-40},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
URL = {http://dx.doi.org/10.1016/j.ic.2004.01.003},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Compagnoni/04,
AUTHOR = {Compagnoni, Adriana},
TITLE = {Higher-order subtyping and its decidability},
JOURNAL = {Inf.~Comput.},
VOLUME = {191},
NUMBER = {1},
PAGES = {41-103},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {higher-order lambda calculus, higher-order subtyping, intersection types, bounded polymorphism, decidability},
URL = {http://dx.doi.org/10.1016/j.ic.2004.01.001},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Luttgen-Vogler/04,
AUTHOR = {L{\"u}ttgen, Gerald and Vogler, Walter},
TITLE = {Bisimulation on speed: Worst-case efficiency},
JOURNAL = {Inf.~Comput.},
VOLUME = {191},
NUMBER = {2},
PAGES = {105-144},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {asynchronous systems, process algebra, worst-case timing behavior, faster-than relation, bisimulation},
URL = {http://dx.doi.org/10.1016/j.ic.2002.08.001},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Yoshida-Berger-Honda/04,
AUTHOR = {Yoshida, Nobuko and Berger, Martin and Honda, Kohei},
TITLE = {Strong normalisation in the $\pi$-calculus},
JOURNAL = {Inf.~Comput.},
VOLUME = {191},
NUMBER = {2},
PAGES = {145-202},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {concurrency theory, the $\pi$-calculus, strong normalisation, type theory},
URL = {http://dx.doi.org/10.1016/j.ic.2003.08.004},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Aceto-Fokkink-van_Glabbeek-Ingolfsdottir/04,
AUTHOR = {Aceto, Luca and Fokkink, Wan and van Glabbeek, Rob and Ing{\'o}lfsd{\'o}ttir, Anna},
TITLE = {Nested semantics over finite trees are equationally hard},
JOURNAL = {Inf.~Comput.},
VOLUME = {191},
NUMBER = {2},
PAGES = {203-232},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {concurrency, process algebra, bccsp, nested simulation, possible futures, nested trace semantics, equational logic, complete axiomatizations, non-finitely based algebras, hennessy-milner logic},
URL = {http://dx.doi.org/10.1016/j.ic.2004.02.001},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Kobler-Schuler/04,
AUTHOR = {K{\"o}bler, Johannes and Schuler, Rainer},
TITLE = {Average-case intractability vs. worst-case intractability},
JOURNAL = {Inf.~Comput.},
VOLUME = {190},
NUMBER = {1},
PAGES = {1-17},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
URL = {http://dx.doi.org/10.1016/j.ic.2003.05.002},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Kleijn-Koutny/04,
AUTHOR = {Kleijn, H.C.M. and Koutny, M.},
TITLE = {Process semantics of general inhibitor nets},
JOURNAL = {Inf.~Comput.},
VOLUME = {190},
NUMBER = {1},
PAGES = {18-69},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {theory of concurrency, petri nets, weighted inhibitor arcs, causality semantics, processes, occurrence nets, step sequences},
URL = {http://dx.doi.org/10.1016/j.ic.2003.11.002},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Honkala/04,
AUTHOR = {Honkala, Juha},
TITLE = {Bounds for the DOL language equivalence problem},
JOURNAL = {Inf.~Comput.},
VOLUME = {190},
NUMBER = {1},
PAGES = {70-80},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {DOL systems, equivalence problem, decidability},
URL = {http://dx.doi.org/10.1016/j.ic.2003.12.002},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Jain-Menzel-Stephan/04,
AUTHOR = {Jain, Sanjay and Menzel, Wolfram and Stephan, Frank},
TITLE = {Classes with easily learnable subclasses},
JOURNAL = {Inf.~Comput.},
VOLUME = {190},
NUMBER = {1},
PAGES = {81-99},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
URL = {http://dx.doi.org/10.1016/j.ic.2003.12.004},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Amir-Church-Dar/04,
AUTHOR = {Amir, Amihood and Church, Kenneth W. and Dar, Emanuel},
TITLE = {The submatrices character count problem: An efficient solution using separable values},
JOURNAL = {Inf.~Comput.},
VOLUME = {190},
NUMBER = {1},
PAGES = {100-116},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
URL = {http://dx.doi.org/10.1016/j.ic.2003.12.001},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Attiya-Shachnai/04,
AUTHOR = {Attiya, Hagit and Shachnai, Hadas},
TITLE = {Tight bounds for FEC-based reliable multicast},
JOURNAL = {Inf.~Comput.},
VOLUME = {190},
NUMBER = {2},
PAGES = {117-135},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {reliable multicast, error-correcting codes, randomized distributed algorithms, lower bounds},
URL = {http://dx.doi.org/10.1016/j.ic.2003.12.005},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Cattani-Sewell/04,
AUTHOR = {Cattani, Gian Luca and Sewell, Peter},
TITLE = {Models for name-passing processes: Interleaving and causal},
JOURNAL = {Inf.~Comput.},
VOLUME = {190},
NUMBER = {2},
PAGES = {136-178},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {concurrency and distributed computation, $\pi$-calculus, semantics, categorical models},
URL = {http://dx.doi.org/10.1016/j.ic.2003.12.003},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Qiu/04,
AUTHOR = {Qiu, Daowen},
TITLE = {Automata theory based on quantum logic: Some characterizations},
JOURNAL = {Inf.~Comput.},
VOLUME = {190},
NUMBER = {2},
PAGES = {179-195},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
URL = {http://dx.doi.org/10.1016/j.ic.2003.11.003},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Vorobyov/04,
AUTHOR = {Vorobyov, Sergei},
TITLE = {The most nonelementary theory},
JOURNAL = {Inf.~Comput.},
VOLUME = {190},
NUMBER = {2},
PAGES = {196-219},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {lower complexity bound, nonelementary theory, generic reduction, reduction via length order, inductive definition},
URL = {http://dx.doi.org/10.1016/j.ic.2004.02.002},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Creignou-Daude/04,
AUTHOR = {Creignou, Nadia and Daud{\'e}, Herv{\'e}},
TITLE = {Combinatorial sharpness criterion and phase transition classification for Random CSPs},
JOURNAL = {Inf.~Comput.},
VOLUME = {190},
NUMBER = {2},
PAGES = {220-238},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {constraint satisfaction problems, phase transition classification, sharp thresholds, coarse thresholds},
URL = {http://dx.doi.org/10.1016/j.ic.2004.01.002},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Dyer-Goldberg-Jerrum/04,
AUTHOR = {Dyer, Martin and Goldberg, Leslie Ann and Jerrum, Mark},
TITLE = {Counting and sampling $H$-colourings},
JOURNAL = {Inf.~Comput.},
VOLUME = {189},
NUMBER = {1},
PAGES = {1-16},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
URL = {http://dx.doi.org/10.1016/j.ic.2003.09.001},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Lengrand-Lescanne-Dougherty-Dezani-Ciancaglini-van_Bakel/04,
AUTHOR = {Lengrand, St{\'{e}}phane and Lescanne, Pierre and Dougherty, Dan and Dezani-Ciancaglini, Mariangiola and van Bakel, Steffen},
TITLE = {Intersection types for explicit substitutions},
JOURNAL = {Inf.~Comput.},
VOLUME = {189},
NUMBER = {1},
PAGES = {17-42},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {calculi of explicit substitutions, intersection types, strong normalization},
URL = {http://dx.doi.org/10.1016/j.ic.2003.09.004},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Kenyon-Kutin/04,
AUTHOR = {Kenyon, Claire and Kutin, Samuel},
TITLE = {Sensitivity, block sensitivity, and $l$-block sensitivity of Boolean functions},
JOURNAL = {Inf.~Comput.},
VOLUME = {189},
NUMBER = {1},
PAGES = {43-53},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
URL = {http://dx.doi.org/10.1016/j.ic.2002.12.001},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Palsberg-Zhao/04,
AUTHOR = {Palsberg, Jens and Zhao, Tian},
TITLE = {Type inference for record concatenation and subtyping},
JOURNAL = {Inf.~Comput.},
VOLUME = {189},
NUMBER = {1},
PAGES = {54-86},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {types, objects, complexity},
URL = {http://dx.doi.org/10.1016/j.ic.2003.10.001},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Paolini-Ronchi_Della_Rocca/04,
AUTHOR = {Paolini, Luca and Ronchi Della Rocca, Simona},
TITLE = {Parametric parameter passing $\lambda$-calculus},
JOURNAL = {Inf.~Comput.},
VOLUME = {189},
NUMBER = {1},
PAGES = {87-106},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {$\lambda$-calculus, confluence, standardization},
URL = {http://dx.doi.org/10.1016/j.ic.2003.08.003},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Fischer/04,
AUTHOR = {Fischer, Eldar},
TITLE = {On the strength of comparisons in property testing},
JOURNAL = {Inf.~Comput.},
VOLUME = {189},
NUMBER = {1},
PAGES = {107-116},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {property testing, monotonicity, ramsey's theorem},
URL = {http://dx.doi.org/10.1016/j.ic.2003.09.003},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Allender-Mahajan/04,
AUTHOR = {Allender, Eric and Mahajan, Meena},
TITLE = {The complexity of planarity testing},
JOURNAL = {Inf.~Comput.},
VOLUME = {189},
NUMBER = {1},
PAGES = {117-134},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {planar graphs, symmetric logspace  pacs},
URL = {http://dx.doi.org/10.1016/j.ic.2003.09.002},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Ergun-Kumar-Rubinfeld/04,
AUTHOR = {Erg{\"{u}}n, Funda and Kumar, Ravi and Rubinfeld, Ronitt},
TITLE = {Fast approximate probabilistically checkable proofs},
JOURNAL = {Inf.~Comput.},
VOLUME = {189},
NUMBER = {2},
PAGES = {135-159},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {property testing, proof-assisted property testing, probabilistically checkable proofs, sub-linear time algorithms, optimization problems},
URL = {http://dx.doi.org/10.1016/j.ic.2003.09.005},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Lohrey-Muscholl/04,
AUTHOR = {Lohrey, Markus and Muscholl, Anca},
TITLE = {Bounded MSC communication},
JOURNAL = {Inf.~Comput.},
VOLUME = {189},
NUMBER = {2},
PAGES = {160-181},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {message sequence charts, channel boundedness, computational commplexity},
URL = {http://dx.doi.org/10.1016/j.ic.2003.10.002},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Atserias-Bonet/04,
AUTHOR = {Atserias, Albert and Bonet, Mar{\'{\i}}a Luisa},
TITLE = {On the automatizability of resolution and related propositional proof systems},
JOURNAL = {Inf.~Comput.},
VOLUME = {189},
NUMBER = {2},
PAGES = {182-201},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {propositional proof complexity, feasible interpolation, automatizability, reflection principles, resolution, res(2)},
URL = {http://dx.doi.org/10.1016/j.ic.2003.10.004},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Mellies/04,
AUTHOR = {Melli{\`{e}}s, Paul-Andr{\'{e}}},
TITLE = {Comparing hierarchies of types in models of linear logic},
JOURNAL = {Inf.~Comput.},
VOLUME = {189},
NUMBER = {2},
PAGES = {202-234},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
URL = {http://dx.doi.org/10.1016/j.ic.2003.10.003},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Sharma-Stephan-Ventsov/04,
AUTHOR = {Sharma, Arun and Stephan, Frank and Ventsov, Yuri},
TITLE = {Generalized notions of mind change complexity},
JOURNAL = {Inf.~Comput.},
VOLUME = {189},
NUMBER = {2},
PAGES = {235-262},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {inductive inference, learning in the limit, mind change bounds, complexity of learning},
URL = {http://dx.doi.org/10.1016/j.ic.2003.11.001},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Jancar-Kucera-Moller-Sawa/04,
AUTHOR = {Jan{\v{c}}ar, Petr and Ku{\v{c}}era, Anton{\'{\i}}n and Moller, Faron and Sawa, Zden{\'e}k},
TITLE = {$DP$ lower bounds for equivalence-checking and model-checking of one-counter automata},
JOURNAL = {Inf.~Comput.},
VOLUME = {188},
NUMBER = {1},
PAGES = {1-19},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {one-counter machines, equivalence-checking, model-checking},
URL = {http://dx.doi.org/10.1016/S0890-5401(03)00171-8},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Cole-Galil-Hariharan-Muthukrishnan-Park/04,
AUTHOR = {Cole, Richard and Galil, Zvi and Hariharan, Ramesh and Muthukrishnan, S. and Park, Kunsoo},
TITLE = {Parallel two dimensional witness computation},
JOURNAL = {Inf.~Comput.},
VOLUME = {188},
NUMBER = {1},
PAGES = {20-67},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
URL = {http://dx.doi.org/10.1016/S0890-5401(03)00162-7},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{van_Breugel/04,
AUTHOR = {van Breugel, Franck},
TITLE = {De Bakker-Zucker processes revisited},
JOURNAL = {Inf.~Comput.},
VOLUME = {188},
NUMBER = {1},
PAGES = {68-76},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {terminal coalgebra, metric space, closed subset, compact subset, hausdorff metric, de bakker-zucker process},
URL = {http://dx.doi.org/10.1016/j.ic.2001.03.001},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Kang-Hong-Whang-Cho/04,
AUTHOR = {Kang, Ji-Hoon and Hong, Ki-Hyung and Whang, Kyu-Young and Cho, Jung-Wan},
TITLE = {Generalization of ZYT-linearizability for bilinear Datalog programs},
JOURNAL = {Inf.~Comput.},
VOLUME = {188},
NUMBER = {1},
PAGES = {77-98},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {deductive databases, datalog programs, bilinear rules, linearizability},
URL = {http://dx.doi.org/10.1016/S0890-5401(03)00172-X},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Long/04,
AUTHOR = {Long, Philip M.},
TITLE = {Efficient algorithms for learning functions with bounded variation},
JOURNAL = {Inf.~Comput.},
VOLUME = {188},
NUMBER = {1},
PAGES = {99-115},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {statistical learning theory, computational learning theory, sample complexity, bounded variation, nonparametric regression},
URL = {http://dx.doi.org/10.1016/S0890-5401(03)00164-0},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Pavan-Selman/04,
AUTHOR = {Pavan, A. and Selman, Alan L.},
TITLE = {Bi-immunity separates strong $NP$-completeness notions},
JOURNAL = {Inf.~Comput.},
VOLUME = {188},
NUMBER = {1},
PAGES = {116-126},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {turing completeness, many-one completeness, bi-immunity},
URL = {http://dx.doi.org/10.1016/j.ic.2003.05.001},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Jain-Stephan-Terwijn/04,
AUTHOR = {Jain, Sanjay and Stephan, Frank and Terwijn, Sebastiaan A.},
TITLE = {Counting extensional differences in $BC$-learning},
JOURNAL = {Inf.~Comput.},
VOLUME = {188},
NUMBER = {1},
PAGES = {127-142},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {models of grammar induction, inductive inference, behaviourally correct learning},
URL = {http://dx.doi.org/10.1016/S0890-5401(03)00174-3},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Schmidt-Schauss/04,
AUTHOR = {Schmidt-Schau{\ss}, Manfred},
TITLE = {Decidability of bounded second order unification},
JOURNAL = {Inf.~Comput.},
VOLUME = {188},
NUMBER = {2},
PAGES = {143-178},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {unification, second order unification, lambda calculus, context unification, automated deduction, rewriting, higher-order unification, logics in artificial intelligence},
URL = {http://dx.doi.org/10.1016/j.ic.2003.08.002},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Levi-Maffeis/04,
AUTHOR = {Levi, Francesca and Maffeis, Sergio},
TITLE = {On abstract interpretation of mobile ambients},
JOURNAL = {Inf.~Comput.},
VOLUME = {188},
NUMBER = {2},
PAGES = {179-240},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {mobile ambients, static analysis, abstract interpretation},
URL = {http://dx.doi.org/10.1016/j.ic.2003.06.001},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}
@article{Fuhrmann-Thielecke/04,
AUTHOR = {F{\"{u}}hrmann, Carsten and Thielecke, Hayo},
TITLE = {On the call-by-value CPS transform and its semantics},
JOURNAL = {Inf.~Comput.},
VOLUME = {188},
NUMBER = {2},
PAGES = {241-283},
YEAR = {2004},
EDITOR = {Meyer, Albert R.},
KEYWORDS = {continuations, lambda-calculus, semantics, categories, monads},
URL = {http://dx.doi.org/10.1016/j.ic.2003.08.001},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Orlando-Amsterdam-Tokyo-Singapore},
}