RAIRO - Theoretical Informatics and Applications

Free Access

Foreword

Preface p. I

Christian Choffrut and Yoshiko Wakabayashi

Published online: 15 March 2005

DOI: https://doi.org/10.1051/ita:2005020

• PDF (120.1 KB)
• Online Material

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

Published online: 15 March 2005

DOI: https://doi.org/10.1051/ita:2005001

• PDF (332.4 KB)
• References

The pseudovariety of semigroups of triangular matrices over a finite field p. 31

Jorge Almeida, Stuart W. Margolis and Mikhail V. Volkov

Published online: 15 March 2005

DOI: https://doi.org/10.1051/ita:2005002

• PDF (224.0 KB)
• References

Hereditary properties of words p. 49

József Balogh and Béla Bollobás

Published online: 15 March 2005

DOI: https://doi.org/10.1051/ita:2005003

• PDF (239.2 KB)
• References

Gate circuits in the algebra of transients p. 67

Janusz Brzozowski and Mihaela Gheorghiu

Published online: 15 March 2005

DOI: https://doi.org/10.1051/ita:2005004

• PDF (277.4 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

Published online: 15 March 2005

DOI: https://doi.org/10.1051/ita:2005005

• PDF (241.3 KB)
• References

Similarity relations and cover automata p. 115

Jean-Marc Champarnaud, Franck Guingne and Georges Hansel

Published online: 15 March 2005

DOI: https://doi.org/10.1051/ita:2005006

• PDF (141.8 KB)
• References

Some decision problems on integer matrices p. 125

Christian Choffrut and Juhani Karhumäki

Published online: 15 March 2005

DOI: https://doi.org/10.1051/ita:2005007

• PDF (132.6 KB)
• References

Finding H-partitions efficiently p. 133

Simone Dantas, Celina M.H. de Figueiredo, Sylvain Gravier and Sulamita Klein

Published online: 15 March 2005

DOI: https://doi.org/10.1051/ita:2005008

• PDF (213.9 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

Published online: 15 March 2005

DOI: https://doi.org/10.1051/ita:2005009

• PDF (212.2 KB)
• References

Some decompositions of Bernoulli sets and codes p. 161

Aldo de Luca

Published online: 15 March 2005

DOI: https://doi.org/10.1051/ita:2005010

• PDF (171.9 KB)
• References

A sparse dynamic programming algorithm for alignment with non-overlapping inversions p. 175

Alair Pereira do Lago, Ilya Muchnik and Casimir Kulikowski

Published online: 15 March 2005

DOI: https://doi.org/10.1051/ita:2005011

• PDF (359.2 KB)
• References

A note on the Size-Ramsey number of long subdivisions of graphs p. 191

Jair Donadelli, Penny E. Haxell and Yoshiharu Kohayakawa

Published online: 15 March 2005

DOI: https://doi.org/10.1051/ita:2005019

• PDF (237.0 KB)
• References

Episturmian morphisms and a Galois theorem on continued fractions p. 207

Jacques Justin

Published online: 15 March 2005

DOI: https://doi.org/10.1051/ita:2005012

• PDF (150.9 KB)
• References

How expressions can code for automata p. 217

Sylvain Lombardy and Jacques Sakarovitch

Published online: 15 March 2005

DOI: https://doi.org/10.1051/ita:2005013

• PDF (259.8 KB)
• References

Some results on C-varieties p. 239

Jean-Éric Pin and Howard Straubing

Published online: 15 March 2005

DOI: https://doi.org/10.1051/ita:2005014

• PDF (255.9 KB)
• References

Parity codes p. 263

Paulo E. D. Pinto, Fábio Protti and Jayme L. Szwarcfiter

Published online: 15 March 2005

DOI: https://doi.org/10.1051/ita:2005015

• PDF (216.0 KB)
• References

Krohn-Rhodes complexity pseudovarieties are not finitely based p. 279

John Rhodes and Benjamin Steinberg

Published online: 15 March 2005

DOI: https://doi.org/10.1051/ita:2005016

• PDF (223.1 KB)
• References

Imre Simon: an exceptional graduate student p. 297

Denis Thérien

Published online: 15 March 2005

DOI: https://doi.org/10.1051/ita:2005017

• PDF (130.5 KB)
• References

Algebraic and graph-theoretic properties of infinite n-posets p. 305

Zoltán Ésik and Zoltán L. Németh

Published online: 15 March 2005

DOI: https://doi.org/10.1051/ita:2005018

• PDF (230.3 KB)
• References