This special issue of Logical Methods in Computer Science contains the revised and extended versions of five articles selected from those presented at the Track B of the 35th International Colloquium on Automata, Languages and Programming (ICALP 2008). The meeting took place in Reykjavik, Iceland form July the 6th to the 13th, 2008. The ICALP colloquium is the main annual meeting of the European Association for Theoretical Com- puter Science (EATCS). Among the three tracks of the conference, Track B is devoted to logic, semantics, and theory of programming.

The article On the Sets of Real Numbers Recognized by Finite Automata in Multiple Bases by Bernard Boigelot, Julien Brusten, and Véronique Bruyère gives precise characterization of the sets of real numbers that are recognizable in multiple bases, and provides a theoretical justification to the use of weak automata as symbolic representations of sets.

The article Tree languages defined in first-order logic with one quantifier alternation by Mikolaj Bojanczyk and Luc Segoufin shows an effective characterization of tree and forest languages definable in Δ₂ fragment of first-order logic.

The article A Theory of Explicit Substitutions with Safe and Full Composition by Delia Kesner solves an old problem of finding a system with explicit substitutions that enjoys all the good properties one expects from such a system, namely, full composition, faithfulness of the representation of β-conversion, strong normalisation and confluence.

The article A Type System For Call-By-Name Exceptions by Sylvain Lebresne presents a type system for a polymorphic call-by-name language with exceptions whose central idea is to enrich the type system with an operator for corruption. Using corruption, and an appropriate subtyping system, one obtains a rather flexible type system whose soundness is proved by resorting to realizability semantics.

The article Weighted Logics for Nested Words and Algebraic Formal Power Series by Christian Mathissen exhibits characterizations of algebraic formal power series in terms of weighted logics.

We thank the authors for their contributions. For inclusion in this special issues all articles underwent a new and complete reviewing process. We are grateful to the reviewers for their valuable feedback. We also thank the members of the Program Committee of ICALP 2008 and their sub-referees who contributed to the selection and the refereeing process.