Informatique Théorique et Applications, Volume 33, 1999

Volume 33, Number 1, January/February 1999

Rafael C. Carrasco, José Oncina: Learning deterministic regular grammars from stochastic samples in polynomial time. 1-20
Christoph Meinel, Thorsten Theobald: On the Influence of the State Encoding on OBDD-Representations of Finite State Machines. 21-32
Maria J. Serna, Fatos Xhafa: On the Average Case Complexity of Some P-complete Problems. 33-46
Carla Selmi: Strongly locally testable semigroups with commuting idempotents and related languages. 47-58
Ines Abdeljaouad: Calculs d'invariants primitifs de groupes finis. 59-78
Christiane Frougny: On-line finite automata for addition in some numeration systems. 79-101

Beate Bollig, Martin Löbbing, Martin Sauerhoff, Ingo Wegener: On the complexity of the hidden weighted bit function for various BDD models. 103-116
Vesa Halava, Tero Harju: Undecidability of the equivalence of finite substitutions on regular language. 117-124
Juha Honkala: On sequences defined by D0L power series. 125-132
Roman R. Redziejowski: Construction of a deterministic -automaton using derivatives. 133-158
Jörg Rothe: Immunity and simplicity for exact counting and other counting classes. 159-176
Rudolf Grübel: On the median-of-K version of Hoare's selection algorithm. 177-192
Juraj Hromkovic: Communication complexity and lower bounds on multilective computations. 193-212

Phan Trung Huy, Nguyen Huong Lam: Unavoidable set: extension and reduction. 213-226
Anne Preller, P. Duroux: Normalisation of the Theory T of Cartesian Closed Categories and Conservativity of Extensions T[x] of T. 227-258
Bernd Borchert, Dietrich Kuske, Frank Stephan: On existentially first-order definable languages and their relation to NP. 259-270
Andrzej Szepietowski: There is no complete axiom system for shuffle expressions. 271-278
Alfons Geser, Hans Zantema: Non-looping string rewriting. 279-302
Andrzej Szepietowski: Lower space bounds for accepting shuffle languages. 303-307

Ralph Matthes: Monotone (co)inductive types and positive fixed-point types. 309-328
André Arnold: p329 The µ-calculus alternation-depth hierarchy is strict on binary trees. 329-340
Julian C. Bradfield: Fixpoint alternation: Arithmetic, transition systems, and the binary tree. 341-356
Jennifer M. Davoren: Topologies, continuity and bisimulations. 357-382
Dilian Gurov, Bruce M. Kapron: A note on negative tagging for least fixed-point formulae. 383-392
Jan J. M. M. Rutten: A note on coinduction and weak bisimilarity for while programs. 393-400
Roland Carl Backhouse, Paul F. Hoogendijk: Final dialgebras: From categories to allegories. 401-426
Helmut Seidl, Damian Niwinski: On distributive fixed-point expressions. 427-446
Flavio Corradini, Rocco De Nicola, Anna Labella: A finite axiomatization of nondeterministic regular expressions. 447-466
Andrea Corradini, Fabio Gadducci: Rewriting on cyclic structures: Equivalence between the operational and the categorical description. 467-493

Olivier Carton, Ramón Maceiras: Computing the Rabin Index of a Parity Automaton. 495-506
Luca Paolini, Simona Ronchi Della Rocca: Call-by-value Solvability. 507-534
Kenichi Morita, Maurice Margenstern, Katsunobu Imai: Universality of Reversible Hexagonal Cellular Automata. 535-550