Theoretical Informatics and Applications

Vol. 39 No. 1 (January-March 2005)

Special Issue: Imre Simon, the tropical computer scientist

• Imre Simon
  
  
• Preface     p. I
  Christian Choffrut and Yoshiko Wakabayashi
  Abstract | PDF file (120 KB)



• The globals of pseudovarieties of ordered semigroups containing B₂ and an application to a problem proposed by Pin     p. 1
  Jorge Almeida and Ana P. Escada
  Abstract | PDF file (334 KB) | References



• The pseudovariety of semigroups of triangular matrices over a finite field     p. 31
  Jorge Almeida, Stuart W. Margolis and Mikhail V. Volkov
  Abstract | PDF file (225 KB) | References



• Hereditary properties of words     p. 49
  József Balogh and Béla Bollobás
  Abstract | PDF file (240 KB) | References



• Gate circuits in the algebra of transients     p. 67
  Janusz Brzozowski and Mihaela Gheorghiu
  Abstract | PDF file (280 KB) | References



• On the number of dissimilar pfaffian orientations of graphs     p. 93
  Marcelo H. de Carvalho, Cláudio L. Lucchesi and U.S.R. Murty
  Abstract | PDF file (242 KB) | References



• Similarity relations and cover automata     p. 115
  Jean-Marc Champarnaud, Franck Guingne and Georges Hansel
  Abstract | PDF file (142 KB) | References



• Some decision problems on integer matrices     p. 125
  Christian Choffrut and Juhani Karhumäki
  Abstract | PDF file (133 KB) | References



• Finding H-partitions efficiently     p. 133
  Simone Dantas, Celina M.H. de Figueiredo, Sylvain Gravier and Sulamita Klein
  Abstract | PDF file (214 KB) | References



• The perfection and recognition of bull-reducible Berge graphs     p. 145
  Hazel Everett, Celina M.H. de Figueiredo, Sulamita Klein and Bruce Reed
  Abstract | PDF file (213 KB) | References



• Some decompositions of Bernoulli sets and codes     p. 161
  Aldo de Luca
  Abstract | PDF file (173 KB) | References



• A sparse dynamic programming algorithm for alignment with non-overlapping inversions     p. 175
  Alair Pereira do Lago, Ilya Muchnik and Casimir Kulikowski
  Abstract | PDF file (370 KB)  | References



• A note on the Size-Ramsey number of long subdivisions of graphs     p. 191
  Jair Donadelli, Penny E. Haxell and Yoshiharu Kohayakawa
  Abstract | PDF file (238 KB) | References



• Episturmian morphisms and a Galois theorem on continued fractions     p. 207
  Jacques Justin
  Abstract | PDF file (151 KB) | References



• How expressions can code for automata     p. 217
  Sylvain Lombardy and Jacques Sakarovitch
  Abstract | PDF file (261 KB) | References



• Some results on -varieties     p. 239
  Jean-Éric Pin and Howard Straubing
  Abstract | PDF file (257 KB) | References



• Parity codes     p. 263
  Paulo E. D. Pinto, Fábio Protti and Jayme L. Szwarcfiter
  Abstract | PDF file (217 KB) | References



• Krohn-Rhodes complexity pseudovarieties are not finitely based     p. 279
  John Rhodes and Benjamin Steinberg
  Abstract | PDF file (224 KB) | References



• Imre Simon: an exceptional graduate student     p. 297
  Denis Thérien
  Abstract | PDF file (131 KB) | References



• Algebraic and graph-theoretic properties of infinite n-posets     p. 305
  Zoltán Ésik and Zoltán L. Németh
  Abstract | PDF file (231 KB) | References