Informatique Théorique et Applications, Volume 30, 1996

Volume 30, Number 1, 1996

Eric Allender, Mitsunori Ogihara: Relationships Among PL, #L, and the Determinant. 1-21 BibTeX
Victor J. Rayward-Smith, D. Rebaine: Uet Flow Shop Scheduling with Delays. 23-30 BibTeX
E. Lippe, Arthur H. M. ter Hofstede: A Category Theory Approach to Conceptual Data Modeling. 31-79 BibTeX
John Michael Robson: Separating Words with Machines and Groups. 81-86 BibTeX

Antoni Lozano: Bounded Queries to Arbitrary Sets. 91-100 BibTeX
Jorge Castro, Carlos Seara: Complexity Classes Between Theta^P_k and Delta^P_k . 101-121 BibTeX
Ronald V. Book, Elvira Mayordomo: On the Robustness of ALMOST-R. 123-133 BibTeX
Thomas Thierauf, Seinosuke Toda, Osamu Watanabe: On Sets Bounded Truth-Table Reducible to P-Selective Sets. 135-154 BibTeX
Vikraman Arvind, Johannes Köbler, Martin Mundhenk: Monotonous and Randomized Reductions to Sparse Sets. 155-179 BibTeX

Bertrand Le Saëc, Igor Litovsky, Bruno Patrou: A More Efficient Notion of Zigzag Stability. 181-194 BibTeX
Michael Cramer: A Note Concerning the Limit Distribution of the Quicksort Algorithm. 195-207 BibTeX
Nami Kobayashi: The Closure Under Division and a Characterization of the Recognizable Z-Subsets. 209-230 BibTeX
Mehmet A. Orgun: Incorporating an Implicit Time Dimension Into the Relational Model and Algebra. 231-260 BibTeX
Karim Nour: Opérateurs de mise en mémoire et types forall-positifs. 261-293 BibTeX

Dominique Geniet, René Schott, Loÿs Thimonier: A Markovian Concurrency Measure. 295-304 BibTeX
Paola Alimonti, Stefano Leonardi, Alberto Marchetti-Spaccamela: Average Case Analysis of Fully Dynamic Reachability for Directed Graphs. 305-318 BibTeX
Lionel Ducos: Algorithme de Bareiss, algorithme des sous-résultants. 319-347 BibTeX
Pedro V. Silva: On Free Inverse Monoid Languages. 349-378 BibTeX

Andreas Weber: Decomposing A k-Valued Transducer into k Unambiguous Ones. 379-413 BibTeX
Winfried Kurth: One-Rule Semi-Thue Systems with Loops of Length One, Two or Three. 415-429 BibTeX
Pierluigi Crescenzi, Luca Trevisan: On the Distributed Decision-Making Complexity of the Minimum Vertex Cover Problem. 431-441 BibTeX
Luc Devroye, Paul Kruszewski: On the Horton-Strahler Number for Random Tries. 443-456 BibTeX
Francine Blanchet-Sadri: On Semidirect and Two-Sided Semidirect Products of Finite J-Trivial Monoids. 457-482 BibTeX

Nguyen Huong Lam: On Codes Having no Finite Completion. 483-493 BibTeX
L. Dubuc: Les automates circulaires biaisés vérifient la conjecture de Cerný. 495-505 BibTeX
Markus E. Nebel: Digital Search Trees with Keys of Variable Length. 507-520 BibTeX
Dany Breslauer, Leszek Gasieniec: Efficient String Matching on Packed Texts. 521-544 BibTeX
Rainer Kemp: On the Average Minimal Prefix-Length of the Generalized Semi-Dycklanguage. 545-561 BibTeX