@article{Baier-Hermanns-Katoen-Haverkort/05,
AUTHOR = {Baier, Christel and Hermanns, Holger and Katoen, Joost-Pieter and Haverkort, Boudewijn R.},
TITLE = {Efficient computation of time-bounded reachability probabilities in uniform continuous-time Markov decision processes},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {345},
NUMBER = {1},
PAGES = {2-26},
YEAR = {2005},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {continuous-time, markov decision process, temporal logic, model checking, time-bounded reachability},
URL = {http://dx.doi.org/10.1016/j.tcs.2005.07.022},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Boston-Jena-London-New York-Oxford-Paris-Philadelphia-San Diego-St. Louis},
}
@article{Lugiez-Niebert-Zennou/05,
AUTHOR = {Lugiez, D. and Niebert, P. and Zennou, S.},
TITLE = {A partial order semantics approach to the clock explosion problem of timed automata},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {345},
NUMBER = {1},
PAGES = {27-59},
YEAR = {2005},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {algorithms, verification, timed automata, partial order},
URL = {http://dx.doi.org/10.1016/j.tcs.2005.07.023},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Boston-Jena-London-New York-Oxford-Paris-Philadelphia-San Diego-St. Louis},
}
@article{Geldenhuys-Valmari/05,
AUTHOR = {Geldenhuys, Jaco and Valmari, Antti},
TITLE = {More efficient on-the-fly LTL verification with Tarjan's algorithm},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {345},
NUMBER = {1},
PAGES = {60-82},
YEAR = {2005},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {model checking, verification},
URL = {http://dx.doi.org/10.1016/j.tcs.2005.07.004},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Boston-Jena-London-New York-Oxford-Paris-Philadelphia-San Diego-St. Louis},
}
@article{Kupferman-Vardi/05,
AUTHOR = {Kupferman, Orna and Vardi, Moshe Y.},
TITLE = {From complementation to certification},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {345},
NUMBER = {1},
PAGES = {83-100},
YEAR = {2005},
EDITOR = {Ausiello, G. and Sannella, D.},
URL = {http://dx.doi.org/10.1016/j.tcs.2005.07.021},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Boston-Jena-London-New York-Oxford-Paris-Philadelphia-San Diego-St. Louis},
}
@article{McMillan/05a,
AUTHOR = {McMillan, K.L.},
TITLE = {An interpolating theorem prover},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {345},
NUMBER = {1},
PAGES = {101-121},
YEAR = {2005},
EDITOR = {Ausiello, G. and Sannella, D.},
URL = {http://dx.doi.org/10.1016/j.tcs.2005.07.003},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Boston-Jena-London-New York-Oxford-Paris-Philadelphia-San Diego-St. Louis},
}
@article{Su-Wagner/05,
AUTHOR = {Su, Zhendong and Wagner, David},
TITLE = {A class of polynomially solvable range constraints for interval analysis without widenings},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {345},
NUMBER = {1},
PAGES = {122-138},
YEAR = {2005},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {range constraints, interval analysis, algorithms, complexity},
URL = {http://dx.doi.org/10.1016/j.tcs.2005.07.035},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Boston-Jena-London-New York-Oxford-Paris-Philadelphia-San Diego-St. Louis},
}
@article{de_Alfaro-Faella-Henzinger-Majumdar-Stoelinga/05,
AUTHOR = {de Alfaro, Luca and Faella, Marco and Henzinger, Thomas A. and Majumdar, Rupak and Stoelinga, Mari{\"e}lle},
TITLE = {Model checking discounted temporal properties},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {345},
NUMBER = {1},
PAGES = {139-170},
YEAR = {2005},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {logic, model checking, quantitative systems, discounting, CTL},
URL = {http://dx.doi.org/10.1016/j.tcs.2005.07.033},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Boston-Jena-London-New York-Oxford-Paris-Philadelphia-San Diego-St. Louis},
}
@article{Bab-Nickelsen/05,
AUTHOR = {Bab, Sebastian and Nickelsen, Arfst},
TITLE = {One query reducibilities between partial information classes},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {345},
NUMBER = {2-3},
PAGES = {173-189},
YEAR = {2005},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {partial information, one qvery reduction cheatable, p-selective, membership comparable, easily countable},
URL = {http://dx.doi.org/10.1016/j.tcs.2005.07.006},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Boston-Jena-London-New York-Oxford-Paris-Philadelphia-San Diego-St. Louis},
}
@article{Beal-Fiorenzi-Perrin/05,
AUTHOR = {B{\'e}al, Marie-Pierre and Fiorenzi, Francesca and Perrin, Dominique},
TITLE = {A hierarchy of shift equivalent sofic shifts},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {345},
NUMBER = {2-3},
PAGES = {190-205},
YEAR = {2005},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {automata and formal languages, symbolic dynamics},
URL = {http://dx.doi.org/10.1016/j.tcs.2005.07.007},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Boston-Jena-London-New York-Oxford-Paris-Philadelphia-San Diego-St. Louis},
}
@article{Beaudry-Fernandez-Holzer/05,
AUTHOR = {Beaudry, Martin and Fernandez, Jos{\'e} M. and Holzer, Markus},
TITLE = {A common algebraic description for probabilistic and quantum computations},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {345},
NUMBER = {2-3},
PAGES = {206-234},
YEAR = {2005},
EDITOR = {Ausiello, G. and Sannella, D.},
URL = {http://dx.doi.org/10.1016/j.tcs.2005.07.008},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Boston-Jena-London-New York-Oxford-Paris-Philadelphia-San Diego-St. Louis},
}
@article{Bernardi-Durand-Formenti-Kari/05,
AUTHOR = {Bernardi, Vincent and Durand, Bruno and Formenti, Enrico and Kari, Jarkko},
TITLE = {A new dimension sensitive property for cellular automata},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {345},
NUMBER = {2-3},
PAGES = {235-247},
YEAR = {2005},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {number-conserving cellular automata, undecidability, number-decreasing cellular automata},
URL = {http://dx.doi.org/10.1016/j.tcs.2005.07.009},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Boston-Jena-London-New York-Oxford-Paris-Philadelphia-San Diego-St. Louis},
}
@article{Beygelzimer-Ogihara/05,
AUTHOR = {Beygelzimer, Alina and Ogihara, Mitsunori},
TITLE = {The enumerability of $P$ collapses $P$ to $NC$},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {345},
NUMBER = {2-3},
PAGES = {248-259},
YEAR = {2005},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {complexity theory, circuit value problem, enumerative approximations},
URL = {http://dx.doi.org/10.1016/j.tcs.2005.07.010},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Boston-Jena-London-New York-Oxford-Paris-Philadelphia-San Diego-St. Louis},
}
@article{Bohler-Glasser-Schwarz-Wagner/05,
AUTHOR = {B{\"o}hler, E. and Gla{\ss}er, C. and Schwarz, B. and Wagner, K.W.},
TITLE = {Generation problems},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {345},
NUMBER = {2-3},
PAGES = {260-295},
YEAR = {2005},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {computational complexity, closures, polynomials, sos problem},
URL = {http://dx.doi.org/10.1016/j.tcs.2005.07.011},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Boston-Jena-London-New York-Oxford-Paris-Philadelphia-San Diego-St. Louis},
}
@article{Czeizler/05,
AUTHOR = {Czeizler, Elena},
TITLE = {The non-parametrizability of the word equation $xyz=zvx$: A short proof},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {345},
NUMBER = {2-3},
PAGES = {296-303},
YEAR = {2005},
EDITOR = {Ausiello, G. and Sannella, D.},
URL = {http://dx.doi.org/10.1016/j.tcs.2005.07.012},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Boston-Jena-London-New York-Oxford-Paris-Philadelphia-San Diego-St. Louis},
}
@article{Domaratzki-Salomaa/05a,
AUTHOR = {Domaratzki, Michael and Salomaa, Kai},
TITLE = {Decidability of trajectory-based equations},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {345},
NUMBER = {2-3},
PAGES = {304-330},
YEAR = {2005},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {shuffle on trajectories, deletion along trajectories, language equations, shuffle decompositions},
URL = {http://dx.doi.org/10.1016/j.tcs.2005.07.013},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Boston-Jena-London-New York-Oxford-Paris-Philadelphia-San Diego-St. Louis},
}
@article{Fraigniaud-Ilcinkas-Peer-Pelc-Peleg/05,
AUTHOR = {Fraigniaud, Pierre and Ilcinkas, David and Peer, Guy and Pelc, Andrzej and Peleg, David},
TITLE = {Graph exploration by a finite automaton},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {345},
NUMBER = {2-3},
PAGES = {331-344},
YEAR = {2005},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {graph exploration, labyrinth, finite automaton, mobile agent, robot},
URL = {http://dx.doi.org/10.1016/j.tcs.2005.07.014},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Boston-Jena-London-New York-Oxford-Paris-Philadelphia-San Diego-St. Louis},
}
@article{Hemaspaandra-Hemaspaandra-Hempel/05a,
AUTHOR = {Hemaspaandra, Edith and Hemaspaandra, Lane A. and Hempel, Harald},
TITLE = {All superlinear inverse schemes are co$NP$-hard},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {345},
NUMBER = {2-3},
PAGES = {345-358},
YEAR = {2005},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {inverse problems, certificates, co$NP$-hardness, $NP$, $P$-producible sets, complexity theory},
URL = {http://dx.doi.org/10.1016/j.tcs.2005.07.015},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Boston-Jena-London-New York-Oxford-Paris-Philadelphia-San Diego-St. Louis},
}
@article{Ilie-Ochem-Shallit/05,
AUTHOR = {Ilie, Lucian and Ochem, Pascal and Shallit, Jeffrey},
TITLE = {A generalization of repetition threshold},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {345},
NUMBER = {2-3},
PAGES = {359-369},
YEAR = {2005},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {combinatorics on words, repetitions},
URL = {http://dx.doi.org/10.1016/j.tcs.2005.07.016},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Boston-Jena-London-New York-Oxford-Paris-Philadelphia-San Diego-St. Louis},
}
@article{Kawachi-Kobayashi-Koshiba-Putra/05,
AUTHOR = {Kawachi, Akinori and Kobayashi, Hirotada and Koshiba, Takeshi and Putra, Raymond H.},
TITLE = {Universal test for quantum one-way permutations},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {345},
NUMBER = {2-3},
PAGES = {370-385},
YEAR = {2005},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {quantum computation, computational cryptography, one-way permutation, one-way function, universal test},
URL = {http://dx.doi.org/10.1016/j.tcs.2005.07.036},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Boston-Jena-London-New York-Oxford-Paris-Philadelphia-San Diego-St. Louis},
}
@article{Lee-Romashchenko/05,
AUTHOR = {Lee, Troy and Romashchenko, Andrei},
TITLE = {Resource bounded symmetry of information revisited},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {345},
NUMBER = {2-3},
PAGES = {386-405},
YEAR = {2005},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {kolmogorov complexity, symmetry of information, compression},
URL = {http://dx.doi.org/10.1016/j.tcs.2005.07.017},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Boston-Jena-London-New York-Oxford-Paris-Philadelphia-San Diego-St. Louis},
}
@article{Nordh/05,
AUTHOR = {Nordh, Gustav},
TITLE = {The complexity of equivalence and isomorphism of systems of equations over finite groups},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {345},
NUMBER = {2-3},
PAGES = {406-424},
YEAR = {2005},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {graph isomorphism, computational complexity, systems of equations, finite groups},
URL = {http://dx.doi.org/10.1016/j.tcs.2005.07.018},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Boston-Jena-London-New York-Oxford-Paris-Philadelphia-San Diego-St. Louis},
}
@article{Okhotin/05b,
AUTHOR = {Okhotin, Alexander},
TITLE = {The dual of concatenation},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {345},
NUMBER = {2-3},
PAGES = {425-447},
YEAR = {2005},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {formal languages, semiring, regular expressions, language equations, deductive parsing, co-context-free languages, conjunctive grammars, boolean grammars},
URL = {http://dx.doi.org/10.1016/j.tcs.2005.07.019},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Boston-Jena-London-New York-Oxford-Paris-Philadelphia-San Diego-St. Louis},
}
@article{Selivanov-Wagner/05,
AUTHOR = {Selivanov, Victor L. and Wagner, Klaus W.},
TITLE = {A reducibility for the dot-depth hierarchy},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {345},
NUMBER = {2-3},
PAGES = {448-472},
YEAR = {2005},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {dot-depth hierarchy, reducibility, complete sets, degree structure, leaf languages},
URL = {http://dx.doi.org/10.1016/j.tcs.2005.07.020},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Boston-Jena-London-New York-Oxford-Paris-Philadelphia-San Diego-St. Louis},
}
@article{Wich/05,
AUTHOR = {Wich, Klaus},
TITLE = {Sublogarithmic ambiguity},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {345},
NUMBER = {2-3},
PAGES = {473-504},
YEAR = {2005},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {formal languages, context-free, ambiguity},
URL = {http://dx.doi.org/10.1016/j.tcs.2005.07.024},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-Boston-Jena-London-New York-Oxford-Paris-Philadelphia-San Diego-St. Louis},
}