@incollection{Meyer/95,
AUTHOR = {Meyer, Albert R.},
TITLE = {Concurrent process equivalences: Some decision problems},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {349},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=34},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Thomas/95a,
AUTHOR = {Thomas, Wolfgang},
TITLE = {On the synthesis of strategies in infinite games},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {1-13},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=1},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Louchard/95,
AUTHOR = {Louchard, Guy},
TITLE = {Finding the maximum with linear error probabilities: A sequential analysis approach},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {14-25},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=14},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Juedes-Lutz/95a,
AUTHOR = {Juedes, David W. and Lutz, Jack H.},
TITLE = {Completeness and weak completeness under polynomial-size circuits},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {26-37},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=26},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Cai-Lipton-Longpre-Ogihara-Regan-Sivakumar/95,
AUTHOR = {Cai, Jin-Yi and Lipton, Richard J. and Longpr{\'e}, Luc and Ogihara, Mitsunori and Regan, Kenneth W. and Sivakumar, D.},
TITLE = {Communication complexity of key agreement on small ranges},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {38-49},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=38},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Han-Hemaspaandra/95,
AUTHOR = {Han, Yenjo and Hemaspaandra, Lane A.},
TITLE = {Pseudorandom generators and the frequency of simplicity},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {50-59},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=50},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Hertrampf/95,
AUTHOR = {Hertrampf, Ulrich},
TITLE = {Classes of bounded counting type and their inclusion relations},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {60-70},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=60},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Green/95,
AUTHOR = {Green, Frederic},
TITLE = {Lower bounds for depth-three circuits with equals and mod-gates},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {71-82},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=71},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Krause/95,
AUTHOR = {Krause, Matthias},
TITLE = {On realizing iterated multiplication by small depth threshold circuits},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {83-94},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=83},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Durand/95a,
AUTHOR = {Durand, Bruno},
TITLE = {A random NP-complete problem for inversion of 2D cellular automata},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {95-106},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
KEYWORDS = {computational complexity, automata and formal languages, computer systems theory, cryptography},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=95},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Fagnot/95,
AUTHOR = {Fagnot, Isabelle},
TITLE = {On the subword equivalence problem for infinite words},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {107-118},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=107},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Garel/95,
AUTHOR = {Garel, Emmanuelle},
TITLE = {On the separators on an infinite word generated by a morphism},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {119-130},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
KEYWORDS = {combinatoric on infinite word, circularity, $q$-regularity},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=119},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Monti-Peron/95,
AUTHOR = {Monti, Angelo and Peron, Adriano},
TITLE = {Systolic tree $\omega$-languages},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {131-142},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=131},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Krishnan-Puri-Brayton/95,
AUTHOR = {Krishnan, Sriram C. and Puri, Anuj and Brayton, Robert K.},
TITLE = {Structural complexity of $\omega$-automata},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {143-156},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=143},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Minkwitz/95a,
AUTHOR = {Minkwitz, Torsten},
TITLE = {Algorithms explained by symmetries},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {157-167},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=157},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Fischer-Preparata-Savage/95,
AUTHOR = {Fischer, Paul F. and Preparata, Franco P. and Savage, John E.},
TITLE = {Generalized scans and tri-diagonal systems},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {168-180},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=168},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Crochemore-Gasieniec-Plandowski-Rytter/95,
AUTHOR = {Crochemore, Maxime and G{\c{a}}sieniec, Leszek and Plandowski, Wojciech and Rytter, Wojciech},
TITLE = {Two-dimensional pattern matching in linear time and small space},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {181-192},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=181},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Djidjev-Pantziou-Zaroliagis/95,
AUTHOR = {Djidjev, Hristo N. and Pantziou, Grammati E. and Zaroliagis, Christos D.},
TITLE = {On-line and dynamic algorithms for shortest path problems},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {193-204},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=193},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Cadoli-Donini-Schaerf/95,
AUTHOR = {Cadoli, Marco and Donini, Francesco M. and Schaerf, Marco},
TITLE = {On compact representations of propositional circumscription},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {205-216},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=205},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{DAgostino-Montanari-Policriti/95,
AUTHOR = {D'Agostino, Giovanna and Montanari, Angelo and Policriti, Alberto},
TITLE = {A set-theoretic translation method for (poly)modal logics},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {217-228},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=217},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Maler-Pnueli-Sifakis/95,
AUTHOR = {Maler, Oded and Pnueli, Amir and Sifakis, Joseph},
TITLE = {On the synthesis of discrete controllers for timed systems},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {229-242},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=229},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Boreale-Sangiorgi/95,
AUTHOR = {Boreale, Michele and Sangiorgi, Davide},
TITLE = {A fully abstract semantics for causality in the $\pi$-calculus},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {243-254},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=243},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Hromkovic-Lorys-Kanarek-Klasing-Unger-Wagener/95,
AUTHOR = {Hromkovi{\v{c}}, J. and Lory{\'s}, K. and Kanarek, P. and Klasing, R. and Unger, W. and Wagener, H.},
TITLE = {On the sizes of permutation networks and consequences for efficient simulation of hypercube algorithms on bounded-degree networks},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {255-266},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=255},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Meyer_auf_der_Heide-Scheideler-Stemann/95,
AUTHOR = {Meyer auf der Heide, Friedhelm and Scheideler, Christian and Stemann, Volker},
TITLE = {Exploiting storage redundancy to speed up randomized shared memory simulations},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {267-278},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=267},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Flammini-Gambosi-Salomone/95,
AUTHOR = {Flammini, Michele and Gambosi, Giorgio and Salomone, Sandro},
TITLE = {Interval routing schemes},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {279-290},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
KEYWORDS = {computational complexity, theory of parallel and distributed computing},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=279},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Meyer_auf_der_Heide-Vocking/95,
AUTHOR = {Meyer auf der Heide, Friedhelm and V{\"o}cking, Berthold},
TITLE = {A packet routing protocol for arbitrary networks},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {291-302},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=291},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Bercoff/95,
AUTHOR = {Bercoff, Christiane},
TITLE = {A family of tag systems for paperfolding sequences},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {303-312},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
KEYWORDS = {automata and formal languages, combinatorics on words},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=303},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Buntrock-Otto/95,
AUTHOR = {Buntrock, Gerhard and Otto, Friedrich},
TITLE = {Growing context-sensitive languages and Church-Rosser languages},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {313-324},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=313},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Giammarresi-Montalbano/95,
AUTHOR = {Giammarresi, Dora and Montalbano, Rosa},
TITLE = {Deterministic generalized automata},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {325-336},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=325},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Indyk/95,
AUTHOR = {Indyk, P.},
TITLE = {Optimal simulation of automata by neural nets},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {337-348},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=337},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Duris-Rolim/95,
AUTHOR = {D{\'u}ri{\v{s}}, Pavol and Rolim, Jos{\'e} D.P.},
TITLE = {Optimal lower bounds on the multiparty communication complexity},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {350-360},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=350},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Babai-Kimmel-Lokam/95,
AUTHOR = {Babai, L{\'a}szl{\'o} and Kimmel, Peter G. and Lokam, Satyanarayana V.},
TITLE = {Simultaneous messages vs.\ communication},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {361-372},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=361},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Bruyere-De_Felice/95,
AUTHOR = {Bruy{\`e}re, V{\'e}ronique and De Felice, Clelia},
TITLE = {Coding and strong coding in trace monoids},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {373-384},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=373},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Diekert-Muscholl-Reinhardt/95,
AUTHOR = {Diekert, Volker and Muscholl, Anca and Reinhardt, Klaus},
TITLE = {On codings of traces},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {385-396},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
KEYWORDS = {formal languages, concurrency},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=385},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Gupta-Nishimura/95a,
AUTHOR = {Gupta, Arvind and Nishimura, Naomi},
TITLE = {Finding largest common embeddable subtrees},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {397-408},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=397},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Kaller-Gupta-Shermer/95,
AUTHOR = {Kaller, Damon and Gupta, Arvind and Shermer, Tom},
TITLE = {The $\chi_t$-coloring problem},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {409-420},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=409},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Nikoletseas-Spirakis/95,
AUTHOR = {Nikoletseas, Sotiris E. and Spirakis, Paul G.},
TITLE = {Expander properties in random regular graphs with edge faults},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {421-432},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=421},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Gardy-Louchard/95,
AUTHOR = {Gardy, Dani{\`e}le and Louchard, Guy},
TITLE = {Dynamic analysis of the sizes of relations},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {433-444},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=433},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Raz/95,
AUTHOR = {Raz, Danny},
TITLE = {On slender context-free languages},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {445-454},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
KEYWORDS = {formal languages, context-free grammars, decidability},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=445},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Antimirov/95,
AUTHOR = {Antimirov, Valentin},
TITLE = {Partial derivates of regular expressions and finite automata constructions},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {455-466},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=455},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Bracho-Droste-Kuske/95,
AUTHOR = {Bracho, Felipe and Droste, Manfred and Kuske, Dietrich},
TITLE = {Dependence orders for computations of concurrent automata},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {467-478},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=467},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Fabret-Petit/95,
AUTHOR = {Fabret, Anne-C{\'e}cile and Petit, Antoine},
TITLE = {On the undecidability of deadlock detection in families of nets},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {479-490},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=479},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Rub/95,
AUTHOR = {R{\"u}b, Christine},
TITLE = {On the average running time of odd-even merge sort},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {491-502},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=491},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Kunde-Niedermeier-Reinhardt-Rossmanith/95,
AUTHOR = {Kunde, Manfred and Niedermeier, Rolf and Reinhardt, Klaus and Rossmanith, Peter},
TITLE = {Optimal average case sorting on arrays},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {503-514},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=503},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Strauss/95,
AUTHOR = {Strauss, Martin},
TITLE = {Normal numbers and sources for BPP},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {515-526},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=515},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Hancock-Jiang-Li-Tromp/95,
AUTHOR = {Hancock, Thomas and Jiang, Tao and Li, Ming and Tromp, John},
TITLE = {Lower bounds on learning decision lists and trees},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {527-538},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=527},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Damaschke/95a,
AUTHOR = {Damaschke, Peter},
TITLE = {Line segmentation of digital curves in parallel},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {539-549},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=539},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Kummer-Schafer/95,
AUTHOR = {Kummer, Martin and Sch{\"a}fer, Marcus},
TITLE = {Computability of convex sets},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {550-561},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=550},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Ottmann-Schuierer-Soundaralakshmi/95,
AUTHOR = {Ottmann, Th. and Schuierer, S. and Soundaralakshmi, S.},
TITLE = {Enumerating extreme points in higher dimensions},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {562-570},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=562},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Petitjean/95,
AUTHOR = {Petitjean, Sylvain},
TITLE = {The number of views of piecewise-smooth algebraic objects},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {571-582},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=571},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Macarie/95a,
AUTHOR = {Macarie, Ioan I.},
TITLE = {On the structure of log-space probabilistic complexity classes},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {583-596},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=583},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Fortnow-Kummer/95,
AUTHOR = {Fortnow, Lance and Kummer, Martin},
TITLE = {Resource-bounded instance complexity},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {597-608},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=597},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Buhrman-Hermo/95,
AUTHOR = {Buhrman, Harry and Hermo, Montserrat},
TITLE = {On the sparse set conjecture for sets with low density},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {609-618},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=609},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Fenner-Fortnow/95,
AUTHOR = {Fenner, Stephen A. and Fortnow, Lance J.},
TITLE = {Beyond $P^{NP} = NEXP$},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {619-627},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=619},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Jakoby-Reischuk-Schindelhauer/95,
AUTHOR = {Jakoby, Andreas and Reischuk, R{\"u}diger and Schindelhauer, Christian},
TITLE = {Malign distributions for average case circuit complexity},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {628-639},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
KEYWORDS = {average case complexity, circuit complexity, delay, distribution},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=628},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}
@incollection{Arques-Michel/95,
AUTHOR = {Arqu{\`e}s, Didier G. and Michel, Christian J.},
TITLE = {A possible code in the genetic code},
BOOKTITLE = {Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS'95 (Munich, Germany, March 2-4, 1995)},
SERIES = {LNCS},
VOLUME = {900},
PAGES = {640-651},
YEAR = {1995},
EDITOR = {Mayr, Ernst W. and Puech, Claude},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=900&spage=640},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest},
}