| 2004 | A Ciliate Bio-operation and Language Families. Jürgen Dassow |
| 2004 | A Kleene Theorem for a Class of Communicating Automata with Effective Algorithms. Blaise Genest, Anca Muscholl, Dietrich Kuske |
| 2004 | A Method for Deciding the Finiteness of Deterministic Tabled Picture Languages. Bianca Truthe |
| 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 | An NP-Complete Fragment of LTL. Anca Muscholl, Igor Walukiewicz |
| 2004 | Avoidable Sets and Well Quasi-Orders. Flavio D'Alessandro, Stefano Varricchio |
| 2004 | Basic Notions of Reaction Systems. Andrzej Ehrenfeucht, Grzegorz Rozenberg |
| 2004 | Complementation of Rational Sets on Countable Scattered Linear Orderings. Chloe Rispal, Olivier Carton |
| 2004 | Context-Sensitive Decision Problems in Groups. Stephen R. Lakin, Richard M. Thomas |
| 2004 | Decidability and Complexity in Automatic Monoids. Markus Lohrey |
| 2004 | Developments in Language Theory, 8th International Conference, DLT 2004, Auckland, New Zealand, December 13-17, 2004, Proceedings Cristian Calude, Elena Calude, Michael J. Dinneen |
| 2004 | From Post Systems to the Reachability Problems for Matrix Semigroups and Multicounter Automata. Igor Potapov |
| 2004 | Input Reversals and Iterated Pushdown Automata: A New Characterization of Khabbaz Geometric Hierarchy of Languages. Henning Bordihn, Markus Holzer, Martin Kutrib |
| 2004 | On Codes Defined by Bio-Operations. Mark Daley, Michael Domaratzki |
| 2004 | On Competence in CD Grammar Systems. Maurice H. ter Beek, Erzsébet Csuhaj-Varjú, Markus Holzer, György Vaszil |
| 2004 | On Left-Monotone Deterministic Restarting Automata. Tomasz Jurdzinski, Friedrich Otto, Frantisek Mráz, Martin Plátek |
| 2004 | On the Complexity of 2-Monotone Restarting Automata. Tomasz Jurdzinski, Friedrich Otto, Frantisek Mráz, Martin Plátek |
| 2004 | On the Computation Power of Finite Automata in Two-dimensional Environments. Oleksiy Kurganskyy, Igor Potapov |
| 2004 | On the Equivalence Problem for E-pattern Languages over Small Alphabets. Daniel Reidenbach |
| 2004 | On the Hausdorff Measure of omega-Power Languages. Ludwig Staiger |
| 2004 | On the Maximum Coefficients of Rational Formal Series in Commuting Variables. Christian Choffrut, Massimiliano Goldwurm, Violetta Lonati |
| 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 | P Systems Working in the Sequential Mode on Arrays and Strings. Rudolf Freund |
| 2004 | Recognizable Sets of Graphs, Hypergraphs and Relational Structures: A Survey. Bruno Courcelle |
| 2004 | Regular Expressions for Two-Dimensional Languages Over One-Letter Alphabet. Marcella Anselmo, Dora Giammarresi, Maria Madonia |
| 2004 | Relating Tree Series Transducers and Weighted Tree Automata. Andreas Maletti |
| 2004 | Semantic Shuffle on and Deletion Along Trajectories. Michael Domaratzki |
| 2004 | Some New Directions and Questions in Parameterized Complexity. Rodney G. Downey, Catherine McCartin |
| 2004 | Sturmian Graphs and a Conjecture of Moser. Chiara Epifanio, Filippo Mignosi, Jeffrey O. Shallit, Ilaria Venturini |
| 2004 | The Boolean Closure of Linear Context-Free Languages. Martin Kutrib, Andreas Malcher, Detlef Wotschke |
| 2004 | The Dot-Depth and the Polynomial Hierarchy Correspond on the Delta Levels. Bernd Borchert, Klaus-Jörn Lange, Frank Stephan, Pascal Tesson, Denis Thérien |
| 2004 | The Power of Maximal Parallelism in P Systems. Oscar H. Ibarra, Hsu-Chun Yen, Zhe Dang |
| 2004 | The Role of the Complementarity Relation in Watson-Crick Automata and Sticker Systems. Dietrich Kuske, Peter Weigel |
| 2004 | Tissue P Systems with Minimal Symport/Antiport. Sergey Verlan |
| 2004 | Words Avoiding 7/3-Powers and the Thue-Morse Morphism. Narad Rampersad |