| 2004 | On the Hausdorff Measure of omega-Power Languages. | Ludwig Staiger |
| 2004 | Complementation of Rational Sets on Countable Scattered Linear Orderings. | Chloe Rispal, Olivier Carton |
| 2004 | On the Equivalence Problem for E-pattern Languages over Small Alphabets. | Daniel Reidenbach |
| 2004 | Words Avoiding 7/3-Powers and the Thue-Morse Morphism. | Narad Rampersad |
| 2004 | From Post Systems to the Reachability Problems for Matrix Semigroups and Multicounter Automata. | Igor Potapov |
| 2004 | An NP-Complete Fragment of LTL. | Anca Muscholl, Igor Walukiewicz |
| 2004 | Relating Tree Series Transducers and Weighted Tree Automata. | Andreas Maletti |
| 2004 | Decidability and Complexity in Automatic Monoids. | Markus Lohrey |
| 2004 | Context-Sensitive Decision Problems in Groups. | Stephen R. Lakin, Richard M. Thomas |
| 2004 | The Boolean Closure of Linear Context-Free Languages. | Martin Kutrib, Andreas Malcher, Detlef Wotschke |
| 2004 | The Role of the Complementarity Relation in Watson-Crick Automata and Sticker Systems. | Dietrich Kuske, Peter Weigel |
| 2004 | On the Computation Power of Finite Automata in Two-dimensional Environments. | Oleksiy Kurganskyy, Igor Potapov |
| 2004 | On Left-Monotone Deterministic Restarting Automata. | Tomasz Jurdzinski, Friedrich Otto, Frantisek Mrz, Martin Pltek |
| 2004 | On the Complexity of 2-Monotone Restarting Automata. | Tomasz Jurdzinski, Friedrich Otto, Frantisek Mrz, Martin Pltek |
| 2004 | Algebraic and Topological Models for DNA Recombinant Processes. | Natasa Jonoska, Masahico Saito |
| 2004 | An Efficient Pattern Matching Algorithm on a Subclass of Context Free Grammars. | Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda |
| 2004 | The Power of Maximal Parallelism in P Systems. | Oscar H. Ibarra, Hsu-Chun Yen, Zhe Dang |
| 2004 | Optimal Time and Communication Solutions of Firing Squad Synchronization Problems on Square Arrays, Toruses and Rings. | Jozef Gruska, Salvatore La Torre, Mimmo Parente |
| 2004 | A Kleene Theorem for a Class of Communicating Automata with Effective Algorithms. | Blaise Genest, Anca Muscholl, Dietrich Kuske |
| 2004 | P Systems Working in the Sequential Mode on Arrays and Strings. | Rudolf Freund |
| 2004 | Sturmian Graphs and a Conjecture of Moser. | Chiara Epifanio, Filippo Mignosi, Jeffrey O. Shallit, Ilaria Venturini |
| 2004 | Basic Notions of Reaction Systems. | Andrzej Ehrenfeucht, Grzegorz Rozenberg |
| 2004 | Some New Directions and Questions in Parameterized Complexity. | Rodney G. Downey, Catherine McCartin |
| 2004 | Semantic Shuffle on and Deletion Along Trajectories. | Michael Domaratzki |
| 2004 | A Ciliate Bio-operation and Language Families. | Jrgen Dassow |