International Journal of Foundations of Computer Science, Volume 18

Volume 18, Number 1, February 2007

• Doron Peled, Yih-Kuen Tsay:
  Preface. 1-4
  
• Ittai Balaban, Amir Pnueli, Lenore D. Zuck:
  Modular Ranking Abstraction. 5-44
  
• Limor Fix, Orna Grumberg, Amnon Heyman, Tamir Heyman, Assaf Schuster:
  Verifying Very Large Industrial Circuits Using 100 Processes and Beyond. 45-62
  
• Werner Damm, Guilherme Pinto, Stefan Ratschan:
  Guaranteed Termination in the Verification of Ltl Properties of Non-linear Robust Discrete Time Hybrid Systems. 63-86
  
• Stéphane Demri, David Nowak:
  Reasoning about Transfinite Sequences. 87-112
  
• Sven Schewe, Bernd Finkbeiner:
  Semi-automatic Distributed Synthesis. 113-138
  

• Tobias Lauer, Thomas Ottmann, Amitava Datta:
  Update-efficient Data Structures for Dynamic Ip Router Tables. 139-162
  
• Artiom Alhazov, Yurii Rogozhin, Sergey Verlan:
  Minimal Cooperation in Symport/antiport Tissue P Systems. 163-180
  
• Juha Honkala:
  The D0l omega-equivalence Problem. 181-194
  

Volume 18, Number 2, April 2007

• Joachim Gudmundsson, C. Barry Jay:
  Preface. 195-196
  
• Yuichi Asahiro, Eiji Miyano, Hirotaka Ono, Kouhei Zenmyo:
  Graph Orientation Algorithms to minimize the Maximum Outdegree. 197-215
  
• Anders Dessmark, Jesper Jansson, Andrzej Lingas, Eva-Marta Lundell, Mia Persson:
  On the Approximability of Maximum and Minimum Edge Clique Partition Problems. 217-226
  
• Brian Herlihy, Peter Schachte, Harald Søndergaard:
  Un-Kleene Boolean equation Solving. 227-250
  
• Chung Keung Poon, Feifeng Zheng, Yinfeng Xu:
  On-Demand Bounded Broadcast Scheduling with Tight Deadlines. 251-262
  
• Tadao Takaoka, Stephen Violich:
  Fusing Loopless Algorithms for Combinatorial Generation. 263-293
  
• Tobias Lauer, Thomas Ottmann, Amitava Datta:
  Update-Efficient Data Structures for Dynamic IP Router Tables. 295-317
  
• Sung Eun Bae, Tadao Takaoka:
  Algorithms for k-Disjoint Maximum Subarrays. 319-339
  
• Joseph Y.-T. Leung, Haibing Li, Hairong Zhao:
  Scheduling Two-Machine Flow shops with Exact Delays. 341-359
  
• Tomasz Jurdzinski, Friedrich Otto:
  Shrinking Restarting Automata. 361-385
  
• Adrian Atanasiu:
  Binary amiable Words. 387-400
  
• Jesper Jansson, Zeshan Peng:
  Online and Dynamic Recognition of Squarefree Strings. 401-414
  
• Ludek Cienciala, Lucie Ciencialová, Pierluigi Frisco, Petr Sosík:
  On the Power of Deterministic and Sequential Communicating P Systems. 415-431
  

Volume 18, Number 3, June 2007

• Jacir Luiz Bordim, Koji Nakano:
  Preface. 433-434
  
• Gheorghe Paun, Mario J. Pérez-Jiménez, Arto Salomaa:
  Spiking Neural P Systems: an Early Survey. 435-455
  
• Fabrizio Luccio, Linda Pagli, Nicola Santoro:
  Network decontamination in Presence of Local Immunity. 457-474
  
• Akihiro Fujiwara, Satoshi Kamio, Akiko Takehara:
  Procedures for Computing the Maximum with DNA. 475-493
  
• Francesco Quaglia:
  Software Diversity-Based Active Replication as an Approach for Enhancing the Performance of Advanced Simulation Systems. 495-515
  
• Yasuaki Ito, Koji Nakano, Youhei Yamagishi:
  Efficient Hardware Algorithms for n Choose k Counters Using the Bitonic Merger. 517-528
  
• Hanane Becha, Paola Flocchini:
  Optimal Construction of Sense of Direction in a Torus by a Mobile Agent. 529-546
  
• Paola Flocchini, Miao Jun Huang, Flaminia L. Luccio:
  Decontaminating Chordal Rings and Tori Using Mobile Agents. 547-563
  
• Alan J. Soper, Vitaly A. Strusevich:
  An Improved Approximation Algorithm for the Two-Machine Flow Shop Scheduling Problem with an interstage transporter. 565-591
  
• Benjamin Aziz, Geoff Hamilton:
  Modelling and Analysis of PKI-Based Systems Using Process Calculi. 593-618
  
• Gautam K. Das, Sasthi C. Ghosh, Subhas C. Nandy:
  Improved Algorithm for Minimum Cost Range Assignment Problem for Linear Radio Networks. 619-635
  
• Jozef Gruska, Salvatore La Torre, Mimmo Parente:
  The Firing Squad Synchronization Problem on Squares, Toruses and Rings. 637-654
  
• Arseny M. Shur:
  Rational Approximations of Polynomial Factorial Languages. 655-665
  

Volume 18, Number 4, August 2007

• Oscar H. Ibarra, Hsu-Chun Yen:
  Preface. 667-668
  
• Ming Li:
  Information Distance and its Applications. 669-681
  
• Kai Salomaa, Sheng Yu:
  On the State Complexity of Combined Operations and their Estimation. 683-698
  
• Parosh Aziz Abdulla, Johanna Högberg, Lisa Kaati:
  Bisimulation Minimization of Tree Automata. 699-713
  
• Cédric Bastien, Jurek Czyzowicz, Wojciech Fraczak, Wojciech Rytter:
  Reducing Simple Grammars: Exponential against Highly-Polynomial Time in Practice. 715-725
  
• Roderick Bloem, Alessandro Cimatti, Ingo Pill, Marco Roveri:
  Symbolic Implementation of Alternating Automata. 727-743
  
• Henning Bordihn, Markus Holzer, Martin Kutrib:
  Hybrid Extended Finite Automata. 745-760
  
• Corinna Cortes, Mehryar Mohri, Ashish Rastogi:
  L_P Distance and Equivalence of Probabilistic Automata. 761-779
  
• Maxime Crochemore, Lucian Ilie, Emine Seid-Hilmi:
  The Structure of Factor Oracles. 781-797
  
• Mathieu Giraud, Philippe Veber, Dominique Lavenier:
  Path-Equivalent Developments in Acyclic Weighted Automata. 799-811
  
• Jens Glöckler:
  Forgetting Automata and Unary Languages. 813-827
  
• Andreas Maletti:
  Pure and O-Substitution. 829-845
  
• Florent Nicart, Jean-Marc Champarnaud, Tibor Csáki, Tamás Gaál, André Kempe:
  Labelling Multi-Tape Automata with Constrained Symbol Classes. 847-858
  
• Martin Simunek, Borivoj Melichar:
  Borders and Finite Automata. 859-871
  
• Elena Czeizler, Juhani Karhumäki:
  On Non-Periodic Solutions of Independent Systems of Word Equations over Three Unknowns. 873-897
  
• Sudha Balla, Sanguthevar Rajasekaran, Ion I. Mandoiu:
  Efficient Algorithms for degenerate Primer Search. 899-910
  

Volume 18, Number 5, October 2007

• Ryuhei Uehara, Yushi Uno:
  On Computing Longest Paths in Small Graph Classes. 911-930
  
• Vesa Halava, Tero Harju, Mika Hirvensalo:
  Undecidability Bounds for Integer Matrices Using Claus Instances. 931-948
  
• Bala Ravikumar, Nicolae Santean:
  On the Existence of Lookahead Delegators for NFA. 949-973
  
• Miguel Couceiro, Erkko Lehtonen:
  On the Effect of Variable Identification on the Essential Arity of Functions on Finite Sets. 975-986
  
• Zhenchuan Chai, Zhenfu Cao, Xiaolei Dong:
  Efficient ID-Based Multi-Receiver Threshold Decryption. 987-1004
  
• Eddie Cheng, László Lipták:
  Fault Resiliency of Cayley Graphs Generated by Transpositions. 1005-1022
  
• Bhuvan Urgaonkar, Arnold L. Rosenberg, Prashant J. Shenoy:
  Application Placement on a Cluster of Servers. 1023-1041
  
• Cho-Chin Lin:
  A Framework for Solving Sequence Problem of Multiple Input Streams. 1043-1064
  
• Janusz A. Brzozowski, Helmut Jürgensen:
  Representation of Semiautomata by Canonical Words and Equivalences, Part II: Specification of Software Modules. 1065-1087
  
• Lila Kari, Kalpana Mahalingam:
  Involutively Bordered Words. 1089-1106
  
• Partha Sarathi Mandal, Krishnendu Mukhopadhyaya:
  Mobile Agent Based Checkpointing with Concurrent Initiations. 1107-1122
  
• Tseren-Onolt Ishdorj, Ion Petre, Vladimir Rogojin:
  Computational Power of intramolecular gene Assembly. 1123-1136
  

Volume 18, Number 6, December 2007

• Henning Bordihn, Bernd Reichel, Ralf Stiebe, Bianca Truthe:
  Preface: Aspects in Language and Automata Theory Special Issue Dedicated to JÜrgen Dassow. 1137-1138
  
• Peter R. J. Asveld:
  Generating All Circular Shifts by Context-Free Grammars in Greibach Normal Form. 1139-1149
  
• Charita Bhika, Sigrid Ewert, Ryan Schwartz, Mutahi Waruhiu:
  Table-Driven Context-Free Picture Grammars. 1151-1160
  
• Oliver Boldt, Helmut Jürgensen:
  Soliton Languages are Nearly an Anti-AFL. 1161-1165
  
• Elena Czeizler, Stepan Holub, Juhani Karhumäki, Markku Laine:
  Intricacies of Simple Word Equations: an Example. 1167-1175
  
• Mark Daley, Michael Domaratzki, Alexis Morris:
  Intra-Molecular Template-Guided Recombination. 1177-1186
  
• Frank Drewes:
  Links. 1187-1196
  
• Zoltán Ésik, Werner Kuich:
  Boolean Fuzzy Sets. 1197-1207
  
• Henning Fernau:
  Programmed Grammars with Rule Queues. 1209-1213
  
• Rudolf Freund, Marion Oswald:
  Partial Halting in P Systems. 1215-1225
  
• Yan Gao, Hendrik Jan Hoogeboom:
  P Systems with Single passenger Carriers. 1227-1235
  
• Ferenc Gécseg:
  Classes of Tree Languages Determined by Classes of Monoids. 1237-1246
  
• Oscar H. Ibarra, Sara Woodworth:
  Characterizing Regular Languages by Spiking Neural P Systems. 1247-1256
  
• Helmut Jürgensen, Pauline Kraak:
  Soliton Automata Based on Trees. 1257-1270
  
• Andreas Klein, Martin Kutrib:
  Context-Free Grammars with Linked Nonterminals. 1271-1282
  
• Manfred Kudlek:
  Some Remarks on Quantum Automata. 1283-1292
  
• Martin Kutrib, Andreas Malcher:
  When Church-Rosser Becomes Context Free. 1293-1302
  
• Enzo Magalini, Giovanni Pighizzini:
  A Pumping Condition for Ultralinear Languages. 1303-1312
  
• Andreas Malcher, Bettina Sunckel:
  On Metalinear Parallel Communicating Grammar Systems. 1313-1322
  
• Carlos Martín-Vide, Victor Mitrana:
  Decision Problems on Path-Controlled Grammars. 1323-1332
  
• Hartmut Messerschmidt, Friedrich Otto:
  Cooperating Distributed Systems of Restarting Automata. 1333-1342
  
• Frantisek Mráz, Martin Plátek, Tomasz Jurdzinski:
  Ambiguity by Restarting Automata. 1343-1352
  
• Taishin Y. Nishida:
  Membrane Algorithm with Brownian Subalgorithm and Genetic Subalgorithm. 1353-1360
  
• Alexander Okhotin:
  Notes on Dual Concatenation. 1361-1370
  
• Gheorghe Paun, Mario J. Pérez-Jiménez, Grzegorz Rozenberg:
  Computing Morphisms by Spiking Neural P Systems. 1371-1382
  
• Klaus Reinhardt:
  A Tree-Height Hierarchy of Context-Free Languages. 1383-1394
  
• Arto Salomaa:
  Comparing Subword Occurrences in Binary D0L Sequences. 1395-1406
  
• Kai Salomaa, Paul Schofield:
  State Complexity of Additive Weighted Finite Automata. 1407-1416
  
• Ludwig Staiger:
  Prefix-Free Lukasiewicz Languages. 1417-1423
  
• Maurice H. ter Beek, Erzsébet Csuhaj-Varjú, György Vaszil, Markus Holzer:
  On Competence in CD Grammar Systems with Parallel Rewriting. 1425-1439
  
• Sheng Yu, Qing Zhao:
  Sc-Expressions in Object-Oriented Languages. 1441-1452