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
Victor J. Rayward-Smith, D. Rebaine: Uet Flow Shop Scheduling with Delays. 23-30
E. Lippe, Arthur H. M. ter Hofstede: A Category Theory Approach to Conceptual Data Modeling. 31-79
John Michael Robson: Separating Words with Machines and Groups. 81-86

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

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

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

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

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