Table of contents for issues of International Journal of Foundations of Computer Science (IJFCS)

Last update: Sat Jun 30 07:23:00 MDT 2018                Valid HTML 3.2!

Volume 1, Number 1, March, 1990
Volume 1, Number 2, June, 1990
Volume 1, Number 3, September, 1990
Volume 1, Number 4, December, 1990
Volume 2, Number 1, March, 1991
Volume 2, Number 2, June, 1991
Volume 2, Number 3, September, 1991
Volume 2, Number 4, December, 1991
Volume 3, Number 1, March, 1992
Volume 3, Number 2, June, 1992
Volume 3, Number 3, September, 1992
Volume 3, Number 4, December, 1992
Volume 4, Number 1, March, 1993
Volume 4, Number 2, June, 1993
Volume 4, Number 3, September, 1993
Volume 4, Number 4, December, 1993
Volume 5, Number 3/4, 1994
Volume 6, Number 1, 1995
Volume 6, Number 2, 1995
Volume 6, Number 3, 1995
Volume 6, Number 4, 1995
Volume 7, Number 1, 1996
Volume 7, Number 2, 1996
Volume 7, Number 3, 1996
Volume 7, Number 4, 1996
Volume 8, Number 1, March, 1997
Volume 8, Number 2, June, 1997
Volume 8, Number 3, September, 1997
Volume 8, Number 4, December, 1997
Volume 9, Number 1, March, 1998
Volume 9, Number 2, June, 1998
Volume 9, Number 3, 1998
Volume 9, Number 4, December, 1998
Volume 10, Number 1, 1999
Volume 10, Number 2, 1999
Volume 10, Number 3, 1999
Volume 10, Number 4, 1999
Volume 11, Number 1, 2000
Volume 11, Number 2, 2000
Volume 11, Number 3, 2000
Volume 11, Number 4, 2000
Volume 12, Number 1, 2001
Volume 12, Number 2, 2001
Volume 12, Number 3, 2001
Volume 12, Number 4, 2001
Volume 12, Number 5, 2001
Volume 12, Number 6, December, 2001
Volume 13, Number 1, 2002
Volume 13, Number 2, 2002
Volume 13, Number 3, 2002
Volume 13, Number 4, 2002
Volume 13, Number 5, October, 2002
Volume 13, Number 6, December, 2002
Volume 14, Number 1, February, 2003
Volume 14, Number 2, April, 2003
Volume 14, Number 3, June, 2003
Volume 14, Number 4, August, 2003
Volume 14, Number 5, October, 2003
Volume 14, Number 6, December, 2003
Volume 15, Number 1, February, 2004
Volume 15, Number 2, April, 2004
Volume 15, Number 3, June, 2004
Volume 15, Number 4, August, 2004
Volume 15, Number 5, October, 2004
Volume 15, Number 6, December, 2004
Volume 16, Number 1, February, 2005
Volume 16, Number 2, April, 2005
Volume 16, Number 3, June, 2005
Volume 16, Number 4, August, 2005
Volume 16, Number 5, October, 2005
Volume 16, Number 6, December, 2005
Volume 17, Number 1, February, 2006
Volume 17, Number 2, April, 2006
Volume 17, Number 3, June, 2006
Volume 17, Number 4, August, 2006
Volume 17, Number 5, October, 2006
Volume 17, Number 6, December, 2006
Volume 18, Number 1, February, 2007
Volume 18, Number 2, April, 2007
Volume 18, Number 3, June, 2007
Volume 18, Number 4, August, 2007
Volume 18, Number 5, October, 2007
Volume 18, Number 6, December, 2007
Volume 19, Number 1, February, 2008
Volume 19, Number 2, April, 2008
Volume 19, Number 3, June, 2008
Volume 19, Number 4, August, 2008
Volume 19, Number 5, October, 2008
Volume 19, Number 6, December, 2008
Volume 20, Number 1, February, 2009
Volume 20, Number 2, April, 2009
Volume 20, Number 3, June, 2009
Volume 20, Number 4, August, 2009
Volume 20, Number 5, October, 2009
Volume 20, Number 6, December, 2009
Volume 21, Number 1, February, 2010
Volume 21, Number 2, April, 2010
Volume 21, Number 3, June, 2010
Volume 21, Number 4, August, 2010
Volume 21, Number 5, October, 2010
Volume 22, Number 1, January, 2011
Volume 22, Number 2, February, 2011
Volume 22, Number 3, April, 2011
Volume 22, Number 4, June, 2011
Volume 22, Number 5, August, 2011
Volume 22, Number 6, September, 2011
Volume 22, Number 7, November, 2011
Volume 22, Number 8, December, 2011
Volume 23, Number 1, January, 2012
Volume 23, Number 2, February, 2012
Volume 23, Number 3, April, 2012
Volume 23, Number 4, June, 2012
Volume 23, Number 5, August, 2012
Volume 23, Number 6, September, 2012
Volume 23, Number 7, November, 2012
Volume 23, Number 8, December, 2012
Volume 24, Number 1, January, 2013
Volume 24, Number 2, February, 2013
Volume 24, Number 3, April, 2013
Volume 24, Number 4, June, 2013
Volume 24, Number 5, August, 2013
Volume 24, Number 6, September, 2013
Volume 24, Number 7, November, 2013
Volume 24, Number 8, December, 2013
Volume 25, Number 1, January, 2014
Volume 25, Number 2, February, 2014
Volume 25, Number 3, April, 2014
Volume 25, Number 5, August, 2014
Volume 25, Number 6, September, 2014
Volume 25, Number 7, November, 2014
Volume 25, Number 8, December, 2014
Volume 26, Number 1, January, 2015
Volume 26, Number 2, February, 2015
Volume 26, Number 3, April, 2015
Volume 26, Number 4, June, 2015
Volume 26, Number 5, August, 2015
Volume 26, Number 6, September, 2015
Volume 26, Number 7, November, 2015
Volume 26, Number 8, December, 2015
Volume 27, Number 1, January, 2016
Volume 27, Number 2, February, 2016
Volume 27, Number 3, April, 2016
Volume 27, Number 4, June, 2016
Volume 27, Number 5, August, 2016
Volume 27, Number 6, September, 2016
Volume 27, Number 7, November, 2016
Volume 27, Number 8, December, 2016
Volume 28, Number 1, January, 2017
Volume 28, Number 2, February, 2017
Volume 28, Number 3, April, 2017
Volume 28, Number 4, June, 2017
Volume 28, Number 5, August, 2017
Volume 28, Number 6, September, 2017
Volume 28, Number 7, November, 2017
Volume 28, Number 8, December, 2017
Volume 29, Number 1, January, 2018
Volume 29, Number 2, February, 2018
Volume 29, Number 3, April, 2018
Volume 29, Number 4, June, 2018


International Journal of Foundations of Computer Science (IJFCS)
Volume 1, Number 1, March, 1990

              Claire Kenyon and   
                  Andrew C. Yao   On Evaluating Boolean Functions with
                                  Unreliable Tests . . . . . . . . . . . . 1
                  A. Saoudi and   
               D. E. Muller and   
                   P. E. Schupp   On the Complexity of omega-Tree Sets and
                                  Nerode Theorem . . . . . . . . . . . . . 11
             V. S. Subrahmanian   A Ring-Theoretic Basis for Logic
                                  Programming  . . . . . . . . . . . . . . 23
              Marek A. Suchenek   Applications of Lyndon Homomorphism
                                  Theorems to the Theory of Minimal Models 49
                     Wei Wan-Di   On a Personnel Assignment Problem  . . . 61
            Franco P. Preparata   Planar Point Location Revisited  . . . . 71

International Journal of Foundations of Computer Science (IJFCS)
Volume 1, Number 2, June, 1990

           Emanuela Fachini and   
               Jozef Gruska and   
  Andrea Maggiolo Schettini and   
                         others   Simulation of Systolic Tree Automata on
                                  Trellis Automata . . . . . . . . . . . . 87
                G. Ausiello and   
                     M. Protasi   Limiting Polynomial Approximation of
                                  Complexity Classes . . . . . . . . . . . 111
         Sergio De Agostino and   
             Rossella Petreschi   Parallel Recognition Algorithms for
                                  Graphs with Restricted Neighbourhoods    123
                   Li Keqin and   
                  Cheng Kam-Hoi   Generalized First-Fit Algorithms in Two
                                  and Three Dimensions . . . . . . . . . . 131
            Roberto Barbuti and   
              Maurizio Martelli   Recognizing Non-Floundering Logic
                                  Programs and Goals . . . . . . . . . . . 151

International Journal of Foundations of Computer Science (IJFCS)
Volume 1, Number 3, September, 1990

               Franco Barbanera   Combining Term Rewriting and Type
                                  Assignment Systems . . . . . . . . . . . 165
            Daniel P. Bovet and   
            Miriam Di Ianni and   
            Pierluigi Crescenzi   Deadlock Prediction in the Case of
                                  Dynamic Routing  . . . . . . . . . . . . 185
             Danilo Bruschi and   
             Deborah Joseph and   
                     Paul Young   Strong Separations for the Boolean
                                  Hierarchy over RP  . . . . . . . . . . . 201
       Alessandra Cherubini and   
            Claudio Citrini and   
    Stefano Crespi Reghizzi and   
                         others   Breadth and Depth Grammars and Deque
                                  Automata . . . . . . . . . . . . . . . . 219
            Stefania Costantini   Semantics of a Metalogic Programming
                                  Language . . . . . . . . . . . . . . . . 233
            Moreno Falaschi and   
        Maurizio Gabbrielli and   
               Giorgio Levi and   
                         others   Nested Guarded Horn Clauses  . . . . . . 249
          Massimiliano Goldwurm   Some Limit Distributions in Analysis of
                                  Algorithms for Problems on Trace
                                  Languages  . . . . . . . . . . . . . . . 265
           Roberto Gorrieri and   
                  Ugo Montanari   Towards Hierarchical Description of
                                  Systems: a Proof System for Strong
                                  Prefixing  . . . . . . . . . . . . . . . 277
                   Erich Gradel   On the Notion of Linear Time
                                  Computability  . . . . . . . . . . . . . 295
                Filippo Mignosi   Sturmian Words and Ambiguous
                                  Context-Free Languages . . . . . . . . . 309
             Adolfo Piperno and   
                  Enrico Tronci   Regular Systems of Equations in
                                  lambda-Calculus  . . . . . . . . . . . . 325
                    G. Rosolini   About Modest Sets  . . . . . . . . . . . 341
                 A. Bertoni and   
                    C. Bohm and   
                    P. Miglioli   Introduction . . . . . . . . . . . . . . ??

International Journal of Foundations of Computer Science (IJFCS)
Volume 1, Number 4, December, 1990

              Robert McNaughton   The Development of Formal Language
                                  Theory Since 1956  . . . . . . . . . . . 355
          William M. Farmer and   
                Ronald J. Watro   Redex Capturing in Term Graph Rewriting  369
                   Hubert Comon   Solving Symbolic Ordering Constraints    387
             Manfred Droste and   
                  Rudiger Gobel   Universal Information Systems  . . . . . 413
           Jyrki Katajainen and   
                  Erkki Makinen   Tree Compression and Optimization with
                                  Applications . . . . . . . . . . . . . . 425
                A. P. Korah and   
                   M. R. Kaimal   Dynamic Optimal Binary Search Tree . . . 449
             V. S. Subrahmanian   A Ring-Theoretic Basis for Logic
                                  Programming  . . . . . . . . . . . . . . 465


International Journal of Foundations of Computer Science (IJFCS)
Volume 2, Number 1, March, 1991

               Martin Abadi and   
            Benjamin Pierce and   
                 Gordon Plotkin   Faithful Ideal Models for Recursive
                                  Polymorphic Types  . . . . . . . . . . . 1
                  Thomas Wilmes   Functional Production Systems Viewed as
                                  Grammars . . . . . . . . . . . . . . . . 23
             J. A. Bergstra and   
                    S. Mauw and   
                     F. Wiedijk   Uniform Algebraic Specifications of
                                  Finite Sets with Equality  . . . . . . . 43
                 Cai Jin-Yi and   
                  Merrick Furst   PSPACE Survives Constant-Width
                                  Bottlenecks  . . . . . . . . . . . . . . 67
                 Viktoria Zanko   #P-Completeness via Many-One Reductions  77

International Journal of Foundations of Computer Science (IJFCS)
Volume 2, Number 2, June, 1991

                  V. Arvind and   
                      S. Biswas   Edge-Deletion Graph Problems with
                                  First-Order Expressible Subgraph
                                  Properties . . . . . . . . . . . . . . . 83--100
              Tung Nguyen Thanh   A Relational Model of Demonic
                                  Nondeterministic Programs  . . . . . . . 101--132
             Hans L. Bodlaender   On the Complexity of Some Coloring Games 133--148
                Sachio Hirokawa   Principal Type Assignment to Lambda
                                  Terms  . . . . . . . . . . . . . . . . . 149--162
                  Tao Jiang and   
            Edward McDowell and   
                   B. Ravikumar   The Structure and Complexity of Minimal
                                  NFA's over a Unary Alphabet  . . . . . . 163

International Journal of Foundations of Computer Science (IJFCS)
Volume 2, Number 3, September, 1991

                  Dung T. Huynh   Efficient Detectors and Constructors for
                                  Simple Languages . . . . . . . . . . . . 183--206
             Chen Zhi-Zhong and   
                 Seinosuke Toda   On the Complexity of Computing Optimal
                                  Solutions  . . . . . . . . . . . . . . . 207--220
                   A. Monti and   
                     D. Parente   Systolic Tree with Base Automata . . . . 221--236
        Lane A. Hemachandra and   
                    Sanjay Jain   On the Limitations of Locally Robust
                                  Positive Reductions  . . . . . . . . . . 237--256
              Yves Metivier and   
                 Brigitte Rozoy   On the Star Operation in Free Partially
                                  Commutative Monoids  . . . . . . . . . . 257--266
               J. V. Tucker and   
                   J. I. Zucker   Projections of Semicomputable Relations
                                  on Abstract Data Types . . . . . . . . . 267

International Journal of Foundations of Computer Science (IJFCS)
Volume 2, Number 4, December, 1991

             N. Marti-Oliet and   
                    J. Meseguer   From Petri Nets to Linear Logic through
                                  Categories: a Survey . . . . . . . . . . 297--400
                   K. Inoue and   
                     A. Ito and   
                    I. Takanami   Alternating Turing Machines with
                                  Modified Accepting Structure . . . . . . 401--418
                       G. Panti   Solution of a Number Theoretic Problem
                                  Involving Knowledge  . . . . . . . . . . 419--424


International Journal of Foundations of Computer Science (IJFCS)
Volume 3, Number 1, March, 1992

                  S. Olariu and   
              J. L. Schwing and   
                       J. Zhang   Optimal Parallel Encoding and Decoding
                                  Algorithms for Trees . . . . . . . . . . 1--10
             S. D. Agostino and   
                   R. Petreschi   On PVsub chunk Operations and Matrogenic
                                  Graphs . . . . . . . . . . . . . . . . . 11--20
                      A. Saoudi   Pushdown Automata on Infinite Trees and
                                  Nondeterministic Context-Free Programs   21--40
              P. Campadelli and   
                    A. Morpurgo   Learning Classes of Linearly Separable
                                  Boolean Functions from Positive Examples 41--54
                  F. Luccio and   
           A. Pietracaprina and   
                       G. Pucci   Analysis and Implementation of Parallel
                                  Uniform Hashing  . . . . . . . . . . . . 55--64
               J. Hromkovic and   
                   K. Inoue and   
                   B. Rovan and   
                         others   On the Power of One-Way Synchronized
                                  Alternating Machines with Small Space    65--80
                      C. Marche   The Word Problem of ACD-Ground Theories
                                  is Undecidable . . . . . . . . . . . . . 81--92
                    J. Case and   
                    S. Jain and   
                      A. Sharma   On Learning Limiting Programs  . . . . . 93

International Journal of Foundations of Computer Science (IJFCS)
Volume 3, Number 2, June, 1992

                  K. Lodaya and   
               R. Ramanujam and   
              P. S. Thiagarajan   Temporal Logics for Communicating
                                  Sequential Agents: I . . . . . . . . . . 117--160
             A. P. Stolboushkin   On the Computing Power of Programs with
                                  Sets . . . . . . . . . . . . . . . . . . 161--180
                 A. Bertoni and   
                P. Massazza and   
                    N. Sabadini   Holonomic Generating Functions and
                                  Context Free Languages . . . . . . . . . 181--192
            W. van der Hoek and   
                J.-J. Ch. Meyer   Making Some Issues of Implicit Knowledge
                                  Explicit . . . . . . . . . . . . . . . . 193--224
                     F. J. Oles   When is a Category of Many-Sorted
                                  Algebras Cartesian Closed? . . . . . . . 225

International Journal of Foundations of Computer Science (IJFCS)
Volume 3, Number 3, September, 1992

                  A. Saoudi and   
               D. E. Muller and   
                   P. E. Schupp   Finite State Processes, $Z$-Temporal
                                  Logic and the Monadic Theory of the
                                  Integers . . . . . . . . . . . . . . . . 233--244
                S. L. Bloom and   
                        Z. Esik   Iteration Algebras . . . . . . . . . . . 245--302
                    P. Krishnan   A Calculus of Timed Communicating
                                  Systems  . . . . . . . . . . . . . . . . 303--322
                   Y. Cheng and   
                F. K. Hwang and   
             I. F. Akyildiz and   
                         others   Routing Algorithms for Double Loop
                                  Networks . . . . . . . . . . . . . . . . 323--332
                         D. Pym   A Unification Algorithm for the
                                  lambdaPi-Calculus  . . . . . . . . . . . 333--378
               S. Antonelli and   
                   S. Pelagatti   On the Complexity of the Mapping Problem
                                  for Massively Parallel Architectures . . 379

International Journal of Foundations of Computer Science (IJFCS)
Volume 3, Number 4, December, 1992

                      M. Droste   Concurrent Automata and Domains  . . . . 389--418
              F. Blanchet-Sadri   The Dot-Depth of a Generating Class of
                                  Aperiodic Monoids is Computable  . . . . 419--442
                      M. Mukund   Petri Nets and Step Transition Systems   443--478
                 T. Ottmann and   
                        D. Wood   Updating Binary Trees with Constant
                                  Linkage Cost . . . . . . . . . . . . . . 479--502


International Journal of Foundations of Computer Science (IJFCS)
Volume 4, Number 1, March, 1993

                  J. Dassow and   
                  G. P\uaun and   
                     A. Salomaa   Grammars Based on Patterns . . . . . . . 1--14
               P. Crescenzi and   
                   R. Silvestri   Average Measure, Descriptive Complexity
                                  and Approximation of Maximization
                                  Problems . . . . . . . . . . . . . . . . 15--30
                     W. Penczek   Temporal Logics for Trace Systems: On
                                  Automated Verification . . . . . . . . . 31--68
           P. Kirschenhofer and   
               H. Prodinger and   
                 W. Szpankowski   Multidimensional Digital Searching and
                                  Some New Parameters in Tries . . . . . . 69--84
                  A. Moffat and   
                   O. Petersson   Historical Searching . . . . . . . . . . 85--98
                S. L. Bloom and   
                        Z. Esik   Iteration Algebras . . . . . . . . . . . 99

International Journal of Foundations of Computer Science (IJFCS)
Volume 4, Number 2, June, 1993

               S.-I. Nakano and   
                   T. Nishizeki   Scheduling File Transfers Under Port and
                                  Channel Constraints  . . . . . . . . . . 101--116
                  I. A. Stewart   On Two Approximation Algorithms for the
                                  Clique Problem . . . . . . . . . . . . . 117--134
               O. H. Ibarra and   
                   T. Jiang and   
                    N. Tran and   
                         others   On the Equivalence of Two-Way Pushdown
                                  Automata and Counter Machines Over
                                  Bounded Languages  . . . . . . . . . . . 135--146
                M. T. Dickerson   General Polynomial Decomposition and the
                                  $s$-$1$-Decomposition are NP-Hard  . . . 147--156
                   S. Lange and   
                    T. Zeugmann   Learning Recursive Languages With a
                                  Bounded Number of Mind Changes . . . . . 157--178
                    K. Diks and   
                 O. Garrido and   
                      A. Lingas   Parallel Algorithms for Finding Maximal
                                  $k$-Dependent Sets and Maximal
                                  $f$-Matchings  . . . . . . . . . . . . . 179

International Journal of Foundations of Computer Science (IJFCS)
Volume 4, Number 3, September, 1993

                  S. Olariu and   
                  I. A. Stewart   A New Characterization of Unbreakable
                                  Graphs . . . . . . . . . . . . . . . . . 193--196
             F. Kamareddine and   
                   R. Nederpelt   On Stepwise Explicit Substitution  . . . 197--240
                  A. P. Lisitsa   Complexity of Universal Circumscription  241--244
         L. A. Hemaspaandra and   
                    S. Jain and   
             N. K. Vereshchagin   Banishing Robust Turing Completeness . . 245--266
                 B. F. Melnikov   The Equality Condition for Infinite
                                  Catenations of Two Sets of Finite Words  267

International Journal of Foundations of Computer Science (IJFCS)
Volume 4, Number 4, December, 1993

                      K. Jansen   Scheduling of Incompatible Jobs on
                                  Unrelated Machines . . . . . . . . . . . 275--292
                 H. Vollmer and   
                   K. W. Wagner   The Complexity of Finding Middle
                                  Elements . . . . . . . . . . . . . . . . 293--308
                  T. W. Lai and   
                        D. Wood   A Top-Down Updating Algorithm for
                                  Weight-Balanced Trees  . . . . . . . . . 309--324
                A. Symvonis and   
                   S. Tragoudas   Searching a Pseudo $3$-Sided Solid
                                  Orthoconvex Grid . . . . . . . . . . . . 325--354
              M. W. Vincent and   
                  B. Srinivasan   Redundancy and the Justification for
                                  Fourth Normal Form in Relational
                                  Databases  . . . . . . . . . . . . . . . 355--366


International Journal of Foundations of Computer Science (IJFCS)
Volume 5, Number 3/4, 1994

                      J.-Y. Cai   Computing Jordan Normal Forms Exactly
                                  for Commuting Matrices in Polynomial
                                  Time . . . . . . . . . . . . . . . . . . ??
                   P. Duris and   
                 J. D. P. Rolim   Conjunctive and Disjunctive
                                  Reducibilities to Sparse and Tally Sets
                                  Revisited  . . . . . . . . . . . . . . . ??
           K. L. Leiberherr and   
                        C. Xiao   Customizing Adaptive Software to
                                  Object-Oriented Software Using Grammars  ??
             J. Y.-T. Leung and   
                    V. K. M. Yu   Heuristic for Minimizing the Number of
                                  Late Jobs on Two Processors  . . . . . . ??
             R. Maelbrancke and   
                      H. Olivie   Dynamic Tree Rebalancing Using Recurrent
                                  Rotations  . . . . . . . . . . . . . . . ??
                     M. Ogihara   On Serializable Languages  . . . . . . . ??
               J. L. Trahan and   
                   S. Vedantham   Analysis of PRAM Instruction Sets from a
                                  Log Cost Perspective . . . . . . . . . . ??
                  H.-C. Yen and   
                 B.-Y. Wang and   
                     M.-S. Yang   Some Complexity Results for Rings of
                                  Petri Nets . . . . . . . . . . . . . . . ??


International Journal of Foundations of Computer Science (IJFCS)
Volume 6, Number 1, 1995

          R. A. Baeza-Yates and   
                  P. V. Poblete   Higher-Order Analysis of $2$-$3$ Trees   1
             I. K. Musikaev and   
                 M. A. Taitslin   Flat Backtracking Prolog for Databases:
                                  a Formal Semantics, the Computational
                                  Complexity and the Expressibility  . . . 11
                J. Hintikka and   
                       G. Sandu   What is the Logic of Parallel
                                  Processing?  . . . . . . . . . . . . . . 27
               M. Monserrat and   
                F. Rossello and   
                     J. Torrens   When is a Category of Many-Sorted
                                  Partial Algebras Cartesian-Closed? . . . 51
            J. Haralambides and   
                   S. Tragoudas   Bipartitioning into Overlapping Sets . . 67
                        S. Jain   An Infinite Class of Functions
                                  Identifiable Using Minimal Programs in
                                  All Kolmogorov Numberings  . . . . . . . 89

International Journal of Foundations of Computer Science (IJFCS)
Volume 6, Number 2, 1995

                S. L. Bloom and   
                        Z. Esik   Some Equational Laws of Initiality in
                                  2CCC's . . . . . . . . . . . . . . . . . 95
                 P. Besnard and   
                      J. Kohlas   Evidence Theory Based on General
                                  Consequence Relations  . . . . . . . . . 119
                  V. Arvind and   
                 J. Koebler and   
                     R. Schuler   On Helping and Interactive Proof Systems 137
                A. Clementi and   
                    M. Di Ianni   Optimum Schedule Problems in Store and
                                  Forward Networks . . . . . . . . . . . . 155
                    W. Peng and   
                     S. P. Iyer   A New Type of Pushdown Automata on
                                  Infinite Trees . . . . . . . . . . . . . 169

International Journal of Foundations of Computer Science (IJFCS)
Volume 6, Number 3, 1995

                 S. Hayashi and   
                   S. Kobayashi   A New Formalization of Feferman's System
                                  of Functions and Classes and Its
                                  Relation to Frege Structure  . . . . . . 187
                    Y. Kameyama   A Type-Free Theory of Half-Monotone
                                  Inductive Definitions  . . . . . . . . . 203
                    S. F. Smith   Hybrid Partial-Total Type Theory . . . . 235
                   I. Mason and   
                     C. Talcott   Reasoning About Object Systems in VTLoE  265
                      M. Beeson   Using Nonstandard Analysis to Ensure the
                                  Correctness of Symbolic Computations . . 299

International Journal of Foundations of Computer Science (IJFCS)
Volume 6, Number 4, 1995

                      W. Szwast   A Note on the Asymptotic Probabilities
                                  of Existential Second-Order Minimal
                                  Goedel Sentences with Equality . . . . . 339
                  I. Castellani   Observing Distribution in Processes:
                                  Static and Dynamic Localities  . . . . . 353
                   J.-C. Dubacq   How to Simulate Turing Machines by
                                  Invertible One-Dimensional Cellular
                                  Automata . . . . . . . . . . . . . . . . 395
         L. A. Hemaspaandra and   
                   A. Hoene and   
                 A. V. Naik and   
                         others   Nondeterministically Selective Sets  . . 403
                    N. Raja and   
             R. K. Shyamasundar   The Quine-Bernays Combinatory Calculus   417
                   A. Slobodova   On the Power of One-Way Globally
                                  Deterministic Synchronized Alternating
                                  Turing Machines and Multihead Automata   431


International Journal of Foundations of Computer Science (IJFCS)
Volume 7, Number 1, 1996

                 D. Sankoff and   
                G. Sundaram and   
                  J. Kececioglu   Steiner Points in the Space of Genome
                                  Rearrangements . . . . . . . . . . . . . 1
                R. Agarwala and   
              D. Fernandez-Baca   Simple-Algorithms for Perfect Phylogeny
                                  and Triangulating Colored Graphs . . . . 11
                  M. Fuerer and   
                      W. Miller   Alignment-to-Alignment Editing with
                                  ``Move Gap'' Operations  . . . . . . . . 23
                K.-Z. Zhang and   
              J. T. L. Wang and   
                      D. Shasha   On the Editing Distance Between
                                  Undirected Acyclic Graphs  . . . . . . . 43
                   L. Hanks and   
               R. K. Cytron and   
                     W. Gillett   On Finding Topologically Valid Matchings
                                  in Restriction-Fragment Maps . . . . . . 59
                A. M. Duval and   
                    W. F. Smyth   Covering a Circular String with
                                  Substrings of Fixed Length . . . . . . . 87

International Journal of Foundations of Computer Science (IJFCS)
Volume 7, Number 2, 1996

         H. Ripphausen-Lipa and   
                  D. Wagner and   
                       K. Weihe   Linear-Time Algorithms for Disjoint
                                  Two-Face Paths Problems in Planar Graphs 95
                       T. Kloks   Treewidth of Circle Graphs . . . . . . . 111
                     G. Das and   
                P. J. Heffernan   Constructing Degree-$3$ Spanners with
                                  Other Sparseness Properties  . . . . . . 121
                   R. Fleischer   A Simple Balanced Search Tree with O(1)
                                  Worst-Case Update Time . . . . . . . . . 137
                    K. Ruohonen   An Effective Cauchy-Peano Existence
                                  Theorem for Unique Solutions . . . . . . 151
                    R. Greenlaw   Subtree Isomorphism is in DLOG for
                                  Nested Trees . . . . . . . . . . . . . . 161
               K. S. Larsen and   
                   R. Fagerberg   Efficient Rebalancing of B-Trees with
                                  Relaxed Balance  . . . . . . . . . . . . 169

International Journal of Foundations of Computer Science (IJFCS)
Volume 7, Number 3, 1996

                      J. Viksna   Inductive Inference of Limiting Programs
                                  with Bounded Number of Mind Changes  . . 187
                R. Orlandic and   
                  H. M. Mahmoud   Storage Overhead of O-Trees, B-Trees and
                                  Prefix B-Trees: a Comparative Analysis   209
                    L. Chen and   
                      R. Schott   Optimal Operations on Red-Black Trees    227
                    S. Caporaso   Safe Turing Machines, Grzegorczyk
                                  Classes and Polytime . . . . . . . . . . 241
             L. Breveglieri and   
               A. Cherubini and   
                 C. Citrini and   
                         others   Multi-Push-Down Languages and Grammars   253
                   H. Prodinger   Depth and Path Length of Heap Ordered
                                  Trees  . . . . . . . . . . . . . . . . . 293

International Journal of Foundations of Computer Science (IJFCS)
Volume 7, Number 4, 1996

                     P.-K. Wong   An Algorithm for Finding a Maximum Cycle
                                  of Bipartite Graphs with Large Degrees   301
               S. Kobayashi and   
                    T. Yokomori   Families of Noncounting Languages and
                                  Their Learnability from Positive Data    309
                  I. I. Macarie   A Note of Multihead Finite-State
                                  Automata . . . . . . . . . . . . . . . . 329
                 M. Agrawal and   
                   S. Venkatesh   On the Isomorphism Conjecture for
                                  $2$-DFA Reductions . . . . . . . . . . . 339
             W. F. Klostermeyer   Scheduling Two Salesmen in a Network . . 353
                    J. A. Plaza   On the Propositional SLDNF-Resolution    359


International Journal of Foundations of Computer Science (IJFCS)
Volume 8, Number 1, March, 1997

         Alexandru Mateescu and   
         Grzegorz Rozenberg and   
                   Arto Salomaa   Geometric Transformations of Language
                                  Families: The Power of Symmetry  . . . . 1
              Carl H. Smith and   
              Rolf Wiehagen and   
                Thomas Zeugmann   Classifying Predicates and Languages . . 15--41
               Lucian Finta and   
                       Zhen Liu   Complexity of Task Graph Scheduling with
                                  Fixed Communication Capacity . . . . . . 43
          Sorina Dumitrescu and   
             Georghe P\uaun and   
                   Arto Salomaa   Pattern Languages Versus Parallel
                                  Communicating Grammar Systems  . . . . . 67
            Oscar H. Ibarra and   
             Pedro C. Diniz and   
               Martin C. Rinard   On the Complexity of Commutativity
                                  Analysis . . . . . . . . . . . . . . . . 81
       Lane A. Hemaspaandra and   
                   Zhigen Jiang   Logspace Reducibility: Models and
                                  Equivalences . . . . . . . . . . . . . . 95

International Journal of Foundations of Computer Science (IJFCS)
Volume 8, Number 2, June, 1997

        Jean-Claude Bermond and   
          H. A. Harutyunyan and   
             A. L. Liestman and   
                         others   A Note on the Dimensionality of Modified
                                  Knödel Graphs . . . . . . . . . . . . . . 109
         Evangelos Kranakis and   
              Danny Krizanc and   
                   Andrzej Pelc   Hop-Congestion Trade-Offs for High-Speed
                                  Networks . . . . . . . . . . . . . . . . 117
              Shuo-Cheng Hu and   
                Chang-Biau Yang   Fault Tolerance on Star Graphs . . . . . 127
     Pascal Berthomé and   
                Afonso Ferreira   Communication Issues in Parallel Systems
                                  with Optical Interconnections  . . . . . 143
               Sajal K. Das and   
            Dirk H. Hohndel and   
            Maximilian Ibel and   
          Sabine R. Öhring   Efficient Communication in Folded
                                  Petersen Networks  . . . . . . . . . . . 163
                     Jie Wu and   
                   Haifeng Qian   Multitriangle: a Constant Node Degree
                                  Interconnection Network  . . . . . . . . 187
                  C. Calvin and   
                L. Colombet and   
                   P. Michallon   Methods to Overlap Communications in
                                  Parallel Numerical Algorithms  . . . . . 211

International Journal of Foundations of Computer Science (IJFCS)
Volume 8, Number 3, September, 1997

                      H. K. Dai   The Complexity of Deciding Strictly
                                  Non-Blocking Concentration and
                                  Generalized-Concentration Properties . . 237
            Young Wook Keum and   
                   Hwakyung Rim   Design and Analysis of the Symmetric
                                  Banyan Network (SBN): a Min with High
                                  Performance and High Fault Tolerance . . 253
                  Jop F. Sibeyn   Routing on Triangles, Tori and
                                  Honeycombs . . . . . . . . . . . . . . . 269
              Marc Baumslag and   
                 Bojana Obrenic   Index-Shuffle Graphs . . . . . . . . . . 289
                 Xingde Jia and   
                     Weidong Su   Triple Loop Networks with Minimal
                                  Transmission Delay . . . . . . . . . . . 305
                     A. Heirich   A Scalable Diffusion Algorithm for
                                  Dynamic Mapping and Load Balancing on
                                  Networks of Arbitrary Topology . . . . . 329
            Burkhard Monien and   
              Ralf Diekmann and   
           Reinhard Lüling   The Construction of Large Scale
                                  Reconfigurable Parallel Computing
                                  Systems (The Architecture of the SC320)  347

International Journal of Foundations of Computer Science (IJFCS)
Volume 8, Number 4, December, 1997

           Padmanabhan Krishnan   A Process Algebraic Approach to Time
                                  Granularity Semantics  . . . . . . . . . 363
                    Twan Basten   Parsing Partially Ordered Multisets  . . 379
               Mark A. Changizi   Learning with Natural Imprecision  . . . 409
                   Bruno Martin   Embedding Torus Automata into a Ring of
                                  Automata . . . . . . . . . . . . . . . . 425
                      V. Arvind   Constructivizing Membership Proofs in
                                  Complexity Classes . . . . . . . . . . . 433
          Glenn K. Manacher and   
             Terrance A. Mankus   Finding a Maximum Clique in a Set of
                                  Proper Circular Arcs in Time $O(n)$ with
                                  Applications . . . . . . . . . . . . . . 443
                      Anonymous   Author Index Volume 8 (1997) . . . . . . 469


International Journal of Foundations of Computer Science (IJFCS)
Volume 9, Number 1, March, 1998

                   D. Frank Hsu   Special Issue on Interconnection
                                  Networks --- Editors' Foreword . . . . . 1
                  Satoshi Okawa   The Permutational Graph: a New Network
                                  Topology . . . . . . . . . . . . . . . . 3
             Luz R. Nochefranca   The diameter and Hamiltonian cycle of
                                  the generalized de Bruijn graphs
                                  $\mbox{UG}_b(n,n(n+1))$  . . . . . . . . 13
          L. R. Nochefrance and   
                       P. W. Sy   The Diameter and Hamiltonian Cycle of
                                  the Generalized De Bruijn Graphs UGB$(n,
                                  n(n+1))$ . . . . . . . . . . . . . . . . 13
          Thomas J. Cortina and   
                     Zhi-Wei Xu   The Cube-Of-Rings Interconnection
                                  Network  . . . . . . . . . . . . . . . . 25
              Ayan Banerjee and   
   Emmanouel (Manos) Varvarigos   A Dynamic Scheduling Communication
                                  Protocol and Its Analysis for Hypercube
                                  Networks . . . . . . . . . . . . . . . . 39
             A. L. Liestman and   
                 J. Opatrny and   
                    M. Zaragoza   Network Properties of Double and Triple
                                  Fixed Step Graphs  . . . . . . . . . . . 57
                Guihai Chen and   
              Francis C. M. Lau   Shuffle-Ring: a New Constant-Degree
                                  Network  . . . . . . . . . . . . . . . . 77
                Sandy Pavel and   
                   Selim G. Akl   Integer Sorting and Routing in Arrays
                                  with Reconfigurable Optical Buses  . . . 99

International Journal of Foundations of Computer Science (IJFCS)
Volume 9, Number 2, June, 1998

    Miltos D. Grammatikakis and   
                Eric Fleury and   
                   Miro Kraetzl   Continuous Routing in Packet Switches    121
               Roman Garcia and   
                     Jose Duato   Suboptimal-Optimal Routing for LAN
                                  Internetworking Using Transparent
                                  Bridges  . . . . . . . . . . . . . . . . 139
           Fabrizio Petrini and   
                Marco Vanneschi   Performance Analysis of Wormhole Routed
                                  $K$-Ary $N$-Trees  . . . . . . . . . . . 157
            Paola Flocchini and   
                 Nicola Santoro   Topological Constraints for Sense of
                                  Direction  . . . . . . . . . . . . . . . 179
    Sanguthevar Rajasekaran and   
             Theodore McKendall   Permutation Routing and Sorting on the
                                  Reconfigurable Mesh  . . . . . . . . . . 199
         Claude G. Diderich and   
                   Marc Gengler   An Extended Dimension Order Token
                                  Distribution Algorithm on $k$-Ary
                                  $d$-Cubes and Its Complexity . . . . . . 213
             Wei-Kuo Chiang and   
                 Rong-Jaye Chen   Topological Properties of the
                                  $(n,k)$-Star Graph . . . . . . . . . . . 235

International Journal of Foundations of Computer Science (IJFCS)
Volume 9, Number 3, 1998

      Hervé Le Verge and   
                 Yannic Saouter   New Results on Computability of
                                  Recurrence Equations . . . . . . . . . . 249
  Hans-Jörg Burtschick and   
                     H. Vollmer   Lindström Quantifiers and Leaf Language
                                  Definability . . . . . . . . . . . . . . 277
             Manfred Droste and   
                 Dietrich Kuske   Recognizable and Logically Definable
                                  Languages of Infinite Computations In
                                  Concurrent Automata  . . . . . . . . . . 295
                    Sanjay Jain   Minimal Concept Identification and
                                  Reliability  . . . . . . . . . . . . . . 315
            Fairouz Kamareddine   The Soundness of Explicit Substitution
                                  with Nameless Variables  . . . . . . . . 321

International Journal of Foundations of Computer Science (IJFCS)
Volume 9, Number 4, December, 1998

             Peter Cappello and   
          Ömer Egecio\uglu   Processor Lower Bound Formulas for Array
                                  Computations and Parametric Diophantine
                                  Systems  . . . . . . . . . . . . . . . . 351
                Doowon Paik and   
             Sudhakar Reddy and   
                   Sartaj Sahni   Vertex Splitting in DAGs and
                                  Applications to Partial Scan Designs and
                                  Lossy Circuits . . . . . . . . . . . . . 377
                  Kim S. Larsen   Sort Order Problems in Relational
                                  Databases  . . . . . . . . . . . . . . . 399
               M. P. A. Sellink   On the Conservativity of Leibniz
                                  Equality . . . . . . . . . . . . . . . . 431
                      Anonymous   Author Index Volume 9 (1998) . . . . . . 455


International Journal of Foundations of Computer Science (IJFCS)
Volume 10, Number 1, 1999

                     S. Cho and   
                       S. Sahni   Mergeable Double-Ended Priority Queues   1
                  G. Sajith and   
                      S. Saxena   Parallel Vertex Colouring of Interval
                                  Graphs . . . . . . . . . . . . . . . . . 19
                  M. H. Karaata   A Self-Stabilizing Algorithm for Finding
                                  Articulation Points  . . . . . . . . . . 33
                   Y. Chung and   
                    K. Park and   
                         Y. Cho   Parallel Maximum Matching Algorithms in
                                  Interval Graphs  . . . . . . . . . . . . 47
                  J. Dassow and   
                  H. Fernau and   
                      G. P\uaun   On the Leftmost Derivation in Matrix
                                  Grammars . . . . . . . . . . . . . . . . 61
            K. Saraç and   
        Ö. Egecio\uglu and   
                   A. El Abbadi   DFT Techniques for Size Estimation of
                                  Database Join Operations . . . . . . . . 81
                 F. Roussel and   
                    I. Rusu and   
                   H. Thuillier   On Graphs with Limited Number of
                                  $P_4$-Partners . . . . . . . . . . . . . 103

International Journal of Foundations of Computer Science (IJFCS)
Volume 10, Number 2, 1999

                  K. Nakano and   
                      S. Olariu   Guest Editors' Introduction  . . . . . . 123
            Florian Roussel and   
                     Irena Rusu   Holes and Dominoes in Meyniel Graphs . . 127
                   M. Habib and   
                    C. Paul and   
                     L. Viennot   Partition Refinement Techniques: An
                                  Interesting Algorithmic Tool Kit . . . . 147
                   S. Isobe and   
                    X. Zhou and   
                   T. Nishizeki   A Polynomial-Time Algorithm for Finding
                                  Total Colorings of Partial $k$-Trees . . 171
                   K. Miura and   
               D. Takahashi and   
               S. I. Nakano and   
                   T. Nishizeki   A Linear-Time Algorithm to Find Four
                                  Independent Spanning Trees in Four
                                  Connected Planar Graphs  . . . . . . . . 195
               S. S. H. Tse and   
                   F. C. M. Lau   On the Complexity of Some Adaptive
                                  Polling Algorithms in General Networks   211
             M. Holzrichter and   
                    S. Oliveira   A Graph Based Davidson Algorithm for the
                                  Graph Partitioning Problem . . . . . . . 223

International Journal of Foundations of Computer Science (IJFCS)
Volume 10, Number 3, 1999

E. De Queiros Vieira Martins and   
           M. M. B. Pascoal and   
            J. L. E. Dos Santos   Deviation Algorithms for Ranking
                                  Shortest Paths . . . . . . . . . . . . . 247--262
        E. D. Q. V. Martins and   
           M. M. B. Pascoal and   
             J. L. E. D. Santos   Deviation Algorithms for Ranking
                                  Shortest Paths . . . . . . . . . . . . . 247
         L. A. Hemaspaandra and   
                  H. Hempel and   
                    G. Wechsung   Self-Specifying Machines . . . . . . . . 263--276
              T. Calamoneri and   
                   R. Petreschi   Optimal Layout of Trivalent Cayley
                                  Interconnection Networks . . . . . . . . 277--288
             M. C. Azizoglu and   
          Ö. E\ugecio\uglu   The Isoperimetric Number of
                                  $d$-Dimensional $k$-Ary Arrays . . . . . 289--300
                   K. S. Larsen   On Grouping in Relational Algebra  . . . 301--312
               A. W. Krings and   
                        M. Dror   Real-Time Dispatching: Scheduling
                                  Stability and Precedence . . . . . . . . 313--328
             J. A. Makowsky and   
                      U. Rotics   On the Clique-Width of Graphs with Few
                                  $P_4$'s  . . . . . . . . . . . . . . . . 329--348
                   S. Greco and   
                 D. Sacc\`a and   
                     C. Zaniolo   Grammars and Automata to Optimize Chain
                                  Logic Queries  . . . . . . . . . . . . . 349--372

International Journal of Foundations of Computer Science (IJFCS)
Volume 10, Number 4, 1999

                D. Andresen and   
                        T. Yang   Preface  . . . . . . . . . . . . . . . . 373
                H. Mongelli and   
                     S. W. Song   Parallel Range Minima on Coarse Grained
                                  Multicomputers . . . . . . . . . . . . . 375--390
                H. Mongelli and   
                     S. W. Song   Part 1 (Irregular '99) . . . . . . . . . 375
               K. T. Herley and   
           A. Pietracaprina and   
                       G. Pucci   Deterministic Branch-and-Bound on
                                  Distributed Memory Machines  . . . . . . 391--404
                  C. Boeres and   
              A. Nascimento and   
               V. E. F. Rebello   Cluster-Based Task Scheduling for the
                                  \em LogP Model . . . . . . . . . . . . . 405--424
                  F. Voisin and   
                   G. R. Perrin   Sparse Computation with PEI  . . . . . . 425--442
             K. Krithivasan and   
                M. S. Balan and   
                      P. Harsha   Distributed Processing in Automata . . . 443--464
             K. Krithivasan and   
                N. S. Balan and   
                      P. Harsha   Part 2 (Regular Papers)  . . . . . . . . 443
              A. P. Sprague and   
                     T. Takaoka   $O(1)$ Query Time Algorithm for All
                                  Pairs Shortest Distances on Interval
                                  Graphs . . . . . . . . . . . . . . . . . 465--472
                      R. Uehara   A Measure for the Lexicographically
                                  First Maximal Independent Set Problem
                                  and its Limits . . . . . . . . . . . . . 473--482
                     T. Okadome   Simple Flat Languages: a Learnable Class
                                  in the Limit from Positive Data  . . . . 483--502
             L. G\kasieniec and   
                E. Kranakis and   
                 D. Krizanc and   
                        A. Pelc   Minimizing Congestion of Layouts for ATM
                                  Networks with Faulty Links . . . . . . . 503--512
              J. L. Fouquet and   
             V. Giakoumakis and   
                 J. M. Vanherpe   Bipartite Graphs Totally Decomposable by
                                  Canonical Decomposition  . . . . . . . . 513--534
                  R. Beigel and   
                  A. Bernasconi   A Note on the Polynomial Representation
                                  of Boolean Functions Over $\mbox{GF}(2)$ 535--542
                      Anonymous   Author Index . . . . . . . . . . . . . . 545


International Journal of Foundations of Computer Science (IJFCS)
Volume 11, Number 1, 2000

                  J. Hsiang and   
                       A. Ohori   Special Issue on Advances in Computing
                                  Science --- Asian '98  . . . . . . . . . 1
               H. Ganzinger and   
              F. Jacquemard and   
                      M. Veanes   Rigid Reachability, The Non-Symmetric
                                  Form of Rigid E-Unification  . . . . . . 3--28
               H. Ganzinger and   
              F. Jacquemard and   
                      M. Veanes   Part 1 (Asian '98) . . . . . . . . . . . 3
             M. Müller and   
                   S. Nishimura   Type Inference for First-Class Messages
                                  with Feature Constraints . . . . . . . . 29--64
                   M. Hashimoto   First-Class Contexts in ML . . . . . . . 65--88
                       I. Ogata   Constructive Classical Logic as
                                  CPS-Calculus . . . . . . . . . . . . . . 89--112
                     L. Roversi   Light Affine Logic as a Programming
                                  Language: a First Contribution . . . . . 113--152
                 Z.-H. Yang and   
                  C.-Z. Sun and   
                    Y. Miao and   
                  A. Sattar and   
                     Y. Y. Yang   Guaranteed Mutually Consistent
                                  Checkpointing in Distributed
                                  Computations . . . . . . . . . . . . . . 153--166
                 Z.-H. Yang and   
                  C.-Z. Sun and   
                    Y. Miao and   
                  A. Sattar and   
                     Y. Y. Yang   Part 2 (Regular Papers)  . . . . . . . . 153
                      G. P\uaun   Computing with Membranes ($P$ Systems):
                                  a Variant  . . . . . . . . . . . . . . . 167--182
                A. L. Rosenberg   Guidelines for Data-Parallel
                                  Cycle-Stealing in Networks of
                                  Workstations II: On Maximizing
                                  Guaranteed Output  . . . . . . . . . . . 183--204

International Journal of Foundations of Computer Science (IJFCS)
Volume 11, Number 2, 2000

             S. Rajasekaran and   
                    S. K. Sahni   Special Issue on Randomized Computing    205--206
                          K. Li   A Method for Evaluating the Expected
                                  Load of Dynamic Tree Embeddings in
                                  Hypercubes . . . . . . . . . . . . . . . 207--230
                          K. Li   Part 1 (Randomized Computing)  . . . . . 207
            N. R. Mahapatra and   
                        S. Dutt   Random Seeking: a General, Efficient,
                                  and Informed Randomized Scheme for
                                  Dynamic Load Balancing . . . . . . . . . 231--246
             S. Nikoletseas and   
                   K. Palem and   
                P. Spirakis and   
                        M. Yung   Connectivity Properties in Random
                                  Regular Graphs with Edge Faults  . . . . 247--262
                   Hung-Min Sun   On the Dealer's Randomness Required in
                                  Perfect Secret Sharing Schemes with
                                  Access Structures of Constant Rank . . . 263--282
         R. K. Shyamasundar and   
                      S. Ramesh   Languages for Reactive Specifications:
                                  Synchrony Vs Asynchrony  . . . . . . . . 283--314
         R. K. Shyamasundar and   
                      S. Ramesh   Part 2 (Regular Papers)  . . . . . . . . 283
                  H. Hempel and   
                    G. Wechsung   The Operators min and max on the
                                  Polynomial Hierarchy . . . . . . . . . . 315--342
                 H. Zantema and   
               H. L. Bodlaender   Finding Small Equivalent Decision Trees
                                  is Hard  . . . . . . . . . . . . . . . . 343--354

International Journal of Foundations of Computer Science (IJFCS)
Volume 11, Number 3, 2000

   M. M. Halldórsson and   
       J. Kratochvíl and   
                    J. A. Telle   Mod-$2$ Independence and Domination in
                                  Graphs . . . . . . . . . . . . . . . . . 355--364
                L. Perkovic and   
                        B. Reed   An Improved Algorithm for Finding Tree
                                  Decompositions of Small Width  . . . . . 365--372
              Ö. Johansson   NLC$_2$-Decomposition in Polynomial Time 373--396
                 Anne Berry and   
           Jean-Paul Bordat and   
                  Olivier Cogis   Generating All the Minimal Separators of
                                  a Graph  . . . . . . . . . . . . . . . . 397--404
               A. Accornero and   
                  M. Ancona and   
                      S. Varini   All Separating Triangles in a Plane
                                  Graph Can Be Optimally ``Broken'' in
                                  Polynomial Time  . . . . . . . . . . . . 405--422
             M. C. Golumbic and   
                      U. Rotics   On the Clique-Width of Some Perfect
                                  Graph Classes  . . . . . . . . . . . . . 423--444
               N. Nishimura and   
                   P. Ragde and   
                 D. M. Thilikos   Finding Smallest Supertrees Under Minor
                                  Containment  . . . . . . . . . . . . . . 445--466
                 A. Liebers and   
                  D. Wagner and   
                       K. Weihe   On the Hardness of Recognizing Bundles
                                  in Time Table Graphs . . . . . . . . . . 467--484
                     S. Cho and   
                       S. Sahni   A New Weight Balanced Binary Search Tree 485--514
                     S. Cho and   
                       S. Sahni   Part 2 (Regular Papers)  . . . . . . . . 485
                     T. Okadome   Some Sufficient Conditions of
                                  Learnability in the Limit From Positive
                                  Data . . . . . . . . . . . . . . . . . . 515--524

International Journal of Foundations of Computer Science (IJFCS)
Volume 11, Number 4, 2000

                   S. Kosub and   
                 H. Schmitz and   
                     H. Vollmer   Uniform Characterizations of Complexity
                                  Classes of Functions . . . . . . . . . . 525--552
            A. G. Bourgeois and   
                   J. L. Trahan   Relating Two-Dimensional Reconfigurable
                                  Meshes with Optically Pipelined Buses    553--572
                    G. Dong and   
                       L. Zhang   Separating Auxiliary Arity Hierarchy of
                                  First-Order Incremental Evaluation
                                  Systems Using $(3k+1)$-ary Input
                                  Relations  . . . . . . . . . . . . . . . 573--578
               P. Bonizzoni and   
               G. D. Vedova and   
                       G. Mauri   Approximating the Maximum Isomorphic
                                  Agreement Subtree is Hard  . . . . . . . 579--590
              R. van der Meyden   Predicate Boundedness of Linear Monadic
                                  Datalog is in PSPACE . . . . . . . . . . 591--614
             J. Köbler and   
                     W. Lindner   Oracles in $\Sigma^p_2$ are Sufficient
                                  for Exact Learning . . . . . . . . . . . 615--632
     E. Csuhaj-Varjú and   
      C. Martín-Vide and   
                 V. Mitrana and   
                      G. Vaszil   Parallel Communicating Pushdown Automata
                                  Systems  . . . . . . . . . . . . . . . . 633--650
                      Anonymous   Author Index . . . . . . . . . . . . . . 651


International Journal of Foundations of Computer Science (IJFCS)
Volume 12, Number 1, 2001

                      Anonymous   Special Issue on Functional and Logic
                                  Programming --- Part 1 . . . . . . . . . 1
                        Preface   Special Issue on Functional and Logic
                                  Programming --- Part 1 . . . . . . . . . 1
           Masako Takahashi and   
                    M. Sato and   
                      Y. Toyama   Lambda-Representable Functions Over Term
                                  Algebras . . . . . . . . . . . . . . . . 3--30 (or 3--29??)
           Yasuyuki Tsukada and   
                    M. Sato and   
                      Y. Toyama   Martin-Löf's Type Theory as an Open-Ended
                                  Framework  . . . . . . . . . . . . . . . 31--67 (or 31--68??)
    Peter Borovanský and   
            Claude Kirchner and   
   Hél\`ene Kirchner and   
                  C. Ringeissen   Rewriting with Strategies in ELAN: a
                                  Functional Semantics . . . . . . . . . . 69--95 (or 69--96??)
        Edgar F. A. Lederer and   
            Romeo A. Dumitrescu   Automatic Result Verification by
                                  Complete Run-Time Checking of
                                  Computations . . . . . . . . . . . . . . 97--124
                      Anonymous   Preface  . . . . . . . . . . . . . . . . ??

International Journal of Foundations of Computer Science (IJFCS)
Volume 12, Number 2, 2001

                 Ralf Hinze and   
                    M. Sato and   
                      Y. Toyama   Prolog's Control Constructs in a
                                  Functional Setting --- Axioms and
                                  Implementation . . . . . . . . . . . . . 125--170
                       R. Hinze   Special Issue on Functional and Logic
                                  Programming --- Part 2 . . . . . . . . . 125
             Sergei Abramov and   
              Robert Glück   From Standard to Non-Standard Semantics
                                  by Semantics Modifiers . . . . . . . . . 171--211 (or 171--212??)
               Takafumi Sakurai   Categorical Model Construction for
                                  Proving Syntactic Properties . . . . . . 213--244

International Journal of Foundations of Computer Science (IJFCS)
Volume 12, Number 3, 2001

               Michael A. Palis   Special Issue on Parallel and
                                  Distributed Computing  . . . . . . . . . 245--247
                    M. A. Palis   Part 1 (Selected Papers From ISPAN '99)  245
                   Sartaj Sahni   Models and Algorithms for Optical and
                                  Optoelectronic Parallel Computers  . . . 249--264
Fabricio Alves Barbosa Da Silva and   
              Isaac D. Scherson   Efficient Parallel Job Scheduling Using
                                  Gang Service . . . . . . . . . . . . . . 265--284
          F. A. B. da Silva and   
                 I. D. Scherson   Efficient Parallel Job Scheduling Using
                                  Gang Service . . . . . . . . . . . . . . 265
          Noriyuki Fujimoto and   
                Tomoki Baba and   
          Takashi Hashimoto and   
                    K. Hagihara   On Message Packaging in Task Scheduling
                                  for Distributed Memory Parallel Machines 285--306
                Weisong Shi and   
                    Zhimin Tang   Load Balancing in Home-Based Software
                                  DSMS . . . . . . . . . . . . . . . . . . 307--324
          Takayoshi Touyama and   
               Susumu Horiguchi   Performance Evaluation of Practical
                                  Parallel Computer Model LogPQ  . . . . . 325--340
         Jennifer M. Schopf and   
                Francine Berman   Using Stochastic Information to Predict
                                  Application Behavior on Contended
                                  Resources  . . . . . . . . . . . . . . . 341--363 (or 341--364??)
                   Marc Bui and   
               Sajal K. Das and   
              Ajoy K. Datta and   
                   D. T. Nguyen   Randomized Mobile Agent Based Routing in
                                  Wireless Networks  . . . . . . . . . . . 365--384
                Birgit Elbl and   
                      Jiawen Su   A Non-Definability Result for a
                                  Predicational Language with the Usual
                                  Control  . . . . . . . . . . . . . . . . 385--396
                        B. Elbl   Part 2 (Regular Papers)  . . . . . . . . 385
 Géza Harváth and   
             Katsushi Inoue and   
                  Akira Ito and   
                        Y. Wang   Closure Property of Probabilistic Turing
                                  Machines and Alternating Turing Machines
                                  with Sublogarithmic Spaces . . . . . . . 397--409

International Journal of Foundations of Computer Science (IJFCS)
Volume 12, Number 4, 2001

               Alan Roberts and   
              Antonios Symvonis   On the Routing Number of Complete
                                  $d$-ary Trees  . . . . . . . . . . . . . 411--434
             Koich Yamazaki and   
              Sei'ichi Tani and   
                Tetsuro Nishino   A Characterization of $k$-th Powers
                                  $P_{n,k}$ of Paths in Terms of $k$-Trees 435--443 (or 435--444??)
                   Pak-Ken Wong   An Algorithm for Finding Longest Cycles
                                  in Certain Bipartite Graphs  . . . . . . 445--454
              Lars Jacobsen and   
                  Kim S. Larsen   Variants of $(A,B)$-Trees with Relaxed
                                  Balance  . . . . . . . . . . . . . . . . 455--478
        Christian S. Calude and   
            Hajime Ishihara and   
              Takeshi Yamaguchi   Coding with Minimal Programs . . . . . . 479--489 (or 479--490??)
                M. Sitharam and   
                Timothy Straney   Derandomized Learning of Boolean
                                  Functions over Finite Abelian Groups . . 491--516
             Oleg Verbitsky and   
               Shafi Goldwasser   Remarks on a Query-Based Variant of the
                                  Parallel Repetition Theorem  . . . . . . 517--531 (or 517--532??)
               Wing-Kai Hon and   
                    Tak-Wah Lam   Approximating the Nearest Neighbor
                                  Interchange Distance for
                                  Non-Uniform-Degree Evolutionary Trees    533--550
                Adam Obtulowicz   Membrane Computing and One-Way Functions 551--558

International Journal of Foundations of Computer Science (IJFCS)
Volume 12, Number 5, 2001

               Albert Y. Zomaya   Scheduling . . . . . . . . . . . . . . . 559--564
               Albert Y. Zomaya   Scheduling: Theory and Applications:
                                  Guest Editor's Preface . . . . . . . . . 559--564
                   A. Y. Zomaya   Special Issue: Part 1  . . . . . . . . . 559
            David L. Rhodes and   
                 Wayne Wolf and   
                  Albert Zomaya   Two CoNP-Complete Schedule Analysis
                                  Problems . . . . . . . . . . . . . . . . 565--580
   Chantana Chantrapornchai and   
          Sissades Tongsima and   
                  Albert Zomaya   Resource Estimation Algorithm Under
                                  Impreciseness Using Inclusion Scheduling 581--598
   Mary Mehrnoosh Eshaghian and   
                  Albert Zomaya   Mapping Arbitrary Heterogeneous Task
                                  Graphs Onto Arbitrary Heterogeneous
                                  System Graphs  . . . . . . . . . . . . . 599--628
                 J. Santoso and   
           G. D. Van Albada and   
             P. M. A. Sloot and   
                B. A. A. Nazief   Simulation of Hierarchical Resource
                                  Management for Meta-Computing Systems    629--643 (or 629--644??)
             Oliver Diessel and   
             Hossam Elgindy and   
                  Albert Zomaya   On Dynamic Task Scheduling for
                                  FPGA-Based Systems . . . . . . . . . . . 645--669 (or 645--670??)
    Harald Meyer Auf'm Hofe and   
                  Albert Zomaya   Solving Rostering Tasks By Generic
                                  Methods for Constraint Optimization  . . 671--693
               Yasuyuki Tsukada   Errata: The paper: \em Martin-Löf's Type
                                  Theory as an Open-Ended Framework  . . . 695

International Journal of Foundations of Computer Science (IJFCS)
Volume 12, Number 6, December, 2001

                Dirk Fimmel and   
                      J. Muller   Optimal Software Pipelining Under
                                  Resource Constraints . . . . . . . . . . 697--718
        Leila Azouz Saidane and   
                      F. Kamoun   Modelling and Performance Evaluation of
                                  the Circulating Multisequencer, The
                                  Multi-Tokens and the Consensus
                                  Algorithms in a Real Time Distributed
                                  Transactional System . . . . . . . . . . 719--750
               Paolo Priore and   
            D. D. L. Fuente and   
                   A. Gomez and   
                         others   Dynamic Scheduling of Manufacturing
                                  Systems with Machine Learning  . . . . . 751--762
                       Keqin Li   An Efficient Job Scheduling Algorithm in
                                  Partitionable Mesh Connected Systems . . 763--774
                    K. Oida and   
                      K. Shinjo   Characteristics of Deterministic Optimal
                                  Routing for Two Heterogeneous Parallel
                                  Servers  . . . . . . . . . . . . . . . . 775--790
            Teofilo F. Gonzalez   On Solving Multimessage Multicasting
                                  Problems . . . . . . . . . . . . . . . . 791--808
                David Blokh and   
                      E. Levner   The Maximum Traveling Salesman Problem
                                  on Banded Matrices . . . . . . . . . . . 809--820
            Oscar H. Ibarra and   
                  T. Bultan and   
                          J. Su   On Reachability and Safety in
                                  Infinite-State Systems . . . . . . . . . 821--836
            Gheorghe P\uaun and   
               G. Rozenberg and   
                    T. Yokomori   Hairpin Languages  . . . . . . . . . . . 837--848
                      Anonymous   Author Index Volume 12 (2001)  . . . . . 849


International Journal of Foundations of Computer Science (IJFCS)
Volume 13, Number 1, 2002

                          S. Yu   Special Issue  . . . . . . . . . . . . . 1
                   D. Harel and   
                      H. Kugler   Synthesizing State-Based Object Systems
                                  from LSC Specifications  . . . . . . . . 5
                A. Bergeron and   
                       S. Hamel   Vector Algorithms for Approximate String
                                  Matching . . . . . . . . . . . . . . . . 53
   A. Brüggemann-Klein and   
                        D. Wood   The Regularity of Two-Way
                                  Nondeterministic Tree Automata Languages 67
                C. Campeanu and   
                  A. P\uaun and   
                          S. Yu   An Efficient Algorithm for Constructing
                                  Minimal Cover Automata for Finite
                                  Languages  . . . . . . . . . . . . . . . 83
              J.-M. Champarnaud   Evaluation of Three Implicit Structures
                                  to Implement Nondeterministic Automata
                                  From Regular Expressions . . . . . . . . 99
                   O. H. Ibarra   Verification in Queue-Connected
                                  Multicounter Machines  . . . . . . . . . 115
                       M. Mohri   Generic e-Removal and Input
                                  e-Normalization Algorithms for Weighted
                                  Transducers  . . . . . . . . . . . . . . 129
              G. Pighizzini and   
                     J. Shallit   Unary Language Operations, State
                                  Complexity and Jacobsthal's Function . . 145

International Journal of Foundations of Computer Science (IJFCS)
Volume 13, Number 2, 2002

                S.-W. Cheng and   
                         T. Dey   Special Issue  . . . . . . . . . . . . . 161
                   O. Devillers   The Delaunay Hierarchy . . . . . . . . . 163
               O. Devillers and   
                    S. Pion and   
                    M. Teillaud   Walking in a Triangulation . . . . . . . 181
         A. Üngör and   
                     A. Sheffer   Pitching Tents in Space-Time: Mesh
                                  Generation for Discontinuous Galerkin
                                  Method . . . . . . . . . . . . . . . . . 201
            H. Edelsbrunner and   
                        D. Guoy   Sink Insertion for Mesh Improvement  . . 223
                      W. Xu and   
              R. Hammersley and   
                      K. Lu and   
                     D. Fussell   Lossless Subdivision-Based
                                  Multiresolution Representation of
                                  Arbitrary Triangle Meshes Using Kite
                                  Trees  . . . . . . . . . . . . . . . . . 243
                      G. Xu and   
                C. L. Bajaj and   
                       S. Evans   $C^1$ Modeling with Hybrid
                                  Multiple-Sided A-Patches . . . . . . . . 261
                     W. H. Frey   Boundary Triangulations Approximating
                                  Developable Surfaces that Interpolate a
                                  Close Space Curve  . . . . . . . . . . . 285
              O. Aichholzer and   
               L. S. Alboul and   
                     F. Hurtado   On Flips in Polyhedral Surfaces  . . . . 303

International Journal of Foundations of Computer Science (IJFCS)
Volume 13, Number 3, 2002

          P. S. Thiagarajan and   
                         R. Yap   Special Issue  . . . . . . . . . . . . . 313
            J. I. D. Hartog and   
                  E. P. D. Vink   Verifying Probabilistic Programs Using a
                                  Hoare Like Logic . . . . . . . . . . . . 315
                J. G. Henriksen   An Expressive Extension of TLC . . . . . 341
             F. Kamareddine and   
                       F. Monin   An Extension of an Automated Termination
                                  Method of Recursive Functions  . . . . . 361
            A. Roychoudhury and   
                K. N. Kumar and   
         C. R. Ramakrishnan and   
             I. V. Ramakrishnan   Beyond Tamaki--Sato Style Unfold/Fold
                                  Transformations for Normal Logic
                                  Programs . . . . . . . . . . . . . . . . 387
             E. Y. C. Cheng and   
                       S. Sahni   Regular Papers . . . . . . . . . . . . . 405
                      M. Hutter   The Fastest and Shortest Algorithm for
                                  All Well-Defined Problems  . . . . . . . 431
                 H. Zantema and   
               H. L. Bodlaender   Sizes of Ordered Decision Trees  . . . . 445
                K. Culik II and   
          J. Karhumäki and   
                        J. Kari   A Note on Synchronized Automata and Road
                                  Coloring Problem . . . . . . . . . . . . 459

International Journal of Foundations of Computer Science (IJFCS)
Volume 13, Number 4, 2002

                 C. X. Ling and   
                     N. Cercone   Special Issue  . . . . . . . . . . . . . 473
            A. Lörincz and   
            I. Kókai and   
                     A. Meretei   Intelligent High-Performance Crawlers
                                  Used to Reveal Topic-Specific Structure
                                  of WWW . . . . . . . . . . . . . . . . . 477
         V. Estivill-Castro and   
                        J. Yang   Clustering Web Visitors by Fast, Robust
                                  and Convergent Algorithms  . . . . . . . 497
                     W. Gao and   
                    S. Wang and   
                         B. Liu   A Dynamic Recommendation System Based on
                                  Log Mining . . . . . . . . . . . . . . . 521
                      V. Ng and   
                       M. K. Ho   An Intelligent Agent for Web
                                  Advertisements . . . . . . . . . . . . . 531
                       N. Zhong   Representation and Construction of
                                  Ontologies for Web Intelligence  . . . . 555
                N. Klarlund and   
           A. Mòller and   
              M. I. Schwatzbach   Regular Papers . . . . . . . . . . . . . 571
                 J. Schmidhuber   Hierarchies of Generalized Kolmogorov
                                  Complexities and Nonenumerable Universal
                                  Measures Computable in the Limit . . . . 587
                R. Lep\`ere and   
                D. Trystram and   
                G. J. Woeginger   Approximation Algorithms for Scheduling
                                  Malleable Tasks Under Precedence
                                  Constraints  . . . . . . . . . . . . . . 613

International Journal of Foundations of Computer Science (IJFCS)
Volume 13, Number 5, October, 2002

                   Xiaotie Deng   Preface  . . . . . . . . . . . . . . . . 629
               J. M. Bilbao and   
     J. R. Fernández and   
             J. J. López   On the Complexity of Computing Values of
                                  Restricted Games . . . . . . . . . . . . 633
                 Qizhi Fang and   
                   Shanfeng Zhu   Linear and Integer Programming
                                  Techniques for Cooperative Games . . . . 653
                 Weijia Jia and   
                     Zhibin Sun   On Computational Complexity of
                                  Hierarchical Optimization  . . . . . . . 667
             Xiaoguang Yang and   
                   Shuo Tao and   
                Rongjun Liu and   
                   Maocheng Cai   Complexity of Scenario-Based Portfolio
                                  Optimization Problem with Var Objective  671
               Xiaotie Deng and   
               Zhong-Fei Li and   
                 Shou-Yang Wang   Computational Complexity of Arbitrage in
                                  Frictional Security Market . . . . . . . 681
                   Jiwu Shu and   
                Yonggeng Gu and   
                   Weimin Zheng   A Novel Numerical Approach of Computing
                                  American Option  . . . . . . . . . . . . 685
            Emmanuelle Anceaume   Efficient Solution To Uniform Atomic
                                  Broadcast  . . . . . . . . . . . . . . . 695
     Nicoletta De Francesco and   
              Antonella Santone   A Formula-Driven Modular Attack on State
                                  Explosion  . . . . . . . . . . . . . . . 719
  Carlos Martín-Vide and   
         Alexandru Mateescu and   
                 Victor Mitrana   Parallel Finite Automata Systems
                                  Communicating By States  . . . . . . . . 733
         Abdullah N. Arslan and   
        Ömer E\ugecio\uglu   Approximation Algorithms for Local
                                  Alignment with Length Constraints  . . . 751
                   Juha Honkala   Remarks Concerning the D0L
                                  $\omega$-Equivalence Problem . . . . . . 769

International Journal of Foundations of Computer Science (IJFCS)
Volume 13, Number 6, December, 2002

              Andrei P\uaun and   
            Gheorghe P\uaun and   
             Grzegorz Rozenberg   Computing By Communication in Networks
                                  of Membranes . . . . . . . . . . . . . . 779
          C. Câmpeanu and   
                 K. Salomaa and   
       S. Vágvölgyi   Shuffle Decompositions of Regular
                                  Languages  . . . . . . . . . . . . . . . 799
               Xiaotie Deng and   
                 Haodi Feng and   
                  Guojun Li and   
                    Guizhen Liu   A PTAS for Minimizing Total Completion
                                  Time of Bounded Batch Scheduling . . . . 817
                  Nicholas Tran   On Universally Polynomial Context-Free
                                  Languages  . . . . . . . . . . . . . . . 829
             Andrea Mantler and   
                  Helen Cameron   Constructing Red-Black Tree Shapes . . . 837
        Emmanuelle Anceaume and   
         Jean-Michel Helary and   
                  Michel Raynal   A Note on the Determination of the
                                  Immediate Predecessors in a Distributed
                                  Computation  . . . . . . . . . . . . . . 865
               Nadia Nedjah and   
       Luiza De Macedo Mourelle   Pattern Matching Code Minimization in
                                  Rewriting-Based Programming Languages    873
         Michalis Faloutsos and   
              Rajesh Pankaj and   
              Kenneth C. Sevcik   The Effect of Asymmetry on the On-Line
                                  Multicast Routing Problem  . . . . . . . 889
                   Zhe Dang and   
                Oscar H. Ibarra   The Existence of $\omega$-Chains for
                                  Transitive Mixed Linear Relations and
                                  Its Applications . . . . . . . . . . . . 911
                      Anonymous   Author Index Volume 13 (2002)  . . . . . 937


International Journal of Foundations of Computer Science (IJFCS)
Volume 14, Number 1, February, 2003

                Koji Nakano and   
                         Jie Wu   Preface  . . . . . . . . . . . . . . . . 1
            Arnold L. Rosenberg   Efficient Pairing Functions --- and Why
                                  You Should Care  . . . . . . . . . . . . 3
               Albert Y. Zomaya   Mobile Computing: Opportunities for
                                  Parallel Algorithms Research . . . . . . 19
                Claudia Leopold   Cache Miss Analysis of $2$D Stencil
                                  Codes with Tiled Time Loop . . . . . . . 39
        Martin Schmollinger and   
               Michael Kaufmann   Designing Parallel Algorithms for
                                  Hierarchical SMP Clusters  . . . . . . . 59
             Chin-Hsiung Wu and   
                 Shi-Jinn Horng   Scalable and Optimal Speed-Up Parallel
                                  Algorithms for Template Matching on
                                  Arrays with Reconfigurable Optical Buses 79
                     Jie Wu and   
                 Stephen Olariu   On Cost-Optimal Merge of Two
                                  Intransitive Sorted Sequences  . . . . . 99
             V. Giakoumakis and   
                 J. M. Vanherpe   Linear Time Recognition and
                                  Optimizations for Weak-Bisplit Graphs,
                                  Bi-Cographs and Bipartite $P_6$-Free
                                  Graphs . . . . . . . . . . . . . . . . . 107
                    Koji Nakano   Linear Layout of Generalized Hypercubes  137
                   Mutyam Madhu   Probabilistic Rewriting $P$ Systems  . . 157

International Journal of Foundations of Computer Science (IJFCS)
Volume 14, Number 2, April, 2003

                      Anonymous   Preface  . . . . . . . . . . . . . . . . 167
               Guangbin Fan and   
                 Jingyuan Zhang   Optimal Cellular Network Deployment
                                  Reusing Existing Base Stations . . . . . 169
                    Yu Wang and   
              Xiang-Yang Li and   
                  Ophir Frieder   Distributed Spanners with Bounded Degree
                                  for Wireless Ad Hoc Networks . . . . . . 183
                     Jie Wu and   
                        Fei Dai   Broadcasting in Ad Hoc Networks Based on
                                  Self-Pruning . . . . . . . . . . . . . . 201
                   A. Ferro and   
                  G. Pigola and   
              A. Pulvirenti and   
                      D. Shasha   Fast Clustering and Minimum Weight
                                  Matching Algorithms for Very Large
                                  Mobile Backbone Wireless Networks  . . . 223
              Justin Lipman and   
              Paul Boustead and   
                     John Judge   Neighbor Aware Adaptive Power Flooding
                                  (NAAP) in Mobile Ad Hoc Networks . . . . 237
            Julien Cartigny and   
  François Ingelrest and   
                  David Simplot   RNG Relay Subset Flooding Protocols in
                                  Mobile Ad-Hoc Networks . . . . . . . . . 253
                B. Bui Xuan and   
                A. Ferreira and   
                       A. Jarry   Computing Shortest, Fastest, and
                                  Foremost Journeys in Dynamic Networks    267
          Khaled M. Alzoubi and   
               Peng-Jun Wan and   
                  Ophir Frieder   Maximal Independent Set,
                                  Weakly-Connected Dominating Set, and
                                  Induced Spanners in Wireless Ad Hoc
                                  Networks . . . . . . . . . . . . . . . . 287
         Yuanzhu Peter Chen and   
             Arthur L. Liestman   A Zonal Algorithm for Clustering An Hoc
                                  Networks . . . . . . . . . . . . . . . . 305
               Peng-Jun Wan and   
          Khaled M. Alzoubi and   
                  Ophir Frieder   A Simple Heuristic for Minimum Connected
                                  Dominating Set in Graphs . . . . . . . . 323

International Journal of Foundations of Computer Science (IJFCS)
Volume 14, Number 3, June, 2003

                      Anonymous   Preface  . . . . . . . . . . . . . . . . 335
               Sartaj Sahni and   
                Kun Suk Kim and   
                      Haibin Lu   Data Structures for One-Dimensional
                                  Packet Classification Using
                                  Most-Specific-Rule Matching  . . . . . . 337
               Michael A. Palis   On the Competitiveness of Online
                                  Real-Time Scheduling with Rate of
                                  Progress Guarantees  . . . . . . . . . . 359
                     Ke Qiu and   
                   Sajal K. Das   Interconnection Networks and Their
                                  Eigenvalues  . . . . . . . . . . . . . . 371
          Jacir Luiz Bordim and   
                Koji Nakano and   
                      Hong Shen   Sorting on Single-Channel Wireless
                                  Sensor Networks  . . . . . . . . . . . . 391
                 Peiyi Tang and   
                  Pen-Chung Yew   Interprocedural Induction Variable
                                  Analysis . . . . . . . . . . . . . . . . 405
           Wolfgang W. Bein and   
        Lawrence L. Larmore and   
             Shahram Latifi and   
              I. Hal Sudborough   Block Sorting is Hard  . . . . . . . . . 425
            Sasthi C. Ghosh and   
           Bhabani P. Sinha and   
                   Nabanita Das   A New Approach to Efficient Channel
                                  Assignment for Hexagonal Cellular
                                  Networks . . . . . . . . . . . . . . . . 439
                Haejae Jung and   
                   Sartaj Sahni   Supernode Binary Search Trees  . . . . . 465
                  S. Bansal and   
               S. Sreekanth and   
                       P. Gupta   M-Heap: a Modified Heap Data Structure   491
        William C. Grimmell and   
            Nageswara S. V. Rao   On Source-Based Route Computation for
                                  Quickest Paths under Dynamic Bandwidth
                                  Constraints  . . . . . . . . . . . . . . 503

International Journal of Foundations of Computer Science (IJFCS)
Volume 14, Number 4, August, 2003

                      Anonymous   Preface  . . . . . . . . . . . . . . . . 525
           E. Allen Emerson and   
              Kedar S. Namjoshi   On Reasoning about Rings . . . . . . . . 527
            Ahmed Bouajjani and   
             Javier Esparza and   
                 Tayssir Touili   A Generic Approach to the Static
                                  Analysis of Concurrent Programs with
                                  Procedures . . . . . . . . . . . . . . . 551
              Edmund Clarke and   
             Ansgar Fehnker and   
                    Zhi Han and   
                Bruce Krogh and   
         Joël Ouaknine and   
             Olaf Stursberg and   
               Michael Theobald   Abstraction and Counterexample-Guided
                                  Refinement in Model Checking of Hybrid
                                  Systems  . . . . . . . . . . . . . . . . 583
       Constantinos Bartzis and   
                  Tevfik Bultan   Efficient Symbolic Representations for
                                  Arithmetic Constraints in Verification   605
                 Deepak D'souza   A Logical Characterisation of Event
                                  Clock Automata . . . . . . . . . . . . . 625
                    Li Jiao and   
                  To-Yat Cheung   Characterizing Liveness Monotonicity for
                                  Weighted Petri Nets in Terms of
                                  Siphon-Based Properties  . . . . . . . . 641
                  Axel Dold and   
        Friedrich Von Henke and   
               Wolfgang Goerigk   A Completely Verified Realistic
                                  Bootstrap Compiler . . . . . . . . . . . 659
         Kamala Krithivasan and   
                  K. Sharda and   
               Sandeep V. Varma   Distributed $\omega$-Automata  . . . . . 681
          J. Karhumäki and   
                  L. P. Lisovik   The Equivalence Problem of Finite
                                  Substitutions on $ab*c$, with
                                  Applications . . . . . . . . . . . . . . 699

International Journal of Foundations of Computer Science (IJFCS)
Volume 14, Number 5, October, 2003

                      Anonymous   Preface  . . . . . . . . . . . . . . . . 711
                  Lov K. Grover   An Improved Quantum Scheduling Algorithm 715
       Gábor Ivanyos and   
Frédéric Magniez and   
                  Miklos Santha   Efficient Quantum Algorithms for Some
                                  Instances of the Non-Abelian Hidden
                                  Subgroup Problem . . . . . . . . . . . . 723
                  Jan Bouda and   
     Vladimír R. Bu\vzek   Encryption of Quantum Information  . . . 741
              Markus Grassl and   
       Martin Rötteler and   
                    Thomas Beth   Efficient Quantum Circuits for Non-Qubit
                                  Quantum Error-Correcting Codes . . . . . 757
       Andreas Klappenecker and   
           Martin Rötteler   Quantum Software Reusability . . . . . . 777
           Philippe Jorrand and   
                   Mehdi Mhalla   Separability of Pure $N$-Qubit States:
                                  Two Characterizations  . . . . . . . . . 797
              Tomoyuki Yamakami   Analysis of Quantum Functions  . . . . . 815
            Harumichi Nishimura   Quantum Computation with Restricted
                                  Amplitudes . . . . . . . . . . . . . . . 853
            Alberto Bertoni and   
           Carlo Mereghetti and   
                Beatrice Palano   Golomb Rulers and Difference Sets for
                                  Succinct Quantum Automata  . . . . . . . 871
            Dominik Janzing and   
               Pawel Wocjan and   
                    Thomas Beth   On the Computational Power of Physical
                                  Interactions: Bounds on the Number of
                                  Time Steps for Simulating Arbitrary
                                  Interaction Graphs . . . . . . . . . . . 889
                  Anuj Jain and   
               Sartaj Sahni and   
             Jatinder Palta and   
                  James Dempsey   Partitioning $3$D Phantoms into
                                  Homogeneous Cuboids  . . . . . . . . . . 905
             Evgeny Dantsin and   
              Alexander Wolpert   A Robust DNA Computation Model that
                                  Captures Pspace  . . . . . . . . . . . . 933

International Journal of Foundations of Computer Science (IJFCS)
Volume 14, Number 6, December, 2003

          Jean-Marc Champarnaud   Preface  . . . . . . . . . . . . . . . . 953
                  Mehryar Mohri   Edit-Distance of Weighted Automata:
                                  General Definitions and Algorithms . . . 957
             Cyril Allauzen and   
                  Mehryar Mohri   Finitely Subsequential Transducers . . . 983
       Cezar Câmpeanu and   
                  Andrei P\uaun   Counting the Number of Minimal DFCA
                                  Obtained By Merging States . . . . . . . 995
       Cezar Câmpeanu and   
                Kai Salomaa and   
                       Sheng Yu   A Formal Study of Practical Regular
                                  Expressions  . . . . . . . . . . . . . . 1007
            Jurek Czyzowicz and   
           Wojciech Fraczak and   
               Andrzej Pelc and   
                Wojciech Rytter   Linear-Time Prime Decomposition of
                                  Regular Prefix Codes . . . . . . . . . . 1019
          Mihaela Gheorghiu and   
              Janusz Brzozowski   Simulation of Feedback-Free Circuits in
                                  the Algebra of Transients  . . . . . . . 1033
             Franck Guingne and   
             Florent Nicart and   
      Jean-Marc Champarnaud and   
            Lauri Karttunen and   
   Tamás Gaál and   
             André Kempe   Virtual Operations on Virtual Networks:
                                  the Priority Union . . . . . . . . . . . 1055
              Heiko Körner   A Time and Space Efficient Algorithm for
                                  Minimizing Cover Automata for Finite
                                  Languages  . . . . . . . . . . . . . . . 1071
              Markus Holzer and   
                  Martin Kutrib   Nondeterministic Descriptional
                                  Complexity of Regular Languages  . . . . 1087
              Alexander Okhotin   Efficient Automaton-Based Recognition
                                  for Linear Conjunctive Languages . . . . 1103
                   Klaus Sutner   Reduced Power Automata and Sofic Systems 1117
            David S. L. Wei and   
    Sanguthevar Rajasekaran and   
           Kshirasagar Naik and   
                     Sy-Yen Kuo   Efficient Algorithms for Selection and
                                  Sorting of Large Distributed Files on De
                                  Bruijn and Hypercube Structures  . . . . 1129
             Carlo Fantozzi and   
       Andrea Pietracaprina and   
                  Geppino Pucci   A General PRAM Simulation Scheme for
                                  Clustered Machines . . . . . . . . . . . 1147
            Paul M. Martini and   
             Walter A. Burkhard   Double Hashing with Multiple Passbits    1165
                      Anonymous   Author Index Volume 14 (2003)  . . . . . 1183


International Journal of Foundations of Computer Science (IJFCS)
Volume 15, Number 1, February, 2004

            Oscar H. Ibarra and   
                   Louxin Zhang   Computing and Combinatorics Conference
                                  --- COCOON'02  . . . . . . . . . . . . . 1
                 Jin-Yi Cai and   
              Denis Charles and   
                   A. Pavan and   
                 Samik Sengupta   On Higher Arthur--Merlin Classes . . . . 3
     San Skulrattanakulchai and   
                Harold N. Gabow   Coloring Algorithms on Subcubic Graphs   21
                Lucian Ilie and   
                   Sheng Yu and   
                 Kaizhong Zhang   Word Complexity and Repetitions in Words 41
         Abdullah N. Arslan and   
        Ömer E\ugecio\uglu   Dictionary Look-Up Within Small Edit
                                  Distance . . . . . . . . . . . . . . . . 57
                    Koji Nakano   Time and Energy Optimal List Ranking
                                  Algorithms on the $k$-Channel Broadcast
                                  Communication Model with No Collision
                                  Detection  . . . . . . . . . . . . . . . 73
           Thanh Minh Hoang and   
                Thomas Thierauf   On the Minimal Polynomial of a Matrix    89
                Yvo Desmedt and   
                    Yongge Wang   Analyzing Vulnerabilities of Critical
                                  Infrastructures Using Flows and Critical
                                  Vertices in And/Or Graphs  . . . . . . . 107
                  Weimin Ma and   
                 Yinfeng Xu and   
                   Jane You and   
                  James Liu and   
                  Kanliang Wang   On the $k$-Truck Scheduling Problem  . . 127
             Michael Domaratzki   Improved Bounds on the Number of
                                  Automata Accepting Finite Languages  . . 143
    Andreas Brandstädt and   
            Ho\`ang-Oanh Le and   
                 Raffaele Mosca   Gem- and Co-Gem-Free Graphs Have Bounded
                                  Clique-Width . . . . . . . . . . . . . . 163
                 Yinlong Xu and   
                     Li Lin and   
              Guoliang Chen and   
                 Yingyu Wan and   
                     Weijun Guo   Multicasting and Broadcasting in
                                  Undirected WDM Networks and QoS
                                  Extensions of Multicasting . . . . . . . 187
           Ricardo Alberich and   
     Merc\`e Llabrés and   
       Francesc Rosselló   Single-Pushout Transformation of Total
                                  Algebras . . . . . . . . . . . . . . . . 205

International Journal of Foundations of Computer Science (IJFCS)
Volume 15, Number 2, April, 2004

                      Anonymous   Preface  . . . . . . . . . . . . . . . . 223
                    Eric Rivals   A Survey on Algorithmic Aspects of
                                  Tandem Repeats Evolution . . . . . . . . 225
             S. W. Margolis and   
                  J.-E. Pin and   
                   M. V. Volkov   Words Guaranteeing Minimum Image . . . . 259
         Alexandru Mateescu and   
                   Arto Salomaa   Matrix Indicators for Subword
                                  Occurrences and Ambiguity  . . . . . . . 277
                   S. Brlek and   
                   S. Hamel and   
                   M. Nivat and   
                  C. Reutenauer   On the Palindromic Complexity of
                                  Infinite Words . . . . . . . . . . . . . 293
Gwénaël Richomme and   
  Patrice Séébold   Conjectures and Results on Morphisms
                                  Generating $k$-Power-Free Words  . . . . 307
                Jeffrey Shallit   Simultaneous Avoidance of Large Squares
                                  and Fractional Powers in Infinite Binary
                                  Words  . . . . . . . . . . . . . . . . . 317
             Jacques Justin and   
               Giuseppe Pirillo   Episturmian Words: Shifts, Morphisms and
                                  Numeration Systems . . . . . . . . . . . 329
                 Tero Harju and   
                   Dirk Nowotka   Minimal Duval Extensions . . . . . . . . 349
               Arturo Carpi and   
                   Aldo de Luca   Repetitions, Fullness, and Uniformity in
                                  Two-Dimensional Words  . . . . . . . . . 355
            Monaldo Mastrolilli   Scheduling To Minimize Max Flow Time:
                                  Off-Line and On-Line Algorithms  . . . . 385
            Jacir L. Bordim and   
            Oscar H. Ibarra and   
                Yasuaki Ito and   
                    Koji Nakano   Instance-Specific Solutions for
                                  Accelerating the CKY Parsing of Large
                                  Context-Free Grammars  . . . . . . . . . 403
       Manolis Gergatsoulis and   
               Christos Nomikos   A Proof Procedure for Temporal Logic
                                  Programming  . . . . . . . . . . . . . . 417
              Chun-Pong Lai and   
                  Cunsheng Ding   Several Generalizations of Shamir's
                                  Secret Sharing Scheme  . . . . . . . . . 445

International Journal of Foundations of Computer Science (IJFCS)
Volume 15, Number 3, June, 2004

                Koji Nakano and   
                         Jie Wu   Preface  . . . . . . . . . . . . . . . . 459
           Akihiro Fujiwara and   
         Ken'Ichi Matsumoto and   
                       Wei Chen   Procedures for Logic and Arithmetic
                                  Operations with DNA Molecules  . . . . . 461
                Susumu Matsumae   Simulation of Meshes with Separable
                                  Buses By Meshes with Multiple
                                  Partitioned Buses  . . . . . . . . . . . 475
               Mitali Singh and   
             Viktor K. Prasanna   A Hierarchical Model for Distributed
                                  Collaborative Computation in Wireless
                                  Sensor Networks  . . . . . . . . . . . . 485
          Lélia Blin and   
                 Franck Butelle   The First Approximated Distributed
                                  Algorithm for the Minimum Degree
                                  Spanning Tree Problem on General Graphs  507
                 Dajin Wang and   
                   Jiannong Cao   On Hierarchical Configuration of
                                  Distributed Systems on Mesh and
                                  Hypercube  . . . . . . . . . . . . . . . 517
              Thomas Rauber and   
             Gudula Rünger   Program-Based Locality Measures for
                                  Scientific Computing . . . . . . . . . . 535
               Mojca Ciglari\vc   Content Networks: Distributed Routing
                                  Decisions in Presence of Repeated
                                  Queries  . . . . . . . . . . . . . . . . 555

International Journal of Foundations of Computer Science (IJFCS)
Volume 15, Number 4, August, 2004

               Sartaj Sahni and   
                    Kun Suk Kim   Efficient Dynamic Lookup for Bursty
                                  Access Patterns  . . . . . . . . . . . . 567
           Chung Keung Poon and   
                       Wenci Yu   On Minimizing Total Completion Time in
                                  Batch Machine Scheduling . . . . . . . . 593
                  Xiaoyu Li and   
                  Howard Barnum   Quantum Authentication Using Entangled
                                  States . . . . . . . . . . . . . . . . . 609
    Ömer E\ugecio\uglu and   
          Jeffrey B. Remmel and   
             S. Gill Williamson   A Class of Graphs Which Has Efficient
                                  Ranking and Unranking Algorithms for
                                  Spanning Trees and Forests . . . . . . . 619
                 Dawei Hong and   
                  Shushuang Man   Analysis of Web Search Algorithm Hits    649
             Jürgen Dassow   On the Descriptional Complexity of
                                  Lindenmayer Systems  . . . . . . . . . . 663
                Qingmin Shi and   
      Joseph Jájá   Fast Algorithms for $3$-D Dominance
                                  Reporting and Counting . . . . . . . . . 673
           Thanh Minh Hoang and   
                Thomas Thierauf   Erratum: on the Minimal Polynomial of a
                                  Matrix . . . . . . . . . . . . . . . . . 685

International Journal of Foundations of Computer Science (IJFCS)
Volume 15, Number 5, October, 2004

      Jean-Marc Champarnaud and   
     Éric Laugerotte and   
             Faissal Ouardi and   
                 Djelloul Ziadi   From Regular Weighted Expressions To
                                  Finite Automata  . . . . . . . . . . . . 687
        Alessandro Ferrante and   
                  Mimmo Parente   On the Vertex-Connectivity Problem for
                                  Graphs with Sharpened Triangle
                                  Inequality . . . . . . . . . . . . . . . 701
             Kevin I.-J. Ho and   
             Joseph Y.-T. Leung   A Dual Criteria Preemptive Scheduling
                                  Problem for Minimax Error of Imprecise
                                  Computation Tasks  . . . . . . . . . . . 717
             Joseph Y.-T. Leung   Improved Competitive Algorithms for
                                  Two-Processor Real-Time Systems  . . . . 733
                Sahar Idwan and   
            Dinesh P. Mehta and   
                 Mario A. Lopez   Fast Pursuit of Mobile Nodes Using TPR
                                  Trees  . . . . . . . . . . . . . . . . . 753
               Chung Keung Poon   Optimal Range Max Datacube for Fixed
                                  Dimensions . . . . . . . . . . . . . . . 773
             Katsushi Inoue and   
                  Akira Ito and   
            Takashi Kamiura and   
            Holger Petersen and   
                      Lan Zhang   A Note on Rebound Turing Machines  . . . 791

International Journal of Foundations of Computer Science (IJFCS)
Volume 15, Number 6, December, 2004

                    Jun Luo and   
        Sanguthevar Rajasekaran   Parallelizing $1$-Dimensional Estuarine
                                  Model  . . . . . . . . . . . . . . . . . 809
                 Olivier Finkel   On Recognizable Languages of Infinite
                                  Pictures . . . . . . . . . . . . . . . . 823
           Jaume Casasnovas and   
            Joe Miró and   
              Manuel Moy\`a and   
       Francesc Rosselló   An Approach To Membrane Computing Under
                                  Inexactitude . . . . . . . . . . . . . . 841
                      Farn Wang   Inductive Composition of Numbers with
                                  Maximum, Minimum, and Addition: a New
                                  Theory for Program Execution-Time
                                  Analysis . . . . . . . . . . . . . . . . 865
               Wing-Kai Hon and   
                Tak-Wah Lam and   
               Siu-Ming Yiu and   
              Ming-Yang Kao and   
                  Wing-Kin Sung   Subtree Transfer Distance for Degree-$D$
                                  Phylogenies  . . . . . . . . . . . . . . 893
                      Anonymous   Author Index Volume 15 (2004)  . . . . . 911


International Journal of Foundations of Computer Science (IJFCS)
Volume 16, Number 1, February, 2005

            Jacir L. Bordim and   
                Koji Nakano and   
            Arnold L. Rosenberg   Foreword . . . . . . . . . . . . . . . . 1
                     Jie Wu and   
                    Shuhui Yang   Energy-Efficient Node Scheduling Models
                                  in Sensor Networks with Adjustable
                                  Ranges . . . . . . . . . . . . . . . . . 3
              Wayne Goddard and   
      Stephen T. Hedetniemi and   
            David P. Jacobs and   
              Pradip K. Srimani   Self-Stabilizing Algorithms for
                                  Orderings and Colorings  . . . . . . . . 19
           Akihiro Fujiwara and   
                  Satoshi Kamio   Procedures for Multiple Input Functions
                                  with DNA Molecules . . . . . . . . . . . 37
José Alberto Fernández-Zepeda and   
     Daniel Fajardo-Delgado and   
José Antonio Cárdenas-Haro and   
               Anu G. Bourgeois   Efficient Simulation of an Acyclic
                                  Directed Reconfigurable Model on an
                                  Undirected Reconfigurable Model  . . . . 55
José Alberto Fernández-Zepeda and   
Alejandro Estrella-Balderrama and   
               Anu G. Bourgeois   Designing Fault Tolerant Algorithms for
                                  Reconfigurable Meshes  . . . . . . . . . 71
                Yasuaki Ito and   
                    Koji Nakano   FM screening by the Local Exhaustive
                                  Search, with Hardware Acceleration . . . 89
               Jaime Davila and   
        Sanguthevar Rajasekaran   Randomized Sorting on the POPS Network   105
             Kazuyuki Miura and   
              Machiko Azuma and   
                Takao Nishizeki   Canonical Decomposition, Realizer,
                                  Schnyder Labeling and Orderly Spanning
                                  Trees of Plane Graphs  . . . . . . . . . 117

International Journal of Foundations of Computer Science (IJFCS)
Volume 16, Number 2, April, 2005

            Jacir L. Bordim and   
                Koji Nakano and   
            Arnold L. Rosenberg   Foreword . . . . . . . . . . . . . . . . 143
                 Henri Casanova   Network Modeling Issues for Grid
                                  Application Scheduling . . . . . . . . . 145
           Olivier Beaumont and   
             Arnaud Legrand and   
              Loris Marchal and   
                    Yves Robert   Steady-State Scheduling on Heterogeneous
                                  Clusters . . . . . . . . . . . . . . . . 163
            Franck Cappello and   
          Pierre Fraigniaud and   
               Bernard Mans and   
            Arnold L. Rosenberg   An Algorithmic Model for Heterogeneous
                                  Hyper-Clusters: Rationale And Experience 195
Pierre-François Dutot and   
              Lionel Eyraud and   
Grégory Mounié and   
                 Denis Trystram   Scheduling on Large Scale Distributed
                                  Platforms: From Models To
                                  Implementations  . . . . . . . . . . . . 217
               Enrique Alba and   
               Fikret Ercal and   
           El-Ghazali Talbi and   
               Albert Y. Zomaya   Guest Editorial: Nature-Inspired
                                  Distributed Computing  . . . . . . . . . 239
       L. Vermeulen-Jourdan and   
                C. Dhaenens and   
                     E-G. Talbi   Linkage Disequilibrium Study with a
                                  Parallel Adaptive GA . . . . . . . . . . 241
            Lucas A. Wilson and   
              Michelle D. Moore   Cross-Pollinating Parallel Genetic
                                  Algorithms for Multi-Objective Search
                                  And Optimization . . . . . . . . . . . . 261
           Albert Y. Zomaya and   
                    Gerard Chan   Efficient Clustering for Parallel Tasks
                                  Execution in Distributed Systems . . . . 281
           Ajay K. Katangur and   
      Somasheker Akkaladevi and   
                     Yi Pan and   
               Martin D. Fraser   Routing in Optical Multistage Networks
                                  with Limited Crosstalk Using Ant Colony
                                  Optimization . . . . . . . . . . . . . . 301
              Daniel Merkle and   
          Martin Middendorf and   
            Alexander Scheidler   Decentralized Packet Clustering in
                                  Router-Based Networks  . . . . . . . . . 321
                    E. Alba and   
                     F. Chicano   On the Behavior of Parallel Genetic
                                  Algorithms for Optimal Placement of
                                  Antennae in Telecommunications . . . . . 343
               Klaus Jansen and   
        Monaldo Mastrolilli and   
              Roberto Solis-Oba   Approximation Algorithms for Flexible
                                  Job Shop Problems  . . . . . . . . . . . 361
              Jens S. Kohrt and   
                  Kim S. Larsen   On-Line Seat Reservations Via Off-Line
                                  Seating Arrangements . . . . . . . . . . 381

International Journal of Foundations of Computer Science (IJFCS)
Volume 16, Number 3, June, 2005

                Kai Salomaa and   
                       Sheng Yu   Preface  . . . . . . . . . . . . . . . . 399
             Cyril Allauzen and   
              Mehryar Mohri and   
                    Brian Roark   The Design Principles and Algorithms of
                                  a Weighted Grammar Library . . . . . . . 403
            Henning Bordihn and   
              Markus Holzer and   
                  Martin Kutrib   Unsolvability Levels of Operation
                                  Problems for Subclasses of Context-Free
                                  Languages  . . . . . . . . . . . . . . . 423
          J.-M. Champarnaud and   
                  F. Coulon and   
             T. Paranthoën   Brute Force Determinization of NFAs by
                                  Means of State Covers  . . . . . . . . . 441
                 Mark Daley and   
                  Ian Mcquillan   Formal Modelling of Viral Gene
                                  Compression  . . . . . . . . . . . . . . 453
               Alfons Geser and   
            Dieter Hofbauer and   
          Johannes Waldmann and   
                   Hans Zantema   Finding Finite Automata That Certify
                                  Termination of String Rewriting Systems  471
                Yonghua Han and   
                     Bin Ma and   
                 Kaizhong Zhang   An Automata Approach to Match Gapped
                                  Sequence Tags Against Protein Database   487
                 Yo-Sub Han and   
                    Derick Wood   The Generalization of Generalized
                                  Automata: Expression Automata  . . . . . 499
       Jozef Jirásek and   
Galina Jirásková and   
              Alexander Szabari   State Complexity of Concatenation and
                                  Complementation  . . . . . . . . . . . . 511
                  Lila Kari and   
     Stavros Konstantinidis and   
              Petr Sosík   Operations on Trajectories with
                                  Applications to Coding and
                                  Bioinformatics . . . . . . . . . . . . . 531
              Bryan Krawetz and   
              John Lawrence and   
                Jeffrey Shallit   State Complexity and the Monoid of
                                  Transformations of a Finite Set  . . . . 547
            Anssi Yli-Jyrä   Approximating Dependency Grammars
                                  Through Intersection of Star-Free
                                  Regular Languages  . . . . . . . . . . . 565
         Stanley P. Y. Fung and   
         Francis Y. L. Chin and   
                      Hong Shen   Online Scheduling of Unit Jobs with
                                  Bounded Importance Ratio . . . . . . . . 581
                   K. Subramani   Cascading Random Walks . . . . . . . . . 599

International Journal of Foundations of Computer Science (IJFCS)
Volume 16, Number 4, August, 2005

             Cristian S. Calude   Preface  . . . . . . . . . . . . . . . . 623
             Bernd Borchert and   
      Klaus-Jörn Lange and   
              Frank Stephan and   
              Pascal Tesson and   
           Denis Thérien   The Dot-Depth and the Polynomial
                                  Hierarchies Correspond on the Delta
                                  Levels . . . . . . . . . . . . . . . . . 625
         Jürgen Dassow and   
                  Markus Holzer   Language Families Defined by a Ciliate
                                  Bio-Operation: Hierarchies and Decision
                                  Problems . . . . . . . . . . . . . . . . 645
                  Rudolf Freund   $P$ Systems Working in the Sequential
                                  Mode on Arrays and Strings . . . . . . . 663
            Oscar H. Ibarra and   
               Hsu-Chun Yen and   
                       Zhe Dang   On Various Notions of Parallelism in $P$
                                  Systems  . . . . . . . . . . . . . . . . 683
                  Markus Lohrey   Decidability and Complexity in Automatic
                                  Monoids  . . . . . . . . . . . . . . . . 707
                Andreas Maletti   Relating Tree Series Transducers and
                                  Weighted Tree Automata . . . . . . . . . 723
              Anca Muscholl and   
               Igor Walukiewicz   An NP-Complete Fragment of LTL . . . . . 743
                Narad Rampersad   Words Avoiding $\frac{7}{3}$-powers and
                                  the Thue--Morse Morphism . . . . . . . . 755
        Chloé Rispal and   
                 Olivier Carton   Complementation of Rational Sets on
                                  Countable Scattered Linear Orderings . . 767
                 Ludwig Staiger   Infinite Iterated Function Systems in
                                  Cantor Space and the Hausdorff Measure
                                  of $\omega$-Power Languages  . . . . . . 787
               Takehiro Ito and   
                  Xiao Zhou and   
                Takao Nishizeki   Partitioning Trees of Supply and Demand  803

International Journal of Foundations of Computer Science (IJFCS)
Volume 16, Number 5, October, 2005

                      Anonymous   Preface  . . . . . . . . . . . . . . . . 829
          Janusz Brzozowski and   
          Helmut Jürgensen   Representation of Semiautomata by
                                  Canonical Words and Equivalences . . . . 831
      Jean-Marc Champarnaud and   
             Franck Guingne and   
                 Georges Hansel   Cover Transducers for Functions with
                                  Finite Domain  . . . . . . . . . . . . . 851
                   Zhe Dang and   
                Oscar H. Ibarra   On One-Membrane $P$ Systems Operating in
                                  Sequential Mode  . . . . . . . . . . . . 867
         Michael Domaratzki and   
                Keith Ellul and   
            Jeffrey Shallit and   
                  Ming-Wei Wang   Non-Uniqueness and Radius of Cyclic
                                  Unary NFAs . . . . . . . . . . . . . . . 883
         Michael Domaratzki and   
                    Kai Salomaa   Restricted Sets of Trajectories and
                                  Decidability of Shuffle Decompositions   897
          Piotr Faliszewski and   
           Lane A. Hemaspaandra   Advice for Semifeasible Sets and the
                                  Complexity-Theoretic Cost(Lessness) of
                                  Algebraic Properties . . . . . . . . . . 913
              Rudolf Freund and   
              Marion Oswald and   
                  Andrei P\uaun   Optimal Results for the Computational
                                  Completeness of Gemmating (Tissue) $P$
                                  Systems  . . . . . . . . . . . . . . . . 929
             Christos Kapoutsis   Non-Recursive Trade-Offs for Two-Way
                                  Machines . . . . . . . . . . . . . . . . 943
                  Martin Kutrib   The Phenomenon of Non-Recursive
                                  Trade-Offs . . . . . . . . . . . . . . . 957
                     Hing Leung   Descriptional Complexity of NFA of
                                  Different Ambiguity  . . . . . . . . . . 975
              Alexander Okhotin   A Characterization of the Arithmetical
                                  Hierarchy by Language Equations  . . . . 985
             Libor Polák   Minimalizations of NFA Using the
                                  Universal Automaton  . . . . . . . . . . 999
                Bettina Sunckel   On the Descriptional Complexity of
                                  Metalinear CD Grammar Systems  . . . . . 1011
               Lynette Van Zijl   Magic Numbers for Symmetric Difference
                                  NFAs . . . . . . . . . . . . . . . . . . 1027
                  Lila Kari and   
     Stavros Konstantinidis and   
              Petr Sosík   Bond-Free Languages: Formalizations,
                                  Maximality and Construction Methods  . . 1039

International Journal of Foundations of Computer Science (IJFCS)
Volume 16, Number 6, December, 2005

                      Jan Holub   Foreword . . . . . . . . . . . . . . . . 1071
                   Amihood Amir   Theoretical Issues of Searching Aerial
                                  Photographs: a Bird's Eye View . . . . . 1075
         Abdullah N. Arslan and   
        Ömer E\ugecio\uglu   Algorithms for the Constrained Longest
                                  Common Subsequence Problems  . . . . . . 1099
               Luigi Cinque and   
         Sergio De Agostino and   
            Franco Liberati and   
                 Bart Westgeest   A Simple Lossless Compression Heuristic
                                  for Grey Scale Images  . . . . . . . . . 1111
              Marc Fontaine and   
           Stefan Burkhardt and   
      Juha Kärkkäinen   BDD-based Analysis of Gapped $q$-Gram
                                  Filters  . . . . . . . . . . . . . . . . 1121
           Frantisek Franek and   
                    W. F. Smyth   Sorting Suffixes of Two-Pattern Strings  1135
       Costas S. Iliopoulos and   
               James Mchugh and   
          Pierre Peterlongo and   
              Nadia Pisanti and   
            Wojciech Rytter and   
             Marie-France Sagot   A First Approach to Finding Common
                                  Motifs with Gaps . . . . . . . . . . . . 1145
           Shunsuke Inenaga and   
            Ayumi Shinohara and   
                Masayuki Takeda   A Fully Compressed Pattern Matching
                                  Algorithm for Simple Collage Systems . . 1155
               Yair Kaufman and   
                Shmuel T. Klein   Semi-Lossless Text Compression . . . . . 1167
            Alban Mancheron and   
                Christophe Moan   Combinatorial Characterization of the
                                  Language Recognized by Factor and Suffix
                                  Oracles  . . . . . . . . . . . . . . . . 1179
      Ernest Ketcha Ngassam and   
            Bruce W. Watson and   
              Derrick G. Kourie   A Framework for the Dynamic
                                  Implementation of Finite Automata for
                                  Performance Enhancement  . . . . . . . . 1193
                Jan \vSupol and   
             Bo\vrivoj Melichar   Arithmetic Coding in Parallel  . . . . . 1207
                  Uli Laube and   
                   Maik Weinard   Conditional Inequalities and the
                                  Shortest Common Superstring Problem  . . 1219
                 Lili Zhang and   
              F. Blanchet-Sadri   Algorithms for Approximate $K$-Covering
                                  of Strings . . . . . . . . . . . . . . . 1231
          J.-M. Champarnaud and   
                      F. Coulon   Enumerating Nondeterministic Automata
                                  for a Given Language Without
                                  Constructing the Canonical Automaton . . 1253
           Giorgio Ausiello and   
            Cristina Bazgan and   
               Marc Demange and   
           Vangelis Th. Paschos   Completeness in Differential
                                  Approximation Classes  . . . . . . . . . 1267
            N. V. Vinodchandran   Nondeterministic Circuit Minimization
                                  Problem and Derandomizing Arthur--Merlin
                                  Games  . . . . . . . . . . . . . . . . . 1297
                      Anonymous   Author Index Volume 16 (2005)  . . . . . 1309


International Journal of Foundations of Computer Science (IJFCS)
Volume 17, Number 1, February, 2006

            Gheorghe P\uaun and   
Mario J. Pérez-Jiménez   Preface  . . . . . . . . . . . . . . . . 1
             Artiom Alhazov and   
              Rudolf Freund and   
                  Marion Oswald   Cell/Symbol Complexity of Tissue $P$
                                  Systems with Symport/Antiport Rules  . . 3
                Luca Bianco and   
           Federico Fontana and   
                 Vincenzo Manca   $P$ Systems with Reaction Maps . . . . . 27
              Luca Cardelli and   
                Gheorghe P\uaun   An Universality Result for a (Mem)Brane
                                  Calculus Based on Mate/Drip Operations   49
           Matteo Cavaliere and   
              Vincenzo Deufemia   Further Results on Time-Free $P$ Systems 69
            Rodica Ceterchi and   
Mario J. Pérez-Jiménez   On Simulating a Class of Parallel
                                  Architectures  . . . . . . . . . . . . . 91
            Gabriel Ciobanu and   
                Mihai Gontineac   Mealy Multiset Automata  . . . . . . . . 111
           Alberto Leporati and   
            Claudio Zandron and   
Miguel A. Gutiérrez-Naranjo   $P$ Systems with Input in Binary Form    127
           Michael Muskulus and   
                 Robert Brijder   Complexity of Bio-Computation: Symbolic
                                  Dynamics in Membrane Systems . . . . . . 147
               Adam Obtu\lowicz   Gandy's Principles for Mechanisms and
                                  Membrane Computing . . . . . . . . . . . 167
              Dario Pescini and   
            Daniela Besozzi and   
            Giancarlo Mauri and   
                Claudio Zandron   Dynamical Probabilistic $P$ Systems  . . 183
               Drago\cs Sburlan   Further Results on $P$ Systems with
                                  Promoters/Inhibitors . . . . . . . . . . 205
                 Shiyong Lu and   
        Arthur J. Bernstein and   
                Philip M. Lewis   Completeness and Realizability:
                                  Conditions for Automatic Generation of
                                  Workflows  . . . . . . . . . . . . . . . 223
                   U. Laube and   
                     M. Weinard   Erratum: ``Conditional Inequalities and
                                  the Shortest Common Superstring
                                  Problem''  . . . . . . . . . . . . . . . 247

International Journal of Foundations of Computer Science (IJFCS)
Volume 17, Number 2, April, 2006

                Koji Nakano and   
                Jacir L. Bordim   Preface  . . . . . . . . . . . . . . . . 249
              Thomas Rauber and   
             Gudula Rünger   A Data Re-Distribution Library for
                                  Multi-Processor Task Programming . . . . 251
             Krishnendu Roy and   
  Ramachandran Vaidyanathan and   
                Jerry L. Trahan   Routing Multiple Width Communications on
                                  the Circuit Switched Tree  . . . . . . . 271
               Mourad Hakem and   
                 Franck Butelle   Critical Path Scheduling Parallel
                                  Programs on an Unbounded Number of
                                  Processors . . . . . . . . . . . . . . . 287
            Sharareh Babvey and   
           Anu G. Bourgeois and   
José Alberto Fernández-Zepeda and   
           Steven W. Mclaughlin   Scalable and Efficient Implementations
                                  of the LDPC Decoder Using Reconfigurable
                                  Models . . . . . . . . . . . . . . . . . 303
                  Zhenyu Xu and   
              Pradip K. Srimani   Self-Stabilizing Anonymous Leader
                                  Election in a Tree . . . . . . . . . . . 323
              Meena Mahajan and   
              Raghavan Rama and   
            Venkatesh Raman and   
                  S. Vijaykumar   Approximate Block Sorting  . . . . . . . 337
                 Shiyong Lu and   
                   Feng Cao and   
                          Yi Lu   PAMA: a Fast String Matching Algorithm   357--378
                 Yo-Sub Han and   
                 Yajun Wang and   
                    Derick Wood   Infix-Free Regular Expressions and
                                  Languages  . . . . . . . . . . . . . . . 379
                   Zsolt Gazdag   Decidability of the Shape Preserving
                                  Property of Bottom-Up Tree Transducers   395
              Hong-Chun Hsu and   
             Cheng-Kuan Lin and   
               Hua-Min Hung and   
                  Lih-Hsing Hsu   The Spanning Connectivity of the
                                  $(n,k)$-Star Graphs  . . . . . . . . . . 415
           Nata\vsa Jonoska and   
           Joni Burnette Pirnot   Transitivity in Two-Dimensional Local
                                  Languages Defined by Dot Systems . . . . 435
                   Juha Honkala   The Base Problem for D0L Parikh Sets . . 465
             A. Ehrenfeucht and   
                   G. Rozenberg   Covers from Templates  . . . . . . . . . 475

International Journal of Foundations of Computer Science (IJFCS)
Volume 17, Number 3, June, 2006

           Clelia De Felice and   
                Antonio Restivo   Preface  . . . . . . . . . . . . . . . . 489
              Sergey Afonin and   
                  Elena Khazova   Membership and Finiteness Problems for
                                  Rational Sets of Regular Languages . . . 493
            D. S. Ananichev and   
               I. V. Petrov and   
                   M. V. Volkov   Collapsing Words: a Progress Report  . . 507
               Alexis B\`es and   
                 Olivier Carton   A Kleene Theorem for Languages of Words
                                  Indexed by Linear Orderings  . . . . . . 519
                   S. Brlek and   
                 G. Labelle and   
                     A. Lacasse   Properties of the Contour Path of
                                  Discrete Sets  . . . . . . . . . . . . . 543
               Aldo De Luca and   
             Alessandro De Luca   Combinatorial Properties of Sturmian
                                  Palindromes  . . . . . . . . . . . . . . 557
                Fernique Thomas   Multidimensional Sturmian Sequences and
                                  Generalized Substitutions  . . . . . . . 575
   Dominik D. Freydenberger and   
          Daniel Reidenbach and   
          Johannes C. Schneider   Unambiguous Morphic Images of Strings    601
              Alexander Okhotin   Generalized LR Parsing Algorithm for
                                  Boolean Grammars . . . . . . . . . . . . 629
            Elena V. Pribavkina   On Some Properties of the Language of
                                  $2$-Collapsing Words . . . . . . . . . . 665
                   Yung H. Tsin   An Efficient Distributed Algorithm for
                                  $3$-Edge-Connectivity  . . . . . . . . . 677
             Daiji Fukagawa and   
                 Tatsuya Akutsu   Fast Algorithms for Comparison of
                                  Similar Unordered Trees  . . . . . . . . 703

International Journal of Foundations of Computer Science (IJFCS)
Volume 17, Number 4, August, 2006

                      Farn Wang   Preface  . . . . . . . . . . . . . . . . 731
           E. Allen Emerson and   
          Kristina D. Hager and   
               Jay H. Konieczka   Molecular Model Checking . . . . . . . . 733
                Doron Peled and   
                    Hongyang Qu   Enforcing Concurrent Temporal Behaviors  743
          Freddy Y. C. Mang and   
                    Pei-Hsin Ho   Controllability and Cooperativeness
                                  Analysis for Automatic Abstraction
                                  Refinement . . . . . . . . . . . . . . . 763
                    Fang Yu and   
                   Bow-Yaw Wang   SAT-Based Model Checking for Region
                                  Automata . . . . . . . . . . . . . . . . 775
                 Robi Malik and   
             David Streader and   
                   Steve Reeves   Conflicts and Fair Testing . . . . . . . 797
   Ivan Cibrario Bertolotti and   
               Luca Durante and   
             Riccardo Sisto and   
              Adriano Valenzano   Exploiting Symmetries for Testing
                                  Equivalence Verification in the Spi
                                  Calculus . . . . . . . . . . . . . . . . 815
                Akio Nakata and   
           Tadaaki Tanimoto and   
              Suguru Sasaki and   
                Teruo Higashino   A Timed Failure Equivalence Preserving
                                  Abstraction for Parametric Time-Interval
                                  Automata . . . . . . . . . . . . . . . . 833
              Ehud Friedgut and   
             Orna Kupferman and   
                 Moshe Y. Vardi   Büchi Complementation Made Tighter  . . . 851
             Orna Kupferman and   
           Gila Morgenstern and   
                 Aniello Murano   Typeness for $\omega$-Regular Automata   869
             Ansgar Fehnker and   
                    Bruce Krogh   Hybrid System Verification is Not a
                                  Sinecure --- The Electronic Throttle
                                  Control Case Study . . . . . . . . . . . 885
                 Tatsuya Akutsu   Algorithms for Point Set Matching with
                                  $k$-Differences  . . . . . . . . . . . . 903
            Sylvain Gravier and   
           Philippe Jorrand and   
               Mehdi Mhalla and   
                  Charles Payan   Quantum Octal Games  . . . . . . . . . . 919
                 Xingqin Qi and   
                  Guojun Li and   
                 Jichang Wu and   
                  Bingqiang Liu   Sorting Signed Permutations by
                                  Fixed-Length Reversals . . . . . . . . . 933
                    Yuli Ye and   
              Janusz Brzozowski   Covering of Transient Simulation of
                                  Feedback-Free Circuits by Binary
                                  Analysis . . . . . . . . . . . . . . . . 949
            Gheorghe P\uaun and   
Mario J. Pérez-Jiménez and   
             Grzegorz Rozenberg   Spike Trains in Spiking Neural $P$
                                  Systems  . . . . . . . . . . . . . . . . 975

International Journal of Foundations of Computer Science (IJFCS)
Volume 17, Number 5, October, 2006

              Seok-Hee Hong and   
                   Hsu-Chun Yen   Preface  . . . . . . . . . . . . . . . . 1003
Károly J. Börözky and   
          János Pach and   
        Géza Tóth   Planar Crossing Numbers of Graphs
                                  Embeddable in Another Surface  . . . . . 1005
        Hubert De Fraysseix and   
   Patrice Ossona De Mendez and   
             Pierre Rosenstiehl   Trémaux Trees and Planarity . . . . . . . 1017
             Kazuyuki Miura and   
           Shin-Ichi Nakano and   
                Takao Nishizeki   Convex Grid Drawings of Four-Connected
                                  Plane Graphs . . . . . . . . . . . . . . 1031
            Maurizio Patrignani   On Extending a Partial Straight-Line
                                  Drawing  . . . . . . . . . . . . . . . . 1061
          Emilio Di Giacomo and   
            Giuseppe Liotta and   
               Francesco Trotta   On Embedding a Graph on Two Sets of
                                  Points . . . . . . . . . . . . . . . . . 1071
              Patrick Healy and   
                    Karol Lynch   Two Fixed-Parameter Tractable Algorithms
                                  for Testing Upward Planarity . . . . . . 1095
             Kazuyuki Miura and   
              Machiko Azuma and   
                Takao Nishizeki   Convex Drawings of Plane Graphs of
                                  Minimum Outer Apices . . . . . . . . . . 1115
              Huaming Zhang and   
                         Xin He   An Application of Well-Orderly Trees in
                                  Graph Drawing  . . . . . . . . . . . . . 1129
        Christian A. Duncan and   
                 Alon Efrat and   
           Stephen Kobourov and   
                    Carola Wenk   Drawing with Fat Edges . . . . . . . . . 1143
              Hiroshi Nagamochi   Packing Soft Rectangles  . . . . . . . . 1165
           Predrag T. To\vsi\'c   On the Complexity of Counting Fixed
                                  Points and Gardens of Eden in Sequential
                                  Dynamical Systems on Planar Bipartite
                                  Graphs . . . . . . . . . . . . . . . . . 1179
      Reihaneh Safavi-Naini and   
              Huaxiong Wang and   
                 Duncan S. Wong   Resilient LKH: Secure Multicast Key
                                  Distribution Schemes . . . . . . . . . . 1205
          Zbyn\vek K\vrivka and   
           Alexander Meduna and   
         Rudolf Schönecker   Generation of Languages by Rewriting
                                  Systems That Resemble Automata . . . . . 1223
          Janusz Brzozowski and   
          Helmut Jürgensen   Errata: \em Representation of
                                  Semiautomata by Canonical Words and
                                  Equivalences . . . . . . . . . . . . . . 1231

International Journal of Foundations of Computer Science (IJFCS)
Volume 17, Number 6, December, 2006

                      Jan Holub   Foreword . . . . . . . . . . . . . . . . 1233--1234
           Domenico Cantone and   
                    Simone Faro   A Space Efficient Bit-Parallel Algorithm
                                  for the Multiple String Matching Problem 1235--1251
              Loek Cleophas and   
               Kees Hemerik and   
                   Gerard Zwaan   Two Related Algorithms for
                                  Root-To-Frontier Tree Pattern Matching   1253--1272
             Sergio De Agostino   Bounded Size Dictionary Compression:
                                  Relaxing the LRU Deletion Heuristic  . . 1273--1280
           Frantisek Franek and   
               William F. Smyth   Reconstructing a Suffix Array  . . . . . 1281--1295
            Shmuel T. Klein and   
                   Dana Shapira   Compressed Pattern Matching in JPEG
                                  Images . . . . . . . . . . . . . . . . . 1297--1306
      Ernest Ketcha Ngassam and   
            Bruce W. Watson and   
              Derrick G. Kourie   Dynamic Allocation of Finite Automata
                                  States for Fast String Recognition . . . 1307--1323
          Heikki Hyyrö and   
                Gonzalo Navarro   Bit-Parallel Computation of Local
                                  Similarity Score Matrices with Unitary
                                  Weights  . . . . . . . . . . . . . . . . 1325--1344
          Kimmo Fredriksson and   
          Veli Mäkinen and   
                Gonzalo Navarro   Flexible Music Retrieval in Sublinear
                                  Time . . . . . . . . . . . . . . . . . . 1345--1364
           Szymon Grabowski and   
            Gonzalo Navarro and   
          Rafa\L Przywarski and   
         Alejandro Salinger and   
              Veli Mäkinen   A Simple Alphabet-Independent Fm-Index   1365--1384
        Élise Prieur and   
                 Thierry Lecroq   From Suffix Trees to Suffix Vectors  . . 1385--1402
              Joseph K. Liu and   
                 Duncan S. Wong   Enhanced Security Models and a Generic
                                  Construction Approach for Linkable Ring
                                  Signature  . . . . . . . . . . . . . . . 1403--1422
            Michel Paquette and   
                   Andrzej Pelc   Fast Broadcasting with Byzantine Faults  1423--1439
                Shuguang Li and   
                  Guojun Li and   
                     Xingqin Qi   Minimizing Total Weighted Completion
                                  Time on Identical Parallel Batch
                                  Machines . . . . . . . . . . . . . . . . 1441--1453
                    Amr Elmasry   A Priority Queue with the Working-Set
                                  Property . . . . . . . . . . . . . . . . 1455--1465
         Sebastian Wernicke and   
               Jochen Alber and   
                 Jens Gramm and   
                  Jiong Guo and   
               Rolf Niedermeier   The Computational Complexity of Avoiding
                                  Forbidden Submatrices by Row Deletions   1467--1484
                      Anonymous   Author Index Volume 17 (2006)  . . . . . 1485--1490


International Journal of Foundations of Computer Science (IJFCS)
Volume 18, Number 1, February, 2007

             Doron A. Peled and   
                  Yih-Kuen Tsay   Preface  . . . . . . . . . . . . . . . . 1--3
              Ittai Balaban and   
                Amir Pnueli and   
                 Lenore D. Zuck   Modular Ranking Abstraction  . . . . . . 5--44
                  Limor Fix and   
              Orna Grumberg and   
               Amnon Heyman and   
               Tamir Heyman and   
                 Assaf Schuster   Verifying Very Large Industrial Circuits
                                  Using 100 Processes and Beyond . . . . . 45--61
                Werner Damm and   
            Guilherme Pinto and   
                Stefan Ratschan   Guaranteed Termination in the
                                  Verification of LTL Properties of
                                  Non-Linear Robust Discrete Time Hybrid
                                  Systems  . . . . . . . . . . . . . . . . 63--86
      Stéphane Demri and   
                    David Nowak   Reasoning About Transfinite Sequences    87--112
                Sven Schewe and   
               Bernd Finkbeiner   Semi-Automatic Distributed Synthesis . . 113--138
               Tobias Lauer and   
             Thomas Ottmann and   
                  Amitava Datta   Update-Efficient Data Structures for
                                  Dynamic IP Router Tables . . . . . . . . 139--161
             Artiom Alhazov and   
             Yurii Rogozhin and   
                  Sergey Verlan   Minimal Cooperation in Symport/Antiport
                                  Tissue $P$ Systems . . . . . . . . . . . 163--179
                   Juha Honkala   The D0L $\omega$-Equivalence Problem . . 181--194

International Journal of Foundations of Computer Science (IJFCS)
Volume 18, Number 2, April, 2007

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

International Journal of Foundations of Computer Science (IJFCS)
Volume 18, Number 3, June, 2007

            Jacir L. Bordim and   
                    Koji Nakano   Preface  . . . . . . . . . . . . . . . . 433--434
            Gheorghe P\uaun and   
Mario J. Pérez-Jiménez and   
                   Arto Salomaa   Spiking Neural $P$ Systems: an Early
                                  Survey . . . . . . . . . . . . . . . . . 435--455
            Fabrizio Luccio and   
                Linda Pagli and   
                 Nicola Santoro   Network Decontamination in Presence of
                                  Local Immunity . . . . . . . . . . . . . 457--474
           Akihiro Fujiwara and   
              Satoshi Kamio and   
                 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 and   
                Koji Nakano and   
               Youhei Yamagishi   Efficient Hardware Algorithms for $n$
                                  Choose $k$ Counters Using the Bitonic
                                  Merger . . . . . . . . . . . . . . . . . 517--528
               Hanane Becha and   
                Paola Flocchini   Optimal Construction of Sense of
                                  Direction in a Torus by a Mobile Agent   529--546
            Paola Flocchini and   
             Miao Jun Huang and   
             Flaminia L. Luccio   Decontaminating Chordal Rings and Tori
                                  Using Mobile Agents  . . . . . . . . . . 547--563
              Alan J. Soper and   
           Vitaly A. Strusevich   An Improved Approximation Algorithm for
                                  the Two-Machine Flow Shop Scheduling
                                  Problem with an Interstage Transporter   565--591
              Benjamin Aziz and   
                 Geoff Hamilton   Modelling and Analysis of PKI-Based
                                  Systems Using Process Calculi  . . . . . 593--618
              Gautam K. Das and   
            Sasthi C. Ghosh and   
                Subhas C. Nandy   Improved Algorithm for Minimum Cost
                                  Range Assignment Problem for Linear
                                  Radio Networks . . . . . . . . . . . . . 619--635
               Jozef Gruska and   
         Salvatore La Torre and   
                  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

International Journal of Foundations of Computer Science (IJFCS)
Volume 18, Number 4, August, 2007

            Oscar H. Ibarra and   
                   Hsu-Chun Yen   Preface  . . . . . . . . . . . . . . . . 667--668
                        Ming Li   Information Distance and Its
                                  Applications . . . . . . . . . . . . . . 669--681
                Kai Salomaa and   
                       Sheng Yu   On the State Complexity of Combined
                                  Operations and Their Estimation  . . . . 683--698
        Parosh Aziz Abdulla and   
       Johanna Högberg and   
                     Lisa Kaati   Bisimulation Minimization of Tree
                                  Automata . . . . . . . . . . . . . . . . 699--713
      Cédric Bastien and   
            Jurek Czyzowicz and   
           Wojciech Fraczak and   
                Wojciech Rytter   Reducing Simple Grammars: Exponential
                                  Against Highly-Polynomial Time in
                                  Practice . . . . . . . . . . . . . . . . 715--725
             Roderick Bloem and   
         Alessandro Cimatti and   
                  Ingo Pill and   
                   Marco Roveri   Symbolic Implementation of Alternating
                                  Automata . . . . . . . . . . . . . . . . 727--743
            Henning Bordihn and   
              Markus Holzer and   
                  Martin Kutrib   Hybrid Extended Finite Automata  . . . . 745--760
             Corinna Cortes and   
              Mehryar Mohri and   
                 Ashish Rastogi   $L_p$ Distance and Equivalence of
                                  Probabilistic Automata . . . . . . . . . 761--779
          Maxime Crochemore and   
                Lucian Ilie and   
               Emine Seid-Hilmi   The Structure of Factor Oracles  . . . . 781--797
             Mathieu Giraud and   
             Phillipe Veber and   
             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 and   
      Jean-Marc Champarnaud and   
         Tibor Csáki and   
   Tamás Gaál and   
             André Kempe   Labelling Multi-Tape Automata with
                                  Constrained Symbol Classes . . . . . . . 847--858
     Martin \vSim\ocircunek and   
             Bo\vrivoj Melichar   Borders and Finite Automata  . . . . . . 859--871
             Elena Czeizler and   
          Juhani Karhumäki   On Non-Periodic Solutions of Independent
                                  Systems of Word Equations Over Three
                                  Unknowns . . . . . . . . . . . . . . . . 873--897
                Sudha Balla and   
    Sanguthevar Rajasekaran and   
                 Ion I. Mandoiu   Efficient Algorithms for Degenerate
                                  Primer Search  . . . . . . . . . . . . . 899--910

International Journal of Foundations of Computer Science (IJFCS)
Volume 18, Number 5, October, 2007

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

International Journal of Foundations of Computer Science (IJFCS)
Volume 18, Number 6, December, 2007

            Henning Bordihn and   
              Bernd Reichel and   
                Ralf Stiebe and   
                  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 and   
               Sigrid Ewert and   
              Ryan Schwartz and   
                 Mutahi Waruhiu   Table-Driven Context-Free Picture
                                  Grammars . . . . . . . . . . . . . . . . 1151--1160
               Oliver Boldt and   
          Helmut Jürgensen   Soliton Languages Are Nearly an Anti-AFL 1161--1165
             Elena Czeizler and   
    \vSt\vepán Holub and   
      Juhani Karhumäki and   
                   Markku Laine   Intricacies of Simple Word Equations: an
                                  Example  . . . . . . . . . . . . . . . . 1167--1175
                 Mark Daley and   
         Michael Domaratzki and   
                  Alexis Morris   Intra-Molecular Template-Guided
                                  Recombination  . . . . . . . . . . . . . 1177--1186
                   Frank Drewes   Links  . . . . . . . . . . . . . . . . . 1187--1196
  Zoltán Ésik and   
                   Werner Kuich   Boolean Fuzzy Sets . . . . . . . . . . . 1197--1207
                 Henning Fernau   Programmed Grammars with Rule Queues . . 1209--1213
              Rudolf Freund and   
                  Marion Oswald   Partial Halting in $P$ Systems . . . . . 1215--1225
                    Yan Gao and   
          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 and   
                 Sara Woodworth   Characterizing Regular Languages by
                                  Spiking Neural $P$ Systems . . . . . . . 1247--1256
      Helmut Jürgensen and   
                  Pauline Kraak   Soliton Automata Based on Trees  . . . . 1257--1270
              Andreas Klein and   
                  Martin Kutrib   Context-Free Grammars with Linked
                                  Nonterminals . . . . . . . . . . . . . . 1271--1282
                 Manfred Kudlek   Some Remarks on Quantum Automata . . . . 1283--1292
              Martin Kutrib and   
                Andreas Malcher   When Church--Rosser Becomes Context Free 1293--1302
              Enzo Magalini and   
            Giovanni Pighizzini   A Pumping Condition for Ultralinear
                                  Languages  . . . . . . . . . . . . . . . 1303--1312
            Andreas Malcher and   
                Bettina Sunckel   On Metalinear Parallel Communicating
                                  Grammar Systems  . . . . . . . . . . . . 1313--1322
         Carlos Martin-Vide and   
                 Victor Mitrana   Decision Problems on Path-Controlled
                                  Grammars . . . . . . . . . . . . . . . . 1323--1332
      Hartmut Messerschmidt and   
                 Friedrich Otto   Cooperating Distributed Systems of
                                  Restarting Automata  . . . . . . . . . . 1333--1342
    Franti\vsek Mráz and   
       Martin Plátek and   
            Tomasz Jurdzi\'nski   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 P\uaun and   
Mario J. Pérez-Jiménez and   
             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 and   
                 Paul Schofield   State Complexity of Additive Weighted
                                  Finite Automata  . . . . . . . . . . . . 1407--1416
                 Ludwig Staiger   Prefix-Free \Lukasiewicz Languages . . . 1417--1423
        Maurice H. Ter Beek and   
Erzsébet Csuhaj-Varjú and   
         György Vaszil and   
                  Markus Holzer   On Competence in CD Grammar Systems with
                                  Parallel Rewriting . . . . . . . . . . . 1425--1439
                   Sheng Yu and   
                      Qing Zhao   SC-Expressions in Object-Oriented
                                  Languages  . . . . . . . . . . . . . . . 1441--1452
                      Anonymous   Author Index Volume 18 (2007)  . . . . . 1453--1459


International Journal of Foundations of Computer Science (IJFCS)
Volume 19, Number 1, February, 2008

                      Jan Holub   Foreword . . . . . . . . . . . . . . . . 1--3
            Giuseppe Lancia and   
             Franca Rinaldi and   
                    Romeo Rizzi   Flipping Letters to Minimize the Support
                                  of a String  . . . . . . . . . . . . . . 5--17
      Christelle Melodelima and   
            Laurent Gueguen and   
          Christian Gautier and   
                    Didier Piau   A Markovian Approach for the Analysis of
                                  the Gene Structure . . . . . . . . . . . 19--35
    Manolis Christodoulakis and   
       Costas S. Iliopoulos and   
            M. Sohel Rahman and   
               William F. Smyth   Identifying Rhythms in Musical Texts . . 37--51
      Ernest Ketcha Ngassam and   
          Derrick G. Kourie and   
                Bruce W. Watson   On Implementation and Performance of
                                  Table-Driven DFA-Based String Processors 53--70
          Pierre Peterlongo and   
              Julien Allali and   
             Marie-France Sagot   Indexing Gapped-Factors Using a Tree . . 71--87
             Ehud S. Conley and   
                Shmuel T. Klein   Using Alignment for Multilingual Text
                                  Compression  . . . . . . . . . . . . . . 89--101
           Domenico Cantone and   
       Salvatore Cristofaro and   
                    Simone Faro   On Some Combinatorial Problems
                                  Concerning the Harmonic Structure of
                                  Musical Chord Sequences  . . . . . . . . 103--124
              Tinus Strauss and   
          Derrick G. Kourie and   
                Bruce W. Watson   A Concurrent Specification of
                                  Brzozowski's DFA Construction Algorithm  125--135
            Shmuel T. Klein and   
           Tamar C. Serebro and   
                   Dana Shapira   Modeling Delta Encoding of Compressed
                                  Files  . . . . . . . . . . . . . . . . . 137--146
                Yasuto Higa and   
               Hideo Bannai and   
           Shunsuke Inenaga and   
                Masayuki Takeda   Reachability on Suffix Tree Graphs . . . 147--162
          Kimmo Fredriksson and   
               Szymon Grabowski   Efficient algorithms for $(\delta,
                                  \gamma, \alpha)$ and $(\delta,
                                  \kappa_\delta, \alpha)$-matching . . . . 163--183
            Bruce W. Watson and   
          Derrick G. Kourie and   
              Tinus Strauss and   
              Ernest Ketcha and   
                  Loek Cleophas   Efficient Automata Constructions and
                                  Approximate Automata . . . . . . . . . . 185--193
           Frantisek Franek and   
                      Qian Yang   An Asymptotic Lower Bound for the
                                  Maximal Number of Runs in a String . . . 195--203
                 Steven Lindell   A Normal Form for First-Order Logic Over
                                  Doubly-Linked Data Structures  . . . . . 205--217
             Corinna Cortes and   
              Mehryar Mohri and   
             Ashish Rastogi and   
                  Michael Riley   On the Computation of the Relative
                                  Entropy of Probabilistic Automata  . . . 219--242
           Anton \vCerný   On Subword Symmetry of Words . . . . . . 243--250

International Journal of Foundations of Computer Science (IJFCS)
Volume 19, Number 2, April, 2008

            Sadok Ben Yahia and   
         Engelbert Mephu Nguifo   Preface  . . . . . . . . . . . . . . . . 251--254
  Radim B\velohlávek and   
                Jan Outrata and   
                 Vilem Vychodil   Fast Factorization by Similarity of
                                  Fuzzy Concept Lattices with Hedges . . . 255--269
             Tarek Hamrouni and   
            Sadok Ben Yahia and   
         Engelbert Mephu Nguifo   Succinct Minimal Generators: Theoretical
                                  Foundations and Applications . . . . . . 271--296
  Radim B\velohlávek and   
                 Vilem Vychodil   Basic Algorithm for Attribute
                                  Implications and Functional Dependencies
                                  in Graded Setting  . . . . . . . . . . . 297--317
              Peggy Cellier and   
Sébastien Ferré and   
             Olivier Ridoux and   
        Mireille Ducassé   A Parameterized Algorithm to Explore
                                  Formal Contexts with a Taxonomy  . . . . 319--343
              Tim B. Kaiser and   
          Stefan E. Schmidt and   
                Cliff A. Joslyn   Adjusting Annotated Taxonomies . . . . . 345--358
                 Jon Ducrou and   
                   Peter Eklund   An Intelligent User Interface for
                                  Browsing and Searching MPEG-7 Images
                                  Using Concept Lattices . . . . . . . . . 359--381
               Camille Roth and   
            Sergei Obiedkov and   
              Derrick G. Kourie   On Succinct Representation of Knowledge
                                  Community Taxonomies with Formal Concept
                                  Analysis . . . . . . . . . . . . . . . . 383--404
              Gautam K. Das and   
                Sasanka Roy and   
                 Sandip Das and   
                Subhas C. Nandy   Variations of Base-Station Placement
                                  Problem on the Boundary of a Convex
                                  Region . . . . . . . . . . . . . . . . . 405--427
            Daniela Berardi and   
              Fahima Cheikh and   
        Giuseppe De Giacomo and   
                  Fabio Patrizi   Automatic Service Composition Via
                                  Simulation . . . . . . . . . . . . . . . 429--451
      Jean-Marc Champarnaud and   
             Franck Guingne and   
         André Kempe and   
                 Florent Nicart   Algorithms for the Join and
                                  Auto-Intersection of Multi-Tape Weighted
                                  Finite-State Machines  . . . . . . . . . 453--476
             Vadim V. Lozin and   
                    Jordan Volz   The Clique-Width of Bipartite Graphs in
                                  Monogenic Classes  . . . . . . . . . . . 477--494

International Journal of Foundations of Computer Science (IJFCS)
Volume 19, Number 3, June, 2008

                 Tero Harju and   
          Juhani Karhumäki   Preface  . . . . . . . . . . . . . . . . 495--496
            Alberto Bertoni and   
              Roberto Radicioni   Approximating the Mean Speedup in Trace
                                  Monoids  . . . . . . . . . . . . . . . . 497--511
             Volker Diekert and   
                Paul Gastin and   
             Manfred Kufleitner   A Survey on Small Fragments of
                                  First-Order Logic Over Finite Words  . . 513--548
              Laurent Doyen and   
        Thomas A. Henzinger and   
    Jean-François Raskin   Equivalence of Labeled Markov Chains . . 549--563
         R\=usi\cn\vs Freivalds   Non-Constructive Methods for Finite
                                  Probabilistic Automata . . . . . . . . . 565--580
                 Yo-Sub Han and   
                    Kai Salomaa   State Complexity of Union and
                                  Intersection of Finite Languages . . . . 581--595
                    Artur Je\.z   Conjunctive Grammars Generate
                                  Non-Regular Unary Languages  . . . . . . 597--615
       Jozef Jirásek and   
Galina Jirásková and   
              Alexander Szabari   Deterministic Blow-Ups of Minimal
                                  Nondeterministic Finite Automata Over a
                                  Fixed Alphabet . . . . . . . . . . . . . 617--631
               Pascal Ochem and   
            Narad Rampersad and   
                Jeffrey Shallit   Avoiding Approximate Squares . . . . . . 633--648
               Victor Selivanov   Fine Hierarchy of Regular Aperiodic
                                  $\omega$-Languages . . . . . . . . . . . 649--675
                    Hellis Tamm   On Transition Minimality of
                                  Bideterministic Automata . . . . . . . . 677--690
                 Sebastian Link   On the Implication of Multivalued
                                  Dependencies in Partial Database
                                  Relations  . . . . . . . . . . . . . . . 691--715
                 Bala Ravikumar   The Benford--Newcomb Distribution and
                                  Unambiguous Context-Free Languages . . . 717--727
Erzsébet Csuhaj-Varjú and   
            Gheorghe P\uaun and   
             György Vaszil   Tissue-Like $P$ Systems with Dynamically
                                  Emerging Requests  . . . . . . . . . . . 729--745

International Journal of Foundations of Computer Science (IJFCS)
Volume 19, Number 4, August, 2008

             Viliam Geffert and   
            Giovanni Pighizzini   Preface  . . . . . . . . . . . . . . . . 747--749
              Marco Almeida and   
              Nelma Moreira and   
            Rogério Reis   Exact Generation of Minimal Acyclic
                                  Deterministic Finite Automata  . . . . . 751--765
              Rudolf Freund and   
                  Marion Oswald   Cd Grammar Systems with Regular Start
                                  Conditions . . . . . . . . . . . . . . . 767--779
              H. Jürgensen   Complexity, Information, Energy  . . . . 781--793
              Martin Kutrib and   
                   Jens Reimann   Optimal Simulations of Weak Restarting
                                  Automata . . . . . . . . . . . . . . . . 795--811
                 Remco Loos and   
            Andreas Malcher and   
                Detlef Wotschke   Descriptional Complexity of Splicing
                                  Systems  . . . . . . . . . . . . . . . . 813--826
               Carlo Mereghetti   Testing the Descriptional Power of Small
                                  Turing Machines on Nonregular Language
                                  Acceptance . . . . . . . . . . . . . . . 827--843
                Beatrice Palano   A Regularity Condition for Context-Free
                                  Grammars . . . . . . . . . . . . . . . . 845--857
            Gheorghe P\uaun and   
Mario J. Pérez-Jiménez and   
               Takashi Yokomori   Representations and Characterizations of
                                  Languages in Chomsky Hierarchy by Means
                                  of Insertion-Deletion Systems  . . . . . 859--871
                  Bianca Truthe   Remarks on Context-Free Parallel
                                  Communicating Grammar Systems Generating
                                  Crossed Agreements . . . . . . . . . . . 873--886
   Ji\vrí Wiedermann and   
          Dana Pardubská   Wireless Mobile Computing and Its Links
                                  to Descriptive Complexity  . . . . . . . 887--913
                Vesa Halava and   
                   Igor Potapov   Preface  . . . . . . . . . . . . . . . . 915--917
            Oscar H. Ibarra and   
                   Zhe Dang and   
                    Linmin Yang   On Counter Machines, Reachability
                                  Problems, and Diophantine Equations  . . 919--934
         Oleksiy Kurganskyy and   
               Igor Potapov and   
      Fernando Sancho-Caparrini   Reachability Problems in Low-Dimensional
                                  Iterative Maps . . . . . . . . . . . . . 935--951
             Alexei Lisitsa and   
             Andrei P. Nemytykh   Reachability Analysis in Verification
                                  Via Supercompilation . . . . . . . . . . 953--969
            Maurice Margenstern   The Finite Tiling Problem Is Undecidable
                                  in the Hyperbolic Plane  . . . . . . . . 971--982
                      Anil Seth   An Alternative Construction in Symbolic
                                  Reachability Analysis of Second Order
                                  Pushdown Systems . . . . . . . . . . . . 983--998
                   Hsu-Chun Yen   Decidability and Complexity Analysis of
                                  Forbidden State Problems for Discrete
                                  Event Systems  . . . . . . . . . . . . . 999--1013
          Sunil Kumar Gupta and   
              R. K. Chauhan and   
                  Parveen Kumar   A Minimum-Process Coordinated
                                  Checkpointing Protocol for Mobile
                                  Computing Systems  . . . . . . . . . . . 1015--1038
   Szilárd Zsolt Fazekas   On Inequalities Between Subword
                                  Histories  . . . . . . . . . . . . . . . 1039--1047
                   N. Imani and   
            H. Sarbazi-Azad and   
                      A. Zomaya   Intruder Capturing in Mesh and Torus
                                  Networks . . . . . . . . . . . . . . . . 1049--1071
            David E. Daykin and   
           Jacqueline W. Daykin   Properties and Construction of Unique
                                  Maximal Factorization Families for
                                  Strings  . . . . . . . . . . . . . . . . 1073--1084

International Journal of Foundations of Computer Science (IJFCS)
Volume 19, Number 5, October, 2008

         Michael Domaratzki and   
                    Kai Salomaa   Preface  . . . . . . . . . . . . . . . . 1085--1086
          Franziska Biegler and   
                 Mark Daley and   
          M. Elizabeth O. Locke   Computation by Annotation: Modelling
                                  Epigenetic Regulation  . . . . . . . . . 1087--1098
       Cezar Câmpeanu and   
         Stavros Konstantinidis   State Complexity of the Subword Closure
                                  Operation with Applications to DNA
                                  Coding . . . . . . . . . . . . . . . . . 1099--1112
            Cezara Dr\uagoi and   
                   Florin Manea   On the Descriptional Complexity of
                                  Accepting Networks of Evolutionary
                                  Processors with Filtered Connections . . 1113--1132
       Tseren-Onolt Ishdorj and   
                      Ion Petre   Gene Assembly Models and Boolean
                                  Circuits . . . . . . . . . . . . . . . . 1133--1145
                  John Jack and   
Alfonso Rodríguez-Patón and   
            Oscar H. Ibarra and   
                  Andrei P\uaun   Discrete Nondeterministic Modeling of
                                  the FAS Pathway  . . . . . . . . . . . . 1147--1162
                  Lila Kari and   
             Kalpana Mahalingam   Watson--Crick Bordered Words and Their
                                  Syntactic Monoid . . . . . . . . . . . . 1163--1179
Erzsébet Csuhaj-Varjú and   
             György Vaszil   Preface  . . . . . . . . . . . . . . . . 1181--1182
       Francesco Bernardini and   
            Marian Gheorghe and   
        Maurice Margenstern and   
                  Sergey Verlan   How to Synchronize the Activity of All
                                  Components of a $P$ System?  . . . . . . 1183--1198
               Radu Mardare and   
           Matteo Cavaliere and   
                  Sean Sedwards   A Logical Characterization of
                                  Robustness, Mutants and Species in
                                  Colonies of Agents . . . . . . . . . . . 1199--1221
              Rudolf Freund and   
              Mihai Ionescu and   
                  Marion Oswald   Extended Spiking Neural $P$ Systems with
                                  Decaying Spikes And/Or Total Spiking . . 1223--1234
            Maurice Margenstern   On a Characterization of Cellular
                                  Automata in Tilings of the Hyperbolic
                                  Plane  . . . . . . . . . . . . . . . . . 1235--1257
                Linmin Yang and   
                   Zhe Dang and   
                Oscar H. Ibarra   On Stateless Automata and $P$ Systems    1259--1276

International Journal of Foundations of Computer Science (IJFCS)
Volume 19, Number 6, December, 2008

            Jacir L. Bordim and   
                    Koji Nakano   Preface  . . . . . . . . . . . . . . . . 1277--1278
                 Zhen Jiang and   
                         Jie Wu   On Achieving the Shortest-Path Routing
                                  in $2$-D Meshes  . . . . . . . . . . . . 1279--1297
        Johannes Jendrsczok and   
              Rolf Hoffmann and   
               Jörg Keller   Implementing Hirschberg's PRAM-Algorithm
                                  for Connected Components on a Global
                                  Cellular Automaton . . . . . . . . . . . 1299--1316
              Jack Dongarra and   
Jean-François Pineau and   
                Yves Robert and   
                  Zhiao Shi and   
  Frédéric Vivien   Revisiting Matrix Product on
                                  Master-Worker Platforms  . . . . . . . . 1317--1336
José Alberto Fernández-Zepeda and   
Carlos Alberto Córdova-Flores and   
               Anu G. Bourgeois   Simulating an $R$-Mesh on an LR-Mesh in
                                  Constant Time  . . . . . . . . . . . . . 1337--1354
              Stefan Dobrev and   
             Nicola Santoro and   
                        Wei Shi   Using Scattered Mobile Agents to Locate
                                  a Black Hole in an Un-Oriented Ring with
                                  Tokens . . . . . . . . . . . . . . . . . 1355--1372
                Yasuaki Ito and   
                    Koji Nakano   A New FM Screening Method to Generate
                                  Cluster-Dot Binary Images Using the
                                  Local Exhaustive Search with FPGA
                                  Acceleration . . . . . . . . . . . . . . 1373--1386
José Alberto Fernández-Zepeda and   
Juan Paulo Alvarado-Magaña   Analysis of the Average Execution Time
                                  for a Self-Stabilizing Leader Election
                                  Algorithm  . . . . . . . . . . . . . . . 1387--1402
           M. V. Panduranga Rao   Generalized Counters and Reversal
                                  Complexity . . . . . . . . . . . . . . . 1403--1412
                Eddie Cheng and   
              Linda Lesniak and   
             Marc J. Lipman and   
László Lipták   Matching Preclusion for Alternating
                                  Group Graphs and Their Generalizations   1413--1437
          F. Blanchet-Sadri and   
                L. Bromberg and   
                      K. Zipple   Remarks on Two Nonstandard Versions of
                                  Periodicity in Words . . . . . . . . . . 1439--1448
             Ivan Fialík   Separation Between Classical and Quantum
                                  Winning Strategies for the Matching Game 1449--1459
           Markus Jalsenius and   
                Kasper Pedersen   A Systematic Scan for 7-Colourings of
                                  the Grid . . . . . . . . . . . . . . . . 1461--1477
                      Anonymous   Author Index Volume 19 (2008)  . . . . . 1479--1485


International Journal of Foundations of Computer Science (IJFCS)
Volume 20, Number 1, February, 2009

        Joachim Gudmundsson and   
                  James Harland   Preface  . . . . . . . . . . . . . . . . 1--2
                Hee-Kap Ahn and   
                 Helmut Alt and   
               Tetsuo Asano and   
               Sang Won Bae and   
                Peter Brass and   
             Otfried Cheong and   
           Christian Knauer and   
               Hyeon-Suk Na and   
               Chan-Su Shin and   
                Alexander Wolff   Constructing Optimal Highways  . . . . . 3--23
              Heidi Gebauer and   
                 Yoshio Okamoto   Fast Exponential-Time Algorithms for the
                                  Forest Counting and the Tutte Polynomial
                                  Computation in Graph Classes . . . . . . 25--44
          Regant Y. S. Hung and   
                     H. F. Ting   A Near-Optimal Broadcasting Protocol for
                                  Mobile Video-On-Demand . . . . . . . . . 45--55
           Jeremy E. Dawson and   
             Rajeev Goré   Termination of Abstract Reduction
                                  Systems  . . . . . . . . . . . . . . . . 57--82
               Peter Morris and   
        Thorsten Altenkirch and   
                     Neil Ghani   A Universe of Strictly Positive Families 83--107
                Damien Vergnaud   New Extensions of Pairing-Based
                                  Signatures into Universal (Multi)
                                  Designated Verifier Signatures . . . . . 109--133
        Joachim Gudmundsson and   
                   Michiel Smid   On Spanners of Geometric Graphs  . . . . 135--149
Virgil Nicolae \cSerb\uanu\ct\ua   On Parikh Matrices, Ambiguity, and
                                  Prints . . . . . . . . . . . . . . . . . 151--165
              Wolfgang Bein and   
        Lawrence L. Larmore and   
          Rüdiger Reischuk   Knowledge States for the Caching Problem
                                  in Shared Memory Multiprocessor Systems  167--183
      Hartmut Messerschmidt and   
                 Friedrich Otto   On Deterministic CD-Systems of
                                  Restarting Automata  . . . . . . . . . . 185--209

International Journal of Foundations of Computer Science (IJFCS)
Volume 20, Number 2, April, 2009

          K. G. Subramanian and   
              Ang Miin Huey and   
                Atulya K. Nagar   On Parikh Matrices . . . . . . . . . . . 211--219
        Torsten Stüber and   
               Heiko Vogler and   
  Zoltán Fülöp   Decomposition of Weighted Multioperator
                                  Tree Automata  . . . . . . . . . . . . . 221--245
     Natalia V. Shakhlevich and   
           Akiyoshi Shioura and   
           Vitaly A. Strusevich   Single Machine Scheduling with
                                  Controllable Processing Times by
                                  Submodular Optimization  . . . . . . . . 247--269
             Robert Brijder and   
      Hendrik Jan Hoogeboom and   
             Grzegorz Rozenberg   Reduction Graphs from Overlap Graphs for
                                  Gene Assembly in Ciliates  . . . . . . . 271--291
Katalin Anna Lázár and   
Erzsébet Csuhaj-Varjú and   
    András L\Horincz and   
             György Vaszil   Dynamically Formed Clusters of Agents in
                                  Eco-Grammar Systems  . . . . . . . . . . 293--311
           Ching-Lueh Chang and   
              Yuh-Dauh Lyuu and   
                      Yen-Wu Ti   Testing Embeddability Between Metric
                                  Spaces . . . . . . . . . . . . . . . . . 313--329
        Tomá\vs Masopust   On the Terminating Derivation Mode in
                                  Cooperating Distributed Grammar Systems
                                  with Forbidding Components . . . . . . . 331--340
      Ond\vrej Zají\vcek   A Note on Scheduling Parallel Unit Jobs
                                  on Hypercubes  . . . . . . . . . . . . . 341--349
              Cheng-Chi Lee and   
           Min-Shiang Hwang and   
              Shiang-Feng Tzeng   A New Convertible Authenticated
                                  Encryption Scheme Based on the ElGamal
                                  Cryptosystem . . . . . . . . . . . . . . 351--359
              Danny Z. Chen and   
              Mark A. Healy and   
                  Chao Wang and   
                         Bin Xu   Geometric Algorithms for the Constrained
                                  $1$-D $K$-Means Clustering Problems and
                                  IMRT Applications  . . . . . . . . . . . 361--377

International Journal of Foundations of Computer Science (IJFCS)
Volume 20, Number 3, June, 2009

              Petr Sosík   Preface  . . . . . . . . . . . . . . . . 379--380
            Gabriel Ciobanu and   
                Mihai Gontineac   Encodings of Multisets . . . . . . . . . 381--393
                   Dorel Lucanu   Rewriting Logic-Based Semantics of $P$
                                  Systems and the Maximal Concurrency  . . 395--410
               Thomas Hinze and   
            Raffael Fassler and   
            Thorsten Lenser and   
                 Peter Dittrich   Register Machine Computations on Binary
                                  Numbers by Oscillating and Catalytic
                                  Chemical Reactions Modelled Using
                                  Mass-Action Kinetics . . . . . . . . . . 411--426
Francisco J. Romero-Campero and   
             Jamie Twycross and   
       Miguel Cámara and   
            Malcolm Bennett and   
            Marian Gheorghe and   
              Natalio Krasnogor   Modular Assembly of Cell Systems Biology
                                  Models Using $P$ Systems . . . . . . . . 427--442
          Clemens Heuberger and   
               Helmut Prodinger   Analysis of Complements in
                                  Multi-Exponentiation Algorithms Using
                                  Signed Digit Representations . . . . . . 443--453
               Vladimir Rogojin   Successful Elementary Gene Assembly
                                  Strategies . . . . . . . . . . . . . . . 455--477
    Sanguthevar Rajasekaran and   
                  Vamsi Kundeti   Spectrum Based Techniques for Graph
                                  Isomorphism  . . . . . . . . . . . . . . 479--499
     Christian Glaßer and   
             Alan L. Selman and   
                     Liyu Zhang   The Informational Content of Canonical
                                  Disjoint NP-Pairs  . . . . . . . . . . . 501--522
               Josef \vSprojcar   Proposal of a Semiformal Model of
                                  Anonymous Communication  . . . . . . . . 523--548
                H. Ahrabian and   
          A. Nowzari-Dalini and   
              F. Zare-Mirakabad   A Constant Time Algorithm for DNA Add    549--558

International Journal of Foundations of Computer Science (IJFCS)
Volume 20, Number 4, August, 2009

            Oscar H. Ibarra and   
                 Bala Ravikumar   Preface  . . . . . . . . . . . . . . . . 559--561
              Markus Holzer and   
                  Martin Kutrib   Nondeterministic Finite Automata ---
                                  Recent Results on the Descriptional and
                                  Computational Complexity . . . . . . . . 563--580
                   Hsu-Chun Yen   Path Decomposition and Semilinearity of
                                  Petri Nets . . . . . . . . . . . . . . . 581--596
                 Ryan Dixon and   
    Ömer E\=gecio\=glu and   
               Timothy Sherwood   Analysis of Bit-Split Languages for
                                  Packet Scanning and Experiments with
                                  Wildcard Matching  . . . . . . . . . . . 597--612
             Cyril Allauzen and   
                  Mehryar Mohri   $N$-Way Composition of Weighted
                                  Finite-State Transducers . . . . . . . . 613--627
            Giovanni Pighizzini   Deterministic Pushdown Automata and
                                  Unary Languages  . . . . . . . . . . . . 629--645
     François Cantin and   
                 Axel Legay and   
                  Pierre Wolper   Computing Convex Hulls by Automata
                                  Iteration  . . . . . . . . . . . . . . . 647--667
              Marco Almeida and   
              Nelma Moreira and   
            Rogério Reis   Antimirov and Mosses's Rewrite System
                                  Revisited  . . . . . . . . . . . . . . . 669--684
        Parosh Aziz Abdulla and   
            Ahmed Bouajjani and   
Luká\vs Holík and   
                 Lisa Kaati and   
          Tomá\vs Vojnar   Composed Bisimulation for Tree Automata  685--700
              Harald Hempel and   
                Madlen Kimmritz   Aspects of Persistent Computations . . . 701--715
          Tetsuya Matsumoto and   
             Kazuhito Hagio and   
                Masayuki Takeda   A Run-Time Efficient Implementation of
                                  Compressed Pattern Matching Automata . . 717--733
                    Andrew Badr   Hyper-minimization in $O(n^2)$ . . . . . 735--746
              Yih-Kuen Tsay and   
                   Bow-Yaw Wang   Automated Compositional Reasoning of
                                  Intuitionistically Closed Regular
                                  Properties . . . . . . . . . . . . . . . 747--762
      Jean-Marc Champarnaud and   
    Jean Philippe Dubernard and   
                 Hadrien Jeanne   An Efficient Algorithm to Test Whether a
                                  Binary and Prolongeable Regular Language
                                  Is Geometrical . . . . . . . . . . . . . 763--774

International Journal of Foundations of Computer Science (IJFCS)
Volume 20, Number 5, October, 2009

                Vesa Halava and   
                   Igor Potapov   Preface  . . . . . . . . . . . . . . . . 775--777
        Parosh Aziz Abdulla and   
           Giorgio Delzanno and   
          Noomene Ben Henda and   
                   Ahmed Rezine   Monotonic Abstraction: on Efficient
                                  Verification of Parameterized Systems    779--801
          Juhani Karhumäki   On the Power of Cooperating Morphisms
                                  Via Reachability Problems  . . . . . . . 803--818
Étienne André and   
             Thomas Chatain and   
           Laurent Fribourg and   
            Emmanuelle Encrenaz   An Inverse Method for Parametric Timed
                                  Automata . . . . . . . . . . . . . . . . 819--836
              Yohan Boichut and   
              Romeo Courbis and   
        Pierre-Cyrille Heam and   
              Olga Kouchnarenko   Handling Non Left-Linear Rules When
                                  Completing Tree Automata . . . . . . . . 837--849
              Ingo Felscher and   
                Wolfgang Thomas   Compositionality and Reachability with
                                  Conditions on Path Lengths . . . . . . . 851--868
           Jan Friso Groote and   
                    Bas Ploeger   Switching Graphs . . . . . . . . . . . . 869--886
                Pavel Martyugin   The Length of Subset Reachability in
                                  Nondeterministic Automata  . . . . . . . 887--900
                 Arne Meier and   
             Michael Thomas and   
           Heribert Vollmer and   
                Martin Mundhenk   The Complexity of Satisfiability for
                                  Fragments of ${\cal CTL}$ and ${\cal
                                  CTL}*$ . . . . . . . . . . . . . . . . . 901--918
           Francois Nicolas and   
                  Yuri Pritykin   On Uniformly Recurrent Morphic Sequences 919--940
       Drago\vs Cvetkovi\'c and   
            Tatjana Davidovi\'c   Multiprocessor Interconnection Networks
                                  with Small Tightness . . . . . . . . . . 941--963

International Journal of Foundations of Computer Science (IJFCS)
Volume 20, Number 6, December, 2009

                      Jan Holub   Foreword . . . . . . . . . . . . . . . . 965--966
                Simone Faro and   
                 Thierry Lecroq   Efficient Variants of the
                                  Backward-Oracle-Matching Algorithm . . . 967--984
                W. F. Smyth and   
                       Shu Wang   An Adaptive Hybrid Pattern-Matching
                                  Algorithm on Indeterminate Strings . . . 985--1004
              Pawe\l Baturo and   
          Marcin Piatkowski and   
                Wojciech Rytter   Usefulness of Directed Acyclic Subword
                                  Graphs in Problems Related to Standard
                                  Sturmian Words . . . . . . . . . . . . . 1005--1023
      Matthias Gallé and   
          Pierre Peterlongo and   
          François Coste   In-Place Update of Suffix Array While
                                  Recoding Words . . . . . . . . . . . . . 1025--1045
    Manolis Christodoulakis and   
                   Gerhard Brey   Edit Distance with Combinations and
                                  Splits and Its Applications in OCR Name
                                  Matching . . . . . . . . . . . . . . . . 1047--1068
              Wikus Coetser and   
          Derrick G. Kourie and   
                Bruce W. Watson   On Regular Expression Hashing to Reduce
                                  FA Size  . . . . . . . . . . . . . . . . 1069--1086
           Domenico Cantone and   
       Salvatore Cristofaro and   
                    Simone Faro   New Efficient Bit-Parallel Algorithms
                                  for the $(\delta, \alpha)$-Matching
                                  Problem with Applications in Music
                                  Information Retrieval  . . . . . . . . . 1087--1108
                    Jie Lin and   
                  Yue Jiang and   
                    Don Adjeroh   The Virtual Suffix Tree  . . . . . . . . 1109--1133
            Kazuhiko Kusano and   
           Wataru Matsubara and   
               Akira Ishino and   
                Ayumi Shinohara   Average Value of Sum of Exponents of
                                  Runs in a String . . . . . . . . . . . . 1135--1146
                  Yumei Huo and   
         Joseph Y.-T. Leung and   
                       Xin Wang   Preemptive Scheduling Algorithms with
                                  Nested Processing Set Restriction  . . . 1147--1160
                      Anonymous   Author Index Volume 20 (2009)  . . . . . 1161--1166


International Journal of Foundations of Computer Science (IJFCS)
Volume 21, Number 1, February, 2010

              Etsuro Moriya and   
                 Friedrich Otto   On Alternating Phrase-Structure Grammars 1--25
               Klaus Jansen and   
              Roberto Solis-Oba   Approximation Schemes for Scheduling
                                  Jobs with Chain Precedence Constraints   27--49
            Yung-Hsing Peng and   
            Chang-Biau Yang and   
            Kuo-Tsung Tseng and   
                   Kuo-Si Huang   An Algorithm and Applications to
                                  Sequence Alignment with Weighted
                                  Constraints  . . . . . . . . . . . . . . 51--59
           Ching-Lueh Chang and   
                  Yuh-Dauh Lyuu   Efficient Testing of Forecasts . . . . . 61--72
           Jinn-Shyong Yang and   
             Jou-Ming Chang and   
            Shyue-Ming Tang and   
                    Yue-Li Wang   Constructing Multiple Independent
                                  Spanning Trees on Recursive Circulant
                                  Graphs $G(2^m, 2)$ . . . . . . . . . . . 73--90
               Arto Salomaa and   
                       Sheng Yu   Subword Occurrences, Parikh Matrices and
                                  Lyndon Images  . . . . . . . . . . . . . 91--111

International Journal of Foundations of Computer Science (IJFCS)
Volume 21, Number 2, April, 2010

             Kedar Namjoshi and   
                Tomohiro Yoneda   Preface  . . . . . . . . . . . . . . . . 113--114
            Geng-Dian Huang and   
                   Bow-Yaw Wang   Complete SAT-Based Model Checking for
                                  Context-Free Processes . . . . . . . . . 115--134
           Gilles Geeraerts and   
Jean-François Raskin and   
              Laurent Van Begin   On the Efficient Computation of the
                                  Minimal Coverability Set of Petri Nets   135--165
             Orna Kupferman and   
                    Yoad Lustig   Latticed Simulation Relations and Games  167--189
               Scott Little and   
               David Walter and   
                Kevin Jones and   
                Chris Myers and   
                      Alper Sen   Analog/Mixed-Signal Circuit Verification
                                  Using Models Generated from Simulation
                                  Traces . . . . . . . . . . . . . . . . . 191--210
               Edith Elkind and   
              Blaise Genest and   
                Doron Peled and   
                Paola Spoletini   Quantifying the Discord: Order
                                  Discrepancies in Message Sequence Charts 211--233
              Laura Recalde and   
               Serge Haddad and   
                   Manuel Silva   Continuous Petri Nets: Expressive Power
                                  and Decidability Issues  . . . . . . . . 235--256

International Journal of Foundations of Computer Science (IJFCS)
Volume 21, Number 3, June, 2010

            Andreas Maletti and   
C\uat\ualin Ionu\ct Tîrn\uauc\ua   Properties of Quasi-Relabeling Tree
                                  Bimorphisms  . . . . . . . . . . . . . . 257--276
               Oliver Friedmann   The Stevens-Stirling-Algorithm for
                                  Solving Parity Games Locally Requires
                                  Exponential Time . . . . . . . . . . . . 277--287
                Henning Schnoor   The Complexity of Model Checking for
                                  Boolean Formulas . . . . . . . . . . . . 289--309
                Aysun Aytac and   
            Zeynep Nihan Odabas   Computing the Rupture Degree in
                                  Composite Graphs . . . . . . . . . . . . 311--319
                  Yen-Wu Ti and   
           Ching-Lueh Chang and   
              Yuh-Dauh Lyuu and   
                 Alexander Shen   Sets of $k$-Independent Strings  . . . . 321--327
             Mihaela P\uaun and   
     Nichamon Naksinehaboon and   
                Raja Nassar and   
       Chokchai Leangsuksun and   
           Stephen L. Scott and   
                  Narate Taerat   Incremental Checkpoint Schemes for
                                  Weibull Failure Distribution . . . . . . 329--344
        Andrzej Ehrenfeucht and   
               Michael Main and   
             Grzegorz Rozenberg   Combinatorics of Life and Death for
                                  Reaction Systems . . . . . . . . . . . . 345--356
              Hans Kellerer and   
           Vitaly A. Strusevich   Minimizing Total Weighted
                                  Earliness-Tardiness on a Single Machine
                                  Around a Small Common Due Date: an FPTAS
                                  Using Quadratic Knapsack . . . . . . . . 357--383
            Jacir L. Bordim and   
           Akihiro Fujiwara and   
                    Koji Nakano   Preface  . . . . . . . . . . . . . . . . 385--386
                 Martti Forsell   On the Performance and Cost of Some PRAM
                                  Models on CMP Hardware . . . . . . . . . 387--404
                Yasuaki Ito and   
                    Koji Nakano   Low-Latency Connected Component Labeling
                                  Using an FPGA  . . . . . . . . . . . . . 405--425
                    Ei Ando and   
               Hirotaka Ono and   
          Kunihiko Sadakane and   
             Masafumi Yamashita   The Space Complexity of Leader Election
                                  in Anonymous Networks  . . . . . . . . . 427--440
            Stefan D. Bruda and   
                 Yuanqiao Zhang   Collapsing the Hierarchy of Parallel
                                  Computational Models . . . . . . . . . . 441--457
               Sayaka Kamei and   
             Hirotsugu Kakugawa   A Self-Stabilizing Distributed
                                  Approximation Algorithm for the Minimum
                                  Connected Dominating Set . . . . . . . . 459--476

International Journal of Foundations of Computer Science (IJFCS)
Volume 21, Number 4, August, 2010

                     Masami Ito   Preface  . . . . . . . . . . . . . . . . 477--478
                       Anil Ada   On the Non-Deterministic Communication
                                  Complexity of Regular Languages  . . . . 479--493
Frédérique Bassino and   
            Laura Giambruno and   
                   Cyril Nicaud   The Average State Complexity of Rational
                                  Operations on Finite Languages . . . . . 495--516
      Ond\vrej Klíma and   
             Libor Polák   Hierarchies of Piecewise Testable
                                  Languages  . . . . . . . . . . . . . . . 517--533
          Maxime Crochemore and   
Szilárd Zsolt Fazekas and   
       Costas S. Iliopoulos and   
               Inuka Jayasekera   Number of Occurrences of Powers in
                                  Strings  . . . . . . . . . . . . . . . . 535--547
Erzsébet Csuhaj-Varjú and   
         Jürgen Dassow and   
             György Vaszil   Variants of Competence-Based Derivations
                                  in CD Grammar Systems  . . . . . . . . . 549--569
            Emmanuel Filiot and   
           Jean-Marc Talbot and   
                   Sophie Tison   Tree Automata with Global Constraints    571--596
        Pawe\l Gawrychowski and   
              Dalia Krieger and   
            Narad Rampersad and   
                Jeffrey Shallit   Finding the Growth Rate of a Regular Or
                                  Context-Free Language in Polynomial Time 597--618
             Jens Glöckler   A Taxonomy of Deterministic Forgetting
                                  Automata . . . . . . . . . . . . . . . . 619--631
    \vSt\vepán Holub and   
                   Dirk Nowotka   On the Relation Between Periodicity and
                                  Unbordered Factors of Finite Words . . . 633--645
            Roberto Mantaci and   
            Sabrina Mantaci and   
                Antonio Restivo   Balance Properties and Distribution of
                                  Squares in Circular Words  . . . . . . . 647--664
              Rémi Morin   Unambiguous Shared-Memory Systems  . . . 665--685

International Journal of Foundations of Computer Science (IJFCS)
Volume 21, Number 5, October, 2010

Erzsébet Csuhaj-Varjú and   
      Zoltán Ésik   Preface  . . . . . . . . . . . . . . . . 687--688
              Sergey Afonin and   
                  Elena Khazova   On the Structure of Finitely Generated
                                  Semigroups of Unary Regular Languages    689--704
          F. Blanchet-Sadri and   
                 Taktin Oey and   
              Timothy D. Rankin   Fine and Wilf's Theorem for Partial
                                  Words with Arbitrarily Many Weak Periods 705--722
         Jürgen Dassow and   
                Ralf Stiebe and   
                  Bianca Truthe   Generative Capacity of Subregularly Tree
                                  Controlled Grammars  . . . . . . . . . . 723--740
           Michael Kaminski and   
                 Daniel Zeitlin   Finite-Memory Automata with
                                  Non-Deterministic Reassignment . . . . . 741--760
      Ond\vrej Klíma and   
             Libor Polák   Literally Idempotent Languages and Their
                                  Varieties --- Two Letter Case  . . . . . 761--780
              Martin Kutrib and   
      Hartmut Messerschmidt and   
                 Friedrich Otto   On Stateless Two-Pushdown Automata and
                                  Restarting Automata  . . . . . . . . . . 781--798
             Tommi Lehtinen and   
              Alexander Okhotin   Boolean Grammars and GSM Mappings  . . . 799--815
                  Markus Lohrey   Compressed Membership Problems for
                                  Regular Expressions and Hierarchical
                                  Automata . . . . . . . . . . . . . . . . 817--841
            Andreas Malcher and   
           Carlo Mereghetti and   
                Beatrice Palano   Sublinearly Space Bounded Iterative
                                  Arrays . . . . . . . . . . . . . . . . . 843--858
               Florin Manea and   
             Victor Mitrana and   
               Takashi Yokomori   Some Remarks on the Hairpin Completion   859--872


International Journal of Foundations of Computer Science (IJFCS)
Volume 22, Number 1, January, 2011

              Rudolf Freund and   
            Marian Gheorghe and   
             Solomon Marcus and   
             Victor Mitrana and   
Mario J. Pérez-Jiménez   Preface  . . . . . . . . . . . . . . . . 1--6
                Oscar H. Ibarra   On Strong Reversibility in $P$ Systems
                                  and Related Problems . . . . . . . . . . 7--14
         Kamala Krithivasan and   
    Venkata Padmavati Metta and   
                    Deepak Garg   On String Languages Generated by Spiking
                                  Neural P Systems with Anti-Spikes  . . . 15--27
               Linqiang Pan and   
  Daniel Díaz-Pernil and   
Mario J. Pérez-Jiménez   Computation of Ramsey Numbers by $P$
                                  Systems with Active Membranes  . . . . . 29--38
              Andrei P\uaun and   
             Mihaela P\uaun and   
Alfonso Rodríguez-Patón and   
               Manuela Sidoroff   $P$ Systems with Proteins on Membranes:
                                  a Survey . . . . . . . . . . . . . . . . 39--53
Ignacio Pérez-Hurtado and   
Mario J. Pérez-Jiménez and   
Agustín Riscos-Núñez and   
Miguel A. Gutiérrez-Naranjo and   
               Miquel Rius-Font   On a Partial Affirmative Answer for a
                                  P\uaun's Conjecture  . . . . . . . . . . 55--64
         Antonio E. Porreca and   
           Alberto Leporati and   
            Giancarlo Mauri and   
                Claudio Zandron   $P$ Systems with Active Membranes
                                  Working in Polynomial Space  . . . . . . 65--73
          Petr Sosík and   
Alfonso Rodríguez-Patón and   
              Lud\vek Cienciala   On the Power of Families of Recognizer
                                  Spiking Neural $P$ Systems . . . . . . . 75--88
            Daniela Besozzi and   
            Paolo Cazzaniga and   
            Stefania Cocolo and   
            Giancarlo Mauri and   
                  Dario Pescini   Modeling Diffusion in a Signal
                                  Transduction Pathway: the Use of Virtual
                                  Volumes in $P$ Systems . . . . . . . . . 89--96
             Vincenzo Manca and   
                 Luca Marchetti   Log-Gain Stoichiometric Stepwise
                                  Regression for MP Systems  . . . . . . . 97--106
M. A. Martínez-Del-Amor and   
    I. Pérez-Hurtado and   
M. J. Pérez-Jiménez and   
A. Riscos-Núñez and   
            F. Sancho-Caparrini   A Simulation Algorithm for
                                  Multienvironment Probabilistic $P$
                                  Systems: a Formal Verification . . . . . 107--118
            Roberto Barbuti and   
  Andrea Maggiolo-Schettini and   
              Paolo Milazzo and   
                    Simone Tini   An Overview on Operational Semantics in
                                  Membrane Computing . . . . . . . . . . . 119--131
            Florentin Ipate and   
           Raluca Lefticaru and   
                Cristina Tudose   Formal Verification of $P$ Systems Using
                                  Spin . . . . . . . . . . . . . . . . . . 133--142
             Artiom Alhazov and   
              Marian Kogler and   
        Maurice Margenstern and   
             Yurii Rogozhin and   
                  Sergey Verlan   Small Universal TVDH and Test Tube
                                  Systems  . . . . . . . . . . . . . . . . 143--154
    Fernando Arroyo Montoro and   
           Juan Castellanos and   
             Victor Mitrana and   
             Eugenio Santos and   
                Jose M. Sempere   Filter Position in Networks of
                                  Substitution Processors Does Not Matter  155--165
        Andrzej Ehrenfeucht and   
               Michael Main and   
             Grzegorz Rozenberg   Functions Defined by Reaction Systems    167--178
           Pierluigi Frisco and   
          Hendrik Jan Hoogeboom   $P$ Systems and Topology: Some
                                  Suggestions for Research . . . . . . . . 179--190
         Cristian S. Calude and   
           Matteo Cavaliere and   
                   Radu Mardare   An Observer-Based De-Quantisation of
                                  Deutsch's Algorithm  . . . . . . . . . . 191--201
Erzsébet Csuhaj-Varjú and   
              Marion Oswald and   
             György Vaszil   PC Grammar Systems with Clusters of
                                  Components . . . . . . . . . . . . . . . 203--212
                 Mark Daley and   
                  Lila Kari and   
            Shinnosuke Seki and   
                   Petr Sos\`ik   Orthogonal Shuffle on Trajectories . . . 213--222
         Jürgen Dassow and   
             György Vaszil   On the Number of Active Symbols in
                                  Lindenmayer Systems  . . . . . . . . . . 223--235
            Miroslav Langer and   
        Alica Kelemenová   Positioned Agents in Eco-Grammar Systems 237--246
               Fumiya Okubo and   
               Takashi Yokomori   Morphic Characterizations of Language
                                  Families in Terms of Insertion Systems
                                  and Star Languages . . . . . . . . . . . 247--260
                   Arto Salomaa   Power Sums Associated with Certain
                                  Recursive Procedures on Words  . . . . . 261--272
          Radu-Florian Atanasiu   Erratum: \em Parikh Matrix Mapping and
                                  Languages  . . . . . . . . . . . . . . . 273--273

International Journal of Foundations of Computer Science (IJFCS)
Volume 22, Number 2, February, 2011

             Volker Diekert and   
                   Dirk Nowotka   Preface  . . . . . . . . . . . . . . . . 275--276
   Marie-Pierre Béal and   
       Mikhail V. Berlinkov and   
               Dominique Perrin   A Quadratic Upper Bound on the Size of a
                                  Synchronizing Word in One-Cluster
                                  Automata . . . . . . . . . . . . . . . . 277--288
            Alberto Bertoni and   
         Christian Choffrut and   
              Roberto Radicioni   The Inclusion Problem of Context-Free
                                  Languages: Some Tractable Cases  . . . . 289--299
          Janusz Brzozowski and   
                Elyot Grant and   
                Jeffrey Shallit   Closures in Formal Languages and
                                  Kuratowski's Theorem . . . . . . . . . . 301--321
   Szilárd Zsolt Fazekas   Powers of Regular Languages  . . . . . . 323--330
 Galina Jirásková   Magic Numbers and Ternary Alphabet . . . 331--344
               Markku Laine and   
            Wojciech Plandowski   Word Equations with One Unknown  . . . . 345--375
             Tommi Lehtinen and   
              Alexander Okhotin   On Equations Over Sets of Numbers and
                                  Their Limitations  . . . . . . . . . . . 377--393
                Holger Petersen   Simulations by Time-Bounded Counter
                                  Machines . . . . . . . . . . . . . . . . 395--409
                 Georg Zetzsche   Toward Understanding the Generative
                                  Capacity of Erasing Rules in Matrix
                                  Grammars . . . . . . . . . . . . . . . . 411--426
               Zsolt Gazdag and   
 Zoltán L. Németh   A Kleene Theorem for Bisemigroup and
                                  Binoid Languages . . . . . . . . . . . . 427--446
                  Lila Kari and   
        Benoît Masson and   
                Shinnosuke Seki   Properties of Pseudo-Primitive Words and
                                  Their Applications . . . . . . . . . . . 447--471
                Vesa Halava and   
        \vSt\vepán Holub   Reduction Tree of the Binary Generalized
                                  Post Correspondence Problem  . . . . . . 473--490
                S. L. Bloom and   
                 Z. Ésik   Algebraic Linear Orderings . . . . . . . 491--515

International Journal of Foundations of Computer Science (IJFCS)
Volume 22, Number 3, April, 2011

            Jacir L. Bordim and   
                Koji Nakano and   
               Akihiro Fujiwara   Preface  . . . . . . . . . . . . . . . . 517--518
               Javid Taheri and   
               Albert Y. Zomaya   On the Performance of Static and Dynamic
                                  Location Management Strategies in Mobile
                                  Computing  . . . . . . . . . . . . . . . 519--546
           Akihiro Fujiwara and   
               Takeshi Tateishi   Logic and Arithmetic Operations with a
                                  Constant Number of Steps in Membrane
                                  Computing  . . . . . . . . . . . . . . . 547--564
  Flávio K. Miyazawa and   
       André L. Vignatti   Bounds on the Convergence Time of
                                  Distributed Selfish Bin Packing  . . . . 565--582
             Yuichi Asahiro and   
             Jesper Jansson and   
                Eiji Miyano and   
                   Hirotaka Ono   Graph Orientation to Maximize the
                                  Minimum Weighted Outdegree . . . . . . . 583--601
                        Wei Sun   Population Size Modeling for Ga in
                                  Time-Critical Task Scheduling  . . . . . 603--620
                Anne Benoit and   
       Veronika Rehn-Sonigo and   
                Yves Robert and   
                 Henri Casanova   Resource Allocation Strategies for
                                  Constructive In-Network Stream
                                  Processing . . . . . . . . . . . . . . . 621--638
             Marin Bougeret and   
Pierre-François Dutot and   
            Alfredo Goldman and   
                Yanik Ngoko and   
                 Denis Trystram   Approximating the Discrete Resource
                                  Sharing Scheduling Problem . . . . . . . 639--656
              Ajoy K. Datta and   
   Stéphane Devismes and   
               Florian Horn and   
            Lawrence L. Larmore   Self-stabilizing $k$-out-of-$\ell$
                                  exclusion in tree networks . . . . . . . 657--677
            Lali Barri\`ere and   
            Paola Flocchini and   
     Eduardo Mesa-Barrameda and   
                 Nicola Santoro   Uniform Scattering of Autonomous Mobile
                                  Robots in a Grid . . . . . . . . . . . . 679--697
        \vSt\vepán Holub   Binary Morphisms with Stable Suffix
                                  Complexity . . . . . . . . . . . . . . . 699--712
          Sushanta Karmakar and   
                 Arobinda Gupta   Adaptive Distributed Mutual Exclusion by
                                  Dynamic Topology Switching . . . . . . . 713--737
                 Han-Yu Lin and   
                 Chien-Lung Hsu   A Novel Identity-Based Key-Insulated
                                  Convertible Authenticated Encryption
                                  Scheme . . . . . . . . . . . . . . . . . 739--756

International Journal of Foundations of Computer Science (IJFCS)
Volume 22, Number 4, June, 2011

            Olivier Bournez and   
                   Igor Potapov   Preface  . . . . . . . . . . . . . . . . 757--760
        Parosh Aziz Abdulla and   
           Giorgio Delzanno and   
                   Ahmed Rezine   Automatic Verification of
                                  Directory-Based Consistency Protocols
                                  with Graph Constraints . . . . . . . . . 761--782
        Mohamed Faouzi Atig and   
                Peter Habermehl   On Yen's Path Logic for Petri Nets . . . 783--799
             Pieter Collins and   
                Ivan S. Zapreev   Computable Semantics for Ctl* on
                                  Discrete-Time and Continuous-Space
                                  Dynamic Systems  . . . . . . . . . . . . 801--821
           Thomas Henzinger and   
          Barbara Jobstmann and   
                    Verena Wolf   Formalisms for Specifying Markovian
                                  Population Models  . . . . . . . . . . . 823--841
                   Denis Lugiez   Forward Analysis of Dynamic Network of
                                  Pushdown Systems Is Easier Without Order 843--862
             Amaldev Manuel and   
                   R. Ramanujam   Class Counting Automata on Datawords . . 863--882
             Cyril Allauzen and   
              Mehryar Mohri and   
                 Ashish Rastogi   General Algorithms for Testing the
                                  Ambiguity of Finite Automata and the
                                  Double-Tape Ambiguity of Finite-State
                                  Transducers  . . . . . . . . . . . . . . 883--904
           Julien Cassaigne and   
Gwénaël Richomme and   
                Kalle Saari and   
                Luca Q. Zamboni   Avoiding Abelian Powers in Binary Words
                                  with Bounded Abelian Complexity  . . . . 905--920
                 Meng Zhang and   
                   Liang Hu and   
                       Yi Zhang   Weighted Automata for Full-Text Indexing 921--943
            Gonzalo Navarro and   
            Rodrigo Paredes and   
        Patricio V. Poblete and   
                  Peter Sanders   Stronger Quickheaps  . . . . . . . . . . 945--969
                   Deshi Ye and   
                     Qinming He   Worst-Case Performance Evaluation on
                                  Multiprocessor Task Scheduling with
                                  Resource Augmentation  . . . . . . . . . 971--982
            Debashis Mondal and   
                Abhay Kumar and   
              Arijit Bishnu and   
   Krishnendu Mukhopadhyaya and   
                Subhas C. Nandy   Measuring the Quality of Surveillance in
                                  a Wireless Sensor Network  . . . . . . . 983--998

International Journal of Foundations of Computer Science (IJFCS)
Volume 22, Number 5, August, 2011

           Akihiro Fujiwara and   
         Hirotsugu Kakugawa and   
                    Koji Nakano   Preface  . . . . . . . . . . . . . . . . 999--1000
                   Yamin Li and   
              Shietung Peng and   
                    Wanming Chu   Disjoint-Paths and Fault-Tolerant
                                  Routing on Recursive Dual-Net  . . . . . 1001--1018
                 Shihong Xu and   
                      Hong Shen   A Distributed Approximation Algorithm
                                  for Fault-Tolerant Metric Facility
                                  Location . . . . . . . . . . . . . . . . 1019--1034
           Marc Moreno Maza and   
                     Yuzhen Xie   Balanced Dense Polynomial Multiplication
                                  on Multi-Cores . . . . . . . . . . . . . 1035--1055
                   Duhu Man and   
                Yasuaki Ito and   
                    Koji Nakano   An Efficient Parallel Sorting Compatible
                                  with the Standard Qsort  . . . . . . . . 1057--1071
               Shlomi Dolev and   
              Yuval Elovici and   
             Alex Kesselman and   
               Polina Zilberman   Trawling Traffic Under Attack Overcoming
                                  DDOS Attacks by Target-Controlled
                                  Traffic Filtering  . . . . . . . . . . . 1073--1098
            Yukiko Yamauchi and   
                 Doina Bein and   
            Toshimitsu Masuzawa   Reliable Communication on Emulated
                                  Channels Resilient to Transient Faults   1099--1122
        Emmanuelle Anceaume and   
       Francisco Brasileiro and   
           Romaric Ludinard and   
             Bruno Sericola and   
  Frédéric Tronel   Dependability Evaluation of
                                  Cluster-Based Distributed Systems  . . . 1123--1142
           Fabienne Carrier and   
   Stéphane Devismes and   
               Franck Petit and   
                  Yvan Rivierre   Asymptotically Optimal Deterministic
                                  Rendezvous . . . . . . . . . . . . . . . 1143--1159
        Abusayeed Saifullah and   
                   Yung H. Tsin   Self-Stabilizing Computation of
                                  3-Edge-Connected Components  . . . . . . 1161--1185
                Aysun Aytac and   
                   Tufan Turaci   Vertex Vulnerability Parameter of Gear
                                  Graphs . . . . . . . . . . . . . . . . . 1187--1195
                 Yo-Sub Han and   
                    Kai Salomaa   Overlap-Free Languages and Solid Codes   1197--1209
             Takaaki Mizuki and   
            Satoru Nakayama and   
                   Hideaki Sone   An Application of ST-Numbering to Secret
                                  Key Agreement  . . . . . . . . . . . . . 1211--1227
         Aysun Aytaç and   
          Zeynep Nihan Odaba\cs   Residual Closeness of Wheels and Related
                                  Networks . . . . . . . . . . . . . . . . 1229--1240

International Journal of Foundations of Computer Science (IJFCS)
Volume 22, Number 6, September, 2011

              Cunsheng Ding and   
                        Qi Wang   Preface  . . . . . . . . . . . . . . . . 1241--1241
            Lilya Budaghyan and   
                  Tor Helleseth   On Isotopisms of Commutative
                                  Presemifields and CCZ-Equivalence of
                                  Functions  . . . . . . . . . . . . . . . 1243--1258
                  Claude Carlet   More Vectorial Boolean Functions with
                                  Unbounded Nonlinearity Profile . . . . . 1259--1269
                 Keqin Feng and   
                      Jing Yang   Vectorial Boolean Functions with Good
                                  Cryptographic Properties . . . . . . . . 1271--1282
                Xiutao Feng and   
               Zhenqing Shi and   
                Chuankun Wu and   
                   Dengguo Feng   On Guess and Determine Analysis of
                                  Rabbit . . . . . . . . . . . . . . . . . 1283--1296
               Mark Goresky and   
                 Andrew Klapper   Statistical Properties of the Arithmetic
                                  Correlation of Sequences . . . . . . . . 1297--1315
                Honggang Hu and   
                     Guang Gong   Periods on Two Kinds of Nonlinear
                                  Feedback Shift Registers with Time
                                  Varying Feedback Functions . . . . . . . 1317--1329
                 Xuelian Li and   
                    Yupu Hu and   
                     Juntao Gao   Lower Bounds on the Second Order
                                  Nonlinearity of Boolean Functions  . . . 1331--1349
            Laurent Poinsot and   
                 Alexander Pott   Non-Boolean Almost Perfect Nonlinear
                                  Functions on Non-Abelian Groups  . . . . 1351--1367
      Reihaneh Safavi-Naini and   
                 Shaoquan Jiang   Unconditionally Secure Conference Key
                                  Distribution: Security Notions, Bounds
                                  and Constructions  . . . . . . . . . . . 1369--1393
         Christophe Tartary and   
              Huaxiong Wang and   
                      Yun Zhang   An Efficient and Information
                                  Theoretically Secure Rational Secret
                                  Sharing Scheme Based on Symmetric
                                  Bivariate Polynomials  . . . . . . . . . 1395--1416
                  Yang Yang and   
                Xiaohu Tang and   
               Udaya Parampalli   Authentication Codes from Difference
                                  Balanced Functions . . . . . . . . . . . 1417--1429
                  Yin Zhang and   
               Meicheng Liu and   
                    Dongdai Lin   On the Nonexistence of Bent Functions    1431--1438
              Danny Z. Chen and   
                    Haitao Wang   Processing an Offline Insertion-Query
                                  Sequence with Applications . . . . . . . 1439--1456
        Hamed M. K. Alazemi and   
           Anton \vCerný   Counting Subwords Using a Trie Automaton 1457--1469
        Arnold L. Rosenberg and   
                  Ron C. Chiang   Heterogeneity in Computing: Insights
                                  from a Worksharing Scheduling Problem    1471--1493

International Journal of Foundations of Computer Science (IJFCS)
Volume 22, Number 7, November, 2011

                       Sheng Yu   Preface  . . . . . . . . . . . . . . . . 1495--1498
             Robert Brijder and   
        Andrzej Ehrenfeucht and   
               Michael Main and   
             Grzegorz Rozenberg   A Tour of Reaction Systems . . . . . . . 1499--1517
               Dora Giammarresi   Exploring Inside Tiling Recognizable
                                  Picture Languages to Find Deterministic
                                  Subclasses . . . . . . . . . . . . . . . 1519--1532
              Markus Holzer and   
                  Martin Kutrib   The Complexity of Regular(-Like)
                                  Expressions  . . . . . . . . . . . . . . 1533--1548
                Michel Rigo and   
              Laurent Waxweiler   Logical Characterization of Recognizable
                                  Sets of Polynomials Over a Finite Field  1549--1563
           Mikhail V. Berlinkov   On a Conjecture by Carpi and
                                  D'Alessandro . . . . . . . . . . . . . . 1565--1576
            Henning Bordihn and   
              Martin Kutrib and   
                Andreas Malcher   Undecidability and Hierarchy Results for
                                  Parallel Communicating Finite Automata   1577--1592
               Sabine Broda and   
  António Machiavelo and   
              Nelma Moreira and   
            Rogério Reis   On the Average State Complexity of
                                  Partial Derivative Automata: an Analytic
                                  Combinatorics Approach . . . . . . . . . 1593--1606
              Sylvia Friese and   
               Helmut Seidl and   
               Sebastian Maneth   Earliest Normal Form and Minimization
                                  for Bottom-Up Tree Transducers . . . . . 1607--1623
                       Tom Head   Computing with Light: Toward Parallel
                                  Boolean Algebra  . . . . . . . . . . . . 1625--1637
Galina Jirásková and   
        Tomá\vs Masopust   Complexity in Union-Free Regular
                                  Languages  . . . . . . . . . . . . . . . 1639--1653
                  Lila Kari and   
                Shinnosuke Seki   Schema for Parallel Insertion and
                                  Deletion: Revisited  . . . . . . . . . . 1655--1668
           Elena Pribavkina and   
                Emanuele Rodaro   State Complexity of Code Operators . . . 1669--1681
                 Arseny M. Shur   On the Existence of Minimal
                                  $\beta$-Powers . . . . . . . . . . . . . 1683--1696
             Benjamin Steinberg   The Averaging Trick and the \vCerný
                                  Conjecture . . . . . . . . . . . . . . . 1697--1706
               Saladi Rahul and   
            Prosenjit Gupta and   
                    K. S. Rajan   Data Structures for Range-Aggregation
                                  Over Categories  . . . . . . . . . . . . 1707--1728
                 Allen Yuan and   
                Eddie Cheng and   
László Lipták   Linearly Many Faults in $(n, k)$-star
                                  graphs . . . . . . . . . . . . . . . . . 1729--1745
       Lakshmanan Kuppusamy and   
            Anand Mahendran and   
             Kamala Krithivasan   On the Ambiguity of Insertion Systems    1747--1758

International Journal of Foundations of Computer Science (IJFCS)
Volume 22, Number 8, December, 2011

         Michael Domaratzki and   
                    Kai Salomaa   Preface  . . . . . . . . . . . . . . . . 1759--1760
             Cyril Allauzen and   
             Corinna Cortes and   
                  Mehryar Mohri   A dual coordinate descent algorithm for
                                  SVMs combined with rational kernels  . . 1761--1779
             Cyril Allauzen and   
              Michael Riley and   
                Johan Schalkwyk   A Filter-Based Algorithm for Efficient
                                  Composition of Finite-State Transducers  1781--1795
                     Bo Cui and   
                   Yuan Gao and   
                  Lila Kari and   
                       Sheng Yu   State Complexity of Two Combined
                                  Operations: Catenation-Union and
                                  Catenation-Intersection  . . . . . . . . 1797--1812
             Volker Diekert and   
                Steffen Kopecki   It Is NL-Complete to Decide Whether a
                                  Hairpin Completion of Regular Languages
                                  Is Regular . . . . . . . . . . . . . . . 1813--1828
             Manfred Droste and   
                Ingmar Meinecke   Weighted Automata and Regular
                                  Expressions Over Valuation Monoids . . . 1829--1844
  Zoltán Ésik and   
                Andreas Maletti   The Category of Simulations for Weighted
                                  Tree Automata  . . . . . . . . . . . . . 1845--1859
         Manfred Kufleitner and   
               Alexander Lauser   Partially Ordered Two-Way Büchi Automata  1861--1876
            Andreas Maletti and   
               Daniel Quernheim   Optimal Hyper-Minimization . . . . . . . 1877--1891
      Jan \vZ\vdárek and   
             Bo\vrivoj Melichar   Tree-Based $2$D Indexing . . . . . . . . 1893--1907
                    Fang Yu and   
              Tevfik Bultan and   
                Oscar H. Ibarra   Relational String Verification Using
                                  Multi-Track Automata . . . . . . . . . . 1909--1924
                   J. C. Birget   On the Circuit-Size of Inverses  . . . . 1925--1938
             Chavdar Dangalchev   Residual Closeness and Generalized
                                  Closeness  . . . . . . . . . . . . . . . 1939--1948
               Artur Czumaj and   
            Jurek Czyzowicz and   
         Leszek G\kasieniec and   
             Jesper Jansson and   
             Andrzej Lingas and   
                 Pawel Zylinski   Approximation Algorithms for Buy-At-Bulk
                                  Geometric Network Design . . . . . . . . 1949--1969
       Csilla Bujtás and   
    György Dósa and   
        Csanád Imreh and   
     Judit Nagy-György and   
                     Zsolt Tuza   The Graph-Bin Packing Problem  . . . . . 1971--1993
                      Anonymous   Author Index Volume 22 (2011)  . . . . . 1995--2004


International Journal of Foundations of Computer Science (IJFCS)
Volume 23, Number 1, January, 2012

              Ian Mcquillan and   
            Giovanni Pighizzini   Preface  . . . . . . . . . . . . . . . . 1--3
              Martin Kappes and   
            Andreas Malcher and   
                Detlef Wotschke   In Memoriam: Chandra Kintala . . . . . . 5--19
          Janusz Brzozowski and   
                   Baiyu Li and   
                        Yuli Ye   On the Complexity of the Evaluation of
                                  Transient Extensions of Boolean
                                  Functions  . . . . . . . . . . . . . . . 21--35
         Cristian S. Calude and   
                Kai Salomaa and   
                Tania K. Roblot   State-Size Hierarchy for Finite-State
                                  Complexity . . . . . . . . . . . . . . . 37--50
                     Bo Cui and   
                   Yuan Gao and   
                  Lila Kari and   
                       Sheng Yu   State Complexity of Two Combined
                                  Operations: Catenation-Star and
                                  Catenation-Reversal  . . . . . . . . . . 51--66
         Krystian Dudzinski and   
         Stavros Konstantinidis   Formal Descriptions of Code Properties:
                                  Decidability, Complexity, Implementation 67--85
      Zoltán Ésik   Ordinal Automata and Cantor Normal Form  87--98
              Ronny Harbich and   
                  Bianca Truthe   A Comparison of the Descriptional
                                  Complexity of Classes of Limited
                                  Lindenmayer Systems: Part I  . . . . . . 99--114
              Markus Holzer and   
           Sebastian Jakobi and   
                  Martin Kutrib   The Magic Number Problem for Subregular
                                  Language Families  . . . . . . . . . . . 115--131
   Przemyslaw Prusinkiewicz and   
        Mitra Shirmohammadi and   
              Faramarz Samavati   $L$-Systems in Geometric Modeling  . . . 133--146
     Adilson Luiz Bonifacio and   
       Arnaldo Vieira Moura and   
                 Adenilso Simao   Model Partitions and Compact Test Case
                                  Suites . . . . . . . . . . . . . . . . . 147--172
               Junping Zhou and   
                Minghao Yin and   
                Xiangtao Li and   
                    Jinyan Wang   Phase Transitions of Expspace-Complete
                                  Problems: a Further Step . . . . . . . . 173--184
             Egor Dolzhenko and   
               Nata\vsa Jonoska   Two-Dimensional Languages and Cellular
                                  Automata . . . . . . . . . . . . . . . . 185--206
         Kalpana Mahalingam and   
              K. G. Subramanian   Product of Parikh Matrices and
                                  Commutativity  . . . . . . . . . . . . . 207--223
César Domínguez and   
                Dominique Duval   A Parameterization Process: from a
                                  Functorial Point of View . . . . . . . . 225--242

International Journal of Foundations of Computer Science (IJFCS)
Volume 23, Number 2, February, 2012

                    F. Chin and   
                  O. Ibarra and   
                   S. Sahni and   
                     A. Salomaa   Sheng Yu . . . . . . . . . . . . . . . . 243--246
                      Jan Holub   Preface  . . . . . . . . . . . . . . . . 247--248
       Costas S. Iliopoulos and   
               Mirka Miller and   
                Solon P. Pissis   Parallel Algorithms for Mapping Short
                                  Degenerate and Weighted DNA Sequences to
                                  a Reference Genome . . . . . . . . . . . 249--259
           Shunsuke Inenaga and   
                   Hideo Bannai   Finding Characteristic Substrings from
                                  Compressed Texts . . . . . . . . . . . . 261--280
          Maxime Crochemore and   
            Laura Giambruno and   
                 Alessio Langiu   On-Line Construction of a Small
                                  Automaton for a Finite Set of Words  . . 281--301
          Marcin Piatkowski and   
                Wojciech Rytter   Asymptotic Behaviour of the Maximal
                                  Number of Squares in Standard Sturmian
                                  Words  . . . . . . . . . . . . . . . . . 303--321
          Matteo Campanelli and   
           Domenico Cantone and   
                Simone Faro and   
             Emanuele Giaquinta   Pattern Matching with Swaps in Practice  323--342
           Domenico Cantone and   
                Simone Faro and   
             Emanuele Giaquinta   Adapting Boyer--Moore-Like Algorithms
                                  for Searching Huffman Encoded Texts  . . 343--356
        Péter Burcsi and   
        Ferdinando Cicalese and   
              Gabriele Fici and   
        Zsuzsanna Lipták   Algorithms for Jumbled Pattern Matching
                                  in Strings . . . . . . . . . . . . . . . 357--374
         Sebastian Smyczy\'nski   Constant-Memory Iterative Generation of
                                  Special Strings Representing Binary
                                  Trees  . . . . . . . . . . . . . . . . . 375--387
           Frantisek Franek and   
                      Mei Jiang   Crochemore's Repetitions Algorithm
                                  Revisited: Computing Runs  . . . . . . . 389--401
               Enrique Alba and   
      Franciszek Seredynski and   
           El-Ghazali Talbi and   
               Albert Y. Zomaya   Preface  . . . . . . . . . . . . . . . . 403--405
         Azzedine Boukerche and   
    Rodolfo Bezerra Batista and   
Alba Cristina Magalhaes Alves De Melo and   
       Felipe Brandt Scarel and   
Lavir Antonio Bahia Carvalho De Souza   Exact Parallel Alignment of Megabase
                                  Genomic Sequences with Tunable Work
                                  Distribution . . . . . . . . . . . . . . 407--429
          Allani Abderrahim and   
           El-Ghazali Talbi and   
                Mellouli Khaled   Hybridization of Genetic and Quantum
                                  Algorithm for Gene Selection and
                                  Classification of Microarray Data  . . . 431--444
            Young Choon Lee and   
               Javid Taheri and   
               Albert Y. Zomaya   A Parallel Metaheuristic Framework Based
                                  on Harmony Search for Scheduling in
                                  Distributed Computing Systems  . . . . . 445--464
            Piotr Switalski and   
          Franciszek Seredynski   An Effective Multiprocessor Scheduling
                                  with Use of Geo Metaheuristic  . . . . . 465--481
             Lakhdar Loukil and   
               Malika Mehdi and   
            Nouredine Melab and   
           El-Ghazali Talbi and   
                  Pascal Bouvry   Parallel Hybrid Genetic Algorithms for
                                  Solving Q3Ap on Computational Grid . . . 483--500
          Marcin Seredynski and   
                  Pascal Bouvry   Direct Reciprocity-Based Cooperation in
                                  Mobile Ad Hoc Networks . . . . . . . . . 501--521
             Patrick Ediger and   
                  Rolf Hoffmann   Efficiency Analysis of the
                                  Time-Shuffling Method for the Evolution
                                  of Agent Behavior  . . . . . . . . . . . 523--542
Julio Cesar Hernandez-Castro and   
Juan Manuel Estevez-Tapiador and   
          Pedro Peris-Lopez and   
              John A. Clark and   
               El-Ghazali Talbi   Metaheuristic Traceability Attack
                                  Against SLMAP, an RFID Lightweight
                                  Authentication Protocol  . . . . . . . . 543--553

International Journal of Foundations of Computer Science (IJFCS)
Volume 23, Number 3, April, 2012

           Angelo Montanari and   
          Margherita Napoli and   
                  Mimmo Parente   Preface  . . . . . . . . . . . . . . . . 555
            Davide Bresolin and   
                Pietro Sala and   
                Guido Sciavicco   On Begins, Meets and Before  . . . . . . 559
               Lubo\vs Brim and   
                Jakub Chaloupka   Using Strategy Improvement to Stay Alive 585
      Krishnendu Chatterjee and   
                 Rupak Majumdar   Discounting and Averaging in Games
                                  Across Time Scales . . . . . . . . . . . 609
        Giovanna D'agostino and   
                  Giacomo Lenzi   On Modal $ \mu $-Calculus over Finite
                                  Graphs with Small Components or Small
                                  Tree Width . . . . . . . . . . . . . . . 627
              John Fearnley and   
              Martin Zimmermann   Playing Muller Games in a Hurry  . . . . 649
           Oliver Friedmann and   
                   Martin Lange   Two Local Strategy Iteration Schemes for
                                  Parity Game Solving  . . . . . . . . . . 669
               Hugo Gimbert and   
              Wies\law Zielonka   Blackwell Optimal Strategies in Priority
                                  Mean-Payoff Games  . . . . . . . . . . . 687
            Henning Bordihn and   
              Martin Kutrib and   
                Andreas Malcher   On the Computational Capacity of
                                  Parallel Communicating Finite Automata   713
               Yuechuan Wei and   
                    Chao Li and   
                        Dan Cao   Improved Related-Key Rectangle Attack on
                                  the Full HAS-160 Encryption Mode . . . . 733
               Deshuai Dong and   
               Longjiang Qu and   
                Shaojing Fu and   
                        Chao Li   New Constructions of Vectorial Boolean
                                  Functions with Good Cryptographic
                                  Properties . . . . . . . . . . . . . . . 749

International Journal of Foundations of Computer Science (IJFCS)
Volume 23, Number 4, June, 2012

            Jacir L. Bordim and   
           Akihiro Fujiwara and   
                    Koji Nakano   Preface  . . . . . . . . . . . . . . . . 761
              Wayne Goddard and   
              Pradip K. Srimani   Self-Stabilizing Master-Slave Token
                                  Circulation and Efficient
                                  Size-Computation in a Unidirectional
                                  Ring of Arbitrary Size . . . . . . . . . 763
                       Keqin Li   Performance Analysis and Evaluation of
                                  Random Walk Algorithms on Wireless
                                  Networks . . . . . . . . . . . . . . . . 779
                  Alain Bui and   
         Abdurusul Kudireti and   
                   Devan Sohier   An Adaptive Random Walk Based
                                  Distributed Clustering Algorithm . . . . 803
                Guoqiang Li and   
               Xiaojuan Cai and   
                     Shoji Yuen   Modeling and Analysis of Real-Time
                                  Systems with Mutex Components  . . . . . 831
     Daniel Fajardo-Delgado and   
José Alberto Fernández-Zepeda and   
               Anu G. Bourgeois   Randomized Self-Stabilizing Leader
                                  Election in Preference-Based Anonymous
                                  Trees  . . . . . . . . . . . . . . . . . 853
               Adam Gudy\'s and   
            Sebastian Deorowicz   A Parallel Algorithm for the Constrained
                                  Multiple Sequence Alignment Problem
                                  Designed for GPUs  . . . . . . . . . . . 877
                   Liang Hu and   
                 Meng Zhang and   
                   Yi Zhang and   
                     Jijun Tang   Label-Guided Graph Exploration with
                                  Adjustable Ratio of Labels . . . . . . . 903
               Chi-Jung Kuo and   
            Chiun-Chieh Hsu and   
                Hon-Ren Lin and   
                    Da-Ren Chen   Minimum Feedback Arc Sets in Rotator and
                                  Incomplete Rotator Graphs  . . . . . . . 931
                Desh Ranjan and   
                Mohammad Zubair   Vertex Isoperimetric Parameter of a
                                  Computation Graph  . . . . . . . . . . . 941

International Journal of Foundations of Computer Science (IJFCS)
Volume 23, Number 5, August, 2012

             Giancarlo Maur and   
               Alberto Leporati   Preface  . . . . . . . . . . . . . . . . 965
               Sabine Broda and   
  António Machiavelo and   
              Nelma Moreira and   
            Rogério Reis   On the Average Size of Glushkov and
                                  Partial Derivative Automata  . . . . . . 969
           Namit Chaturvedi and   
       Jörg Olschewski and   
                Wolfgang Thomas   Languages Versus $ \omega $-Languages in
                                  Regular Infinite Games . . . . . . . . . 985
             Volker Diekert and   
               Alexei Myasnikov   Group Extensions Over Infinite Words . . 1001
         Michael Domaratzki and   
                Narad Rampersad   Abelian Primitive Words  . . . . . . . . 1021
     Émilie Charlier and   
            Narad Rampersad and   
                Jeffrey Shallit   Enumeration and Decidable Properties of
                                  Automatic Sequences  . . . . . . . . . . 1035
     Edita Pelantová and   
\vStépán Starosta   Almost Rich Words As Morphic Images of
                                  Rich Words . . . . . . . . . . . . . . . 1067
                   Yuan Gao and   
                       Sheng Yu   State Complexity and Approximation . . . 1085
              A. C. Cem Say and   
             Abuzer Yakaryilmaz   Quantum Counter Automata . . . . . . . . 1099
             Shenggen Zheng and   
                 Daowen Qiu and   
                      Lvzhou Li   Some Languages Recognized by Two-Way
                                  Finite Automata with Quantum and
                                  Classical States . . . . . . . . . . . . 1117
              Pablo Arrighi and   
                   Gilles Dowek   The Physical Church--Turing Thesis and
                                  the Principles of Quantum Theory . . . . 1131
               Guaning Chen and   
                Chih-Wei Yi and   
                 Min-Te Sun and   
               Fang-Chu Liu and   
                    Wei-Chi Lan   Minimum Local Disk Cover Sets for
                                  Broadcasting in Heterogeneous Multihop
                                  Wireless Networks  . . . . . . . . . . . 1147
        Andrzej Ehrenfeucht and   
               Michael Main and   
         Grzegorz Rozenberg and   
         Allison Thompson Brown   Stability and Chaos in Reaction Systems  1173

International Journal of Foundations of Computer Science (IJFCS)
Volume 23, Number 6, September, 2012

Pál Dömösi and   
      Zoltán Ésik   Preface  . . . . . . . . . . . . . . . . 1185
              F. Blanchet-Sadri   Algorithmic Combinatorics on Partial
                                  Words  . . . . . . . . . . . . . . . . . 1189
            Andreas Maletti and   
               Daniel Quernheim   Unweighted and Weighted
                                  Hyper-Minimization . . . . . . . . . . . 1207
           Jean-Éric Pin   Equational Descriptions of Languages . . 1227
            Gilles Benattar and   
Béatrice Bérard and   
                Didier Lime and   
               John Mullins and   
            Olivier H. Roux and   
               Mathieu Sassolas   Channel Synthesis for Finite Transducers 1241
          Janusz Brzozowski and   
                         Bo Liu   Quotient Complexity of Star-Free
                                  Languages  . . . . . . . . . . . . . . . 1261
Szilárd Zsolt Fazekas and   
              Peter Leupold and   
        Kayoko Shikishima-Tsuji   On Non-Primitive Palindromic
                                  Context-Free Languages . . . . . . . . . 1277
            Oscar H. Ibarra and   
                Shinnosuke Seki   Characterizations of Bounded Semilinear
                                  Languages by One-Way and Two-Way
                                  Deterministic Machines . . . . . . . . . 1291
                  Lila Kari and   
                         Zhi Xu   De Bruijn Sequences Revisited  . . . . . 1307
         Manfred Kufleitner and   
               Alexander Lauser   Around Dot-Depth One . . . . . . . . . . 1323
                       Keqin Li   Probing High-Capacity Peers to Reduce
                                  Download Times in P2P File Sharing
                                  Systems with Stochastic Service
                                  Capacities . . . . . . . . . . . . . . . 1341
          Michalis Christou and   
          Maxime Crochemore and   
           Costas S. Iliopoulos   Identifying All Abelian Periods of a
                                  String in Quadratic Time and Relevant
                                  Problems . . . . . . . . . . . . . . . . 1371
      Jana Hadravová and   
        \vSt\uepán Holub   Large Simple Binary Equality Words . . . 1385
                   Orly Yahalom   Testing for Forbidden Posets in Ordered
                                  Rooted Forests . . . . . . . . . . . . . 1405

International Journal of Foundations of Computer Science (IJFCS)
Volume 23, Number 7, November, 2012

Jérôme Durand-Lose and   
        Maurice Margenstern and   
                   Klaus Sutner   Preface  . . . . . . . . . . . . . . . . 1419
             Artiom Alhazov and   
             Yurii Rogozhin and   
                  Sergey Verlan   On Small Universal Splicing Systems  . . 1423
                David Auger and   
                Olivier Teytaud   The Frontier of Decidability in
                                  Partially Observable Recursive Games . . 1439
          Amir M. Ben-Amram and   
               Lars Kristiansen   On the Edge of Decidability in
                                  Complexity Analysis of Loop Programs . . 1451
                    Mark Burgin   Decidability and Universality in the
                                  Axiomatic Theory of Computability and
                                  Algorithms . . . . . . . . . . . . . . . 1465
                 Olivier Finkel   Three Applications to Rational Relations
                                  of the High Undecidability of the
                                  Infinite Post Correspondence Problem in
                                  a regular $ \omega $-Language  . . . . . 1481
                     Klaus Meer   Some Initial Thoughts on Bounded Query
                                  Computations Over the Reals  . . . . . . 1499
                 Yunyun Niu and   
          K. G. Subramanian and   
             Ibrahim Venkat and   
                 Rosni Abdullah   A Tissue $P$ System Based Solution to
                                  Quadratic Assignment Problem . . . . . . 1511
            Hammadi Bennoui and   
             Allaoua Chaoui and   
                 Kamel Barkaoui   On Structural Analysis of Interacting
                                  Behavioral Petri Nets for Distributed
                                  Causal Model-Based Diagnosis . . . . . . 1523
            Chung-Shou Liao and   
                   Louxin Zhang   Approximating the Spanning $k$-Tree
                                  Forest Problem . . . . . . . . . . . . . 1543
           Alexander Meduna and   
                     Petr Zemek   Jumping Finite Automata  . . . . . . . . 1555

International Journal of Foundations of Computer Science (IJFCS)
Volume 23, Number 8, December, 2012

Zuzana Masáková and   
        \vSt\vepán Holub   Preface  . . . . . . . . . . . . . . . . 1579
         Irina A. Gorbunova and   
                 Arseny M. Shur   On Pansiot Words Avoiding 3-Repetitions  1583
           Elena A. Petrova and   
                 Arseny M. Shur   Constructing Premaximal Binary Cube-Free
                                  Words of Any Level . . . . . . . . . . . 1595
             Luke Schaeffer and   
                Jeffrey Shallit   The Critical Exponent Is Computable for
                                  Automatic Sequences  . . . . . . . . . . 1611
                  Daniel Dombek   Substitutions over Infinite Alphabet
                                  Generating $ ( - \beta) $-integers . . . 1627
           Bastian Bischoff and   
               James Currie and   
                   Dirk Nowotka   Unary Patterns with Involution . . . . . 1641
                  Steven Widmer   Permutation Complexity and the Letter
                                  Doubling Map . . . . . . . . . . . . . . 1653
                  Fabio Burderi   Full Monoids and Maximal Codes . . . . . 1677
      Michaël Cadilhac and   
               Alain Finkel and   
                Pierre Mckenzie   Bounded Parikh Automata  . . . . . . . . 1691
    Stefano Crespi Reghizzi and   
           Pierluigi San Pietro   From Regular to Strictly Locally
                                  Testable Languages . . . . . . . . . . . 1711
               Shuming Zhou and   
              Lanxiang Chen and   
                    Jun-Ming Xu   Conditional Fault Diagnosability of
                                  Dual-Cubes . . . . . . . . . . . . . . . 1729
                   Juha Honkala   Equality Sets of Morphic Word Sequences  1749
                      Anonymous   Author Index Volume 23 (2012)  . . . . . 1767


International Journal of Foundations of Computer Science (IJFCS)
Volume 24, Number 1, January, 2013

               Alex Potanin and   
                    Taso Viglas   Preface  . . . . . . . . . . . . . . . . 1
             Peter Floderus and   
             Andrzej Lingas and   
                    Mia Persson   Towards More Efficient Infection and
                                  Fire Fighting  . . . . . . . . . . . . . 3
               Akira Suzuki and   
               Kei Uchizawa and   
                      Xiao Zhou   Energy-Efficient Threshold Circuits
                                  Computing Mod Functions  . . . . . . . . 15
             John Augustine and   
                     Qi Han and   
               Philip Loden and   
               Sachin Lodha and   
                    Sasanka Roy   Tight Analysis of Shortest Path
                                  Convergecast in Wireless Sensor Networks 31
             Guillaume Blin and   
                Romeo Rizzi and   
             Florian Sikora and   
              Stephane Vialette   Minimum Mosaic Inference of a Set of
                                  Recombinants . . . . . . . . . . . . . . 51
        N. S. Narayanaswamy and   
                   N. Sadagopan   A Unified Framework for
                                  Bi(tri)connectivity and Chordal
                                  Augmentation . . . . . . . . . . . . . . 67
          Marcin Bienkowski and   
                Pawe\l Zalewski   $ (1, 2) $-Hamiltonian Completion on a
                                  Matching . . . . . . . . . . . . . . . . 95
           Martin R. Ehmsen and   
                  Kim S. Larsen   A Technique for Exact Computation of
                                  Precoloring Extension on Interval Graphs 109
                  Fabien Durand   Decidability of Uniform Recurrence of
                                  Morphic Sequences  . . . . . . . . . . . 123
                   Arto Salomaa   Functional Constructions Between
                                  Reaction Systems and Propositional Logic 147

International Journal of Foundations of Computer Science (IJFCS)
Volume 24, Number 2, February, 2013

           Giorgio Delzanno and   
                   Igor Potapov   Preface  . . . . . . . . . . . . . . . . 161
      Krishnendu Chatterjee and   
             Luca De Alfaro and   
                 Rupak Majumdar   The Complexity of Coverage . . . . . . . 165
        Parosh Aziz Abdulla and   
         Jonathan Cederberg and   
          Tomá\vs Vojnar   Monotonic Abstraction for Programs with
                                  Multiply-Linked Structures . . . . . . . 187
         Alessandro Carioni and   
            Silvio Ghilardi and   
                  Silvio Ranise   Automated Termination in Model-Checking
                                  Modulo Theories  . . . . . . . . . . . . 211
           Laurent Fribourg and   
              Ulrich Kühne   Parametric Verification and Test
                                  Coverage for Hybrid Automata Using the
                                  Inverse Method . . . . . . . . . . . . . 233
              Vladimir V. Gusev   Lower Bounds for the Length of Reset
                                  Words in Eulerian Automata . . . . . . . 251
              Malcolm Mumme and   
              Gianfranco Ciardo   An Efficient Fully Symbolic Bisimulation
                                  Algorithm for Non-Deterministic Systems  263
         Nataliya Skrypnyuk and   
               Flemming Nielson   Reachability for Finite-State Process
                                  Algebras Using Horn Clauses  . . . . . . 283

International Journal of Foundations of Computer Science (IJFCS)
Volume 24, Number 3, April, 2013

         Goksen Bacak-Turan and   
                Alpay Kirlangic   Neighbor Integrity of Transformation
                                  Graphs . . . . . . . . . . . . . . . . . 303
        Tomá\vs Masopust   A Note on Limited Pushdown Alphabets in
                                  Stateless Deterministic Pushdown
                                  Automata . . . . . . . . . . . . . . . . 319
        Javad Akbari Torkestani   A Learning Automata-Based Algorithm to
                                  the Stochastic Min-Degree Constrained
                                  Minimum Spanning Tree Problem  . . . . . 329
                   Houguang Yue   From Computing to Interaction: on the
                                  Expressiveness of Asynchronous
                                  Pi-Calculus  . . . . . . . . . . . . . . 349
               S. P. Tiwari and   
             Shambhu Sharan and   
                Anupam K. Singh   On Coverings of Products of Rough
                                  Transformation Semigroups  . . . . . . . 375
          K. G. Subramanian and   
         Kalpana Mahalingam and   
             Rosni Abdullah and   
                Atulya K. Nagar   Two-Dimensional Digitized Picture Arrays
                                  and Parikh Matrices  . . . . . . . . . . 393
                   Ziran Tu and   
               Yupeng Jiang and   
                 Xiangyong Zeng   Constructing Odd Variable Boolean
                                  Functions with Optimal Algebraic
                                  Immunity . . . . . . . . . . . . . . . . 409

International Journal of Foundations of Computer Science (IJFCS)
Volume 24, Number 4, June, 2013

           Alessio Lomuscio and   
                 Ben Strulo and   
               Nigel Walker and   
                        Peng Wu   Assume-Guarantee Reasoning with Local
                                  Specifications . . . . . . . . . . . . . 419
Szilárd Zsolt Fazekas and   
                Robert Merca\cs   A Note on the Decidability of Subword
                                  Inequalities . . . . . . . . . . . . . . 445
                 Friedrich Otto   On Centralized Parallel Communicating
                                  Grammar Systems with Context-Sensitive
                                  Components . . . . . . . . . . . . . . . 453
             Sudipta Pathak and   
    Sanguthevar Rajasekaran and   
                 Marius Nicolae   Ems1: an Elegant Algorithm for Edit
                                  Distance Based Motif Search  . . . . . . 473
                Mark Burgin and   
         Cristian S. Calude and   
                   Elena Calude   Inductive Complexity Measures for
                                  Mathematical Problems  . . . . . . . . . 487
Katalin Anna Lázár   A Bridge Between Self--Organizing
                                  Networks and Grammar Systems Theory  . . 501
        Antonios Kalampakas and   
    Olympia Louscou-Bozapalidou   Minimization of Planar Directed Acyclic
                                  Graph Algebras . . . . . . . . . . . . . 519
                    Han Cai and   
             Xiangyong Zeng and   
                Xiaohu Tang and   
                         Lei Hu   New Optimal Frequency Hopping Sequence
                                  Sets from Balanced Nested Difference
                                  Packings of Partition-Type . . . . . . . 533

International Journal of Foundations of Computer Science (IJFCS)
Volume 24, Number 5, August, 2013

            Marian Gheorghe and   
            Gheorghe P\uaun and   
Mario J. Pérez-Jiménez and   
             Grzegorz Rozenberg   Research Frontiers of Membrane
                                  Computing: Open Problems and Research
                                  Topics . . . . . . . . . . . . . . . . . 547
            Ashok Kumar Das and   
         Santanu Chatterjee and   
              Jamuna Kanta Sing   A Novel Efficient Access Control Scheme
                                  for Large-Scale Distributed Wireless
                                  Sensor Networks  . . . . . . . . . . . . 625
                Andreas Darmann   Popular Spanning Trees . . . . . . . . . 655
                     Yo-Sub Han   An Improved Prefix-Free
                                  Regular-Expression Matching  . . . . . . 679

International Journal of Foundations of Computer Science (IJFCS)
Volume 24, Number 6, September, 2013

              Nelma Moreira and   
            Rogério Reis   Preface  . . . . . . . . . . . . . . . . 689
              Janusz Brzozowski   In Search of Most Complex Regular
                                  Languages  . . . . . . . . . . . . . . . 691
        José N. Oliveira   Weighted Automata As Coalgebras in
                                  Categories of Matrices . . . . . . . . . 709
           Mikhail V. Berlinkov   Synchronizing Quasi-Eulerian and
                                  Quasi-One-Cluster Automata . . . . . . . 729
    Stefano Crespi Reghizzi and   
           Pierluigi San Pietro   Strict Local Testability with Consensus
                                  Equals Regularity, and Other Properties  747
             F. M. Fominykh and   
            P. V. Martyugin and   
                   M. V. Volkov   P(l)aying for Synchronization  . . . . . 765
               Daniel Go\vc and   
              Dane Henshall and   
                Jeffrey Shallit   Automatic Theorem-Proving in
                                  Combinatorics on Words . . . . . . . . . 781
            Oscar H. Ibarra and   
               Nicholas Q. Tran   How to Synchronize the Heads of a
                                  Multitape Automaton  . . . . . . . . . . 799
                Artur Je\.z and   
                Andreas Maletti   Hyper-Minimization for Deterministic
                                  Tree Automata  . . . . . . . . . . . . . 815
              Martin Kutrib and   
                 Friedrich Otto   On the Descriptional Complexity of the
                                  Window Size for Deleting Restarting
                                  Automata . . . . . . . . . . . . . . . . 831
                  Mehryar Mohri   On the Disambiguation of Finite Automata
                                  and Functional Transducers . . . . . . . 847
           Daniel Pr\ru\vsa and   
        Franti\vsek Mráz   Restarting Tiling Automata . . . . . . . 863
                   En Zhang and   
                   Yongquan Cai   Rational Multi-Secret Sharing Scheme in
                                  Standard Point-To-Point Communication
                                  Networks . . . . . . . . . . . . . . . . 879
              Guangyan Zhou and   
                  Zongsheng Gao   A new upper bound for random $ (2 + p)
                                  $-SAT by flipping two variables  . . . . 899
             Prabhu M. Santhosh   Self Stabilization in Distributed Knot
                                  Detection  . . . . . . . . . . . . . . . 913
                    Jing Li and   
                     Di Liu and   
                       Jun Yuan   The Super Spanning Connectivity and
                                  Super Spanning Laceability of Tori with
                                  Faulty Elements  . . . . . . . . . . . . 921

International Journal of Foundations of Computer Science (IJFCS)
Volume 24, Number 7, November, 2013

               Hsu-Chun Yen and   
                Oscar H. Ibarra   Preface  . . . . . . . . . . . . . . . . 941
               Arto Salomaa and   
             Kai T. Salomaa and   
              Andrew L. Szilard   Goodby to the Kindhearted Dragon Prof.
                                  Sheng Yu, 1950--2012 . . . . . . . . . . 945
          Juraj Hromkovi\vc and   
Rastislav Královi\vc and   
  Richard Královi\vc and   
             Richard \vStefanec   Determinism vs. Nondeterminism for
                                  Two-Way Automata: Representing the
                                  Meaning of States by Logical Formulæ  . . 955
                Kazuo Iwama and   
            Harumichi Nishimura   Recovering Strings in Oracles: Quantum
                                  and Classic  . . . . . . . . . . . . . . 979
Erzsébet Csuhaj-Varjú   P and DP automata: unconventional versus
                                  classical automata . . . . . . . . . . . 995
          Janusz Brzozowski and   
                    Hellis Tamm   Complexity of Atoms of Regular Languages 1009
  Zoltán Ésik and   
                  Satoshi Okawa   On Context-Free Languages of Scattered
                                  Words  . . . . . . . . . . . . . . . . . 1029
             Tommi Lehtinen and   
              Alexander Okhotin   Homomorphisms Preserving Deterministic
                                  Context-Free Languages . . . . . . . . . 1049
                 Yo-Sub Han and   
                 Sang-Ki Ko and   
                    Kai Salomaa   The Edit-Distance Between a Regular
                                  Language and a Context-Free Language . . 1067
              Markus Holzer and   
               Sebastian Jakobi   From Equivalence to Almost-Equivalence,
                                  and Beyond: Minimizing Automata with
                                  Errors . . . . . . . . . . . . . . . . . 1083
      Michaël Cadilhac and   
               Alain Finkel and   
                Pierre Mckenzie   Unambiguous Constrained Automata . . . . 1099
               Markus L. Schmid   Inside the Class of Regex Languages  . . 1117
      Juhani Karhumäki and   
          Svetlana Puzynina and   
                 Aleksi Saarela   Fine and Wilf's theorem for $k$-Abelian
                                  periods  . . . . . . . . . . . . . . . . 1135
Alexandre Blondin Massé and   
            Sarah Desmeules and   
   Sébastien Gaboury and   
           Sylvain Hallé   Multipseudoperiodic Words  . . . . . . . 1153
             Viliam Geffert and   
          Dana Pardubská   Unary coded NP-complete languages in $
                                  {\rm ASPACE}(\log \log n) $  . . . . . . 1167

International Journal of Foundations of Computer Science (IJFCS)
Volume 24, Number 8, December, 2013

                 Simon Ware and   
                     Robi Malik   Compositional Verification of the
                                  Generalized Nonblocking Property Using
                                  Abstraction and Canonical Automata . . . 1183
              Zhengbang Zha and   
                         Lei Hu   Constructing New APN Functions from
                                  Known PN Functions . . . . . . . . . . . 1209
             Stephen Fenner and   
                     Yong Zhang   On the Complexity of the Hidden Subgroup
                                  Problem  . . . . . . . . . . . . . . . . 1221
                Yunchao Wei and   
                   Fuguang Chen   Generalized connectivity of $ (n, k)
                                  $-star graphs  . . . . . . . . . . . . . 1235
         Abuzer Yakaryilmaz and   
                  A. C. Cem Say   Tight Bounds for the Space Complexity of
                                  Nonregular Language Recognition by
                                  Real-Time Machines . . . . . . . . . . . 1243
             Hermann Gruber and   
                  Markus Holzer   Provably Shorter Regular Expressions
                                  from Finite Automata . . . . . . . . . . 1255
        Sebastian Deorowicz and   
                Agnieszka Danek   Bit-Parallel Algorithms for the Merged
                                  Longest Common Subsequence Problem . . . 1281
                Rolf Harren and   
               Klaus Jansen and   
           Lars Prädel and   
          Ulrich M. Schwarz and   
                   Rob Van Stee   Two for One: Tight Approximation of $2$D
                                  Bin Packing  . . . . . . . . . . . . . . 1299
         Aysun Aytaç and   
                    Hanife Aksu   Some Results for the Rupture Degree  . . 1329
                     Kenya Ueno   Breaking the Rectangle Bound Barrier
                                  Against Formula Size Lower Bounds  . . . 1339
                      Anonymous   Author Index Volume 24 (2013)  . . . . . 1355


International Journal of Foundations of Computer Science (IJFCS)
Volume 25, Number 1, January, 2014

                    Jia Fan and   
              Yuliang Zheng and   
                    Xiaohu Tang   A New Construction of Identity-Based
                                  Signcryption Without Random Oracles  . . 1
             George Lagogiannis   Parent Queries Over Dynamic Balanced
                                  Parenthesis Strings  . . . . . . . . . . 25
              Xiang-Lan Cao and   
                    Elkin Vumar   Super Edge Connectivity of Kronecker
                                  Products of Graphs . . . . . . . . . . . 59
                    Haejae Jung   A Simple Array Version of $M$-Heap . . . 67
             Alexander Golovnev   Approximating Asymmetric TSP in
                                  Exponential Time . . . . . . . . . . . . 89
 Galina Jirásková   The Ranges of State Complexities for
                                  Complement, Star, and Reversal of
                                  Regular Languages  . . . . . . . . . . . 101

International Journal of Foundations of Computer Science (IJFCS)
Volume 25, Number 2, February, 2014

           Jheng-Cheng Chen and   
               Chia-Jui Lai and   
              Chang-Hsiung Tsai   A Three-Round Adaptive Diagnostic
                                  Algorithm in a Distributed System
                                  Modeled by Dual-Cubes  . . . . . . . . . 125
           Nata\vsa Jonoska and   
                 Daria Karpenko   Active Tile Self-Assembly, Part 1:
                                  Universality at Temperature 1  . . . . . 141
           Nata\vsa Jonoska and   
                 Daria Karpenko   Active Tile Self-Assembly, Part 2:
                                  Self-Similar Structures and Structural
                                  Recursion  . . . . . . . . . . . . . . . 165
                  Eric Wang and   
                  Cewei Cui and   
                   Zhe Dang and   
          Thomas R. Fischer and   
                    Linmin Yang   Zero-Knowledge Blackbox Testing: Where
                                  Are the Faults?  . . . . . . . . . . . . 195
                  Pai-Chou Wang   Dynamic Reducts Generation Using
                                  Cascading Hashes . . . . . . . . . . . . 219

International Journal of Foundations of Computer Science (IJFCS)
Volume 25, Number 3, April, 2014

               Andrzej Pelc and   
                     Anas Tiane   Efficient Grid Exploration with a
                                  Stationary Token . . . . . . . . . . . . 247
                 Jing Zhang and   
               Xiaofan Yang and   
                     Cui Yu and   
                          Li He   The Congestion of Generalized Cube
                                  Communication Pattern in Linear Array
                                  Network  . . . . . . . . . . . . . . . . 263
        Andrzej Ehrenfeucht and   
             Grzegorz Rozenberg   Zoom Structures and Reaction Systems
                                  Yield Exploration Systems  . . . . . . . 275
         Yoshiyuki Yamamoto and   
             Kouichi Hirata and   
               Tetsuji Kuboyama   Tractable and Intractable Variations of
                                  Unordered Tree Edit Distance . . . . . . 307
                   Nhat Lam and   
               Min Kyung An and   
              Dung T. Huynh and   
                    Trac Nguyen   Broadcast Scheduling Problem in SINR
                                  Model  . . . . . . . . . . . . . . . . . 331
                    Yu Zhou and   
                   Lin Wang and   
              Weiqiong Wang and   
               Xinfeng Dong and   
                      Xiaoni Du   One Sufficient and Necessary Condition
                                  on Balanced Boolean Functions with $
                                  \sigma_f = 2^{2n} + 2^{n + 3} (n \geq 3)
                                  $  . . . . . . . . . . . . . . . . . . . 343
                Amr Elmasry and   
                   Yung H. Tsin   On Finding Sparse Three-Edge-Connected
                                  and Three-Vertex-Connected Spanning
                                  Subgraphs  . . . . . . . . . . . . . . . 355

International Journal of Foundations of Computer Science (IJFCS)
Volume 25, Number 5, August, 2014

                  Ning Ding and   
                    Yan Lan and   
                   Xin Chen and   
    György Dósa and   
                     He Guo and   
                        Xin Han   Online Minimum Makespan Scheduling with
                                  a Buffer . . . . . . . . . . . . . . . . 525
                  Jia Zheng and   
                 Baofeng Wu and   
                  Yufu Chen and   
                    Zhuojun Liu   Constructing $ 2 m$-variable Boolean
                                  functions with optimal algebraic
                                  immunity based on polar decomposition of
                                  $ \mathbb {F}_{2^{2m}}^*$  . . . . . . . 537
                  Yinkui Li and   
               Zongtian Wei and   
                Xiaokui Yue and   
                    Erqiang Liu   Tenacity of Total Graphs . . . . . . . . 553
      Partha Sarathi Mandal and   
                  Anil K. Ghosh   A Statistical Approach Towards Secure
                                  Location Verification in Noisy Wireless
                                  Channels . . . . . . . . . . . . . . . . 563
                Tim Boykett and   
                  Gerhard Wendt   $ {\cal I}_2 $ Radical in Automata Near
                                  Rings  . . . . . . . . . . . . . . . . . 585
           Gennaro Cordasco and   
            Arnold L. Rosenberg   On Scheduling Series--Parallel DAGs to
                                  Maximize Area  . . . . . . . . . . . . . 597
               Taha Ghasemi and   
     Hossein Ghasemalizadeh and   
           Mohammadreza Razzazi   An Algorithmic Framework for Solving
                                  Geometric Covering Problems --- with
                                  Applications . . . . . . . . . . . . . . 623
             Manfred Droste and   
             Bundit Pibaljommee   Weighted Nested Word Automata and Logics
                                  Over Strong Bimonoids  . . . . . . . . . 641

International Journal of Foundations of Computer Science (IJFCS)
Volume 25, Number 6, September, 2014

               Junping Zhou and   
                  Weihua Su and   
                    Jianan Wang   New Worst-Case Upper Bound for Counting
                                  Exact Satisfiability . . . . . . . . . . 667
        Pedro García and   
 Damián López and   
 Manuel Vázquez De Parga   Efficient Deterministic Finite Automata
                                  Split-Minimization Derived from
                                  Brzozowski's Algorithm . . . . . . . . . 679
                Haijun Yang and   
                Minqiang Li and   
                  Qinghua Zheng   Performance Analysis of Grid
                                  Architecture Via Queueing Theory . . . . 697
             Chiao-Wei Chiu and   
               Kuo-Si Huang and   
            Chang-Biau Yang and   
               Chiou-Ting Tseng   An Adaptive Heuristic Algorithm with the
                                  Probabilistic Safety Vector for
                                  Fault-Tolerant Routing on the $ (n,
                                  k)$-Star Graph . . . . . . . . . . . . . 723
                   Lin Chen and   
                   Deshi Ye and   
                 Guochuan Zhang   Online Scheduling of Mixed CPU--GPU Jobs 745
                  Deng Tang and   
              Claude Carlet and   
                    Xiaohu Tang   A Class of $1$-Resilient Boolean
                                  Functions with Optimal Algebraic
                                  Immunity and Good Behavior Against Fast
                                  Algebraic Attacks  . . . . . . . . . . . 763
           Tamar Aizikowitz and   
               Michael Kaminski   Linear Conjunctive Grammars and One-Turn
                                  Synchronized Alternating Pushdown
                                  Automata . . . . . . . . . . . . . . . . 781

International Journal of Foundations of Computer Science (IJFCS)
Volume 25, Number 7, November, 2014

      Helmut Jürgensen and   
            Rogério Reis   Preface  . . . . . . . . . . . . . . . . 803
          Janusz Brzozowski and   
                       Baiyu Li   Syntactic Complexity of $ \cal R $- and
                                  $ \cal J $-Trivial Regular Languages . . 807
               Daniel Go\vc and   
     Alexandros Palioudakis and   
                    Kai Salomaa   Nondeterministic State Complexity of
                                  Proportional Removals  . . . . . . . . . 823
              Markus Holzer and   
               Sebastian Jakobi   Nondeterministic Biautomata and Their
                                  Descriptional Complexity . . . . . . . . 837
                      K. Sutner   Iteration of Invertible Transductions    857
              Martin Kutrib and   
            Andreas Malcher and   
             Matthias Wendlandt   Simulations of Unary One-Way Multi-Head
                                  Finite Automata  . . . . . . . . . . . . 877
        Giovanni Pighizzini and   
                  Andrea Pisoni   Limited Automata and Regular Languages   897
           Cezar Câmpeanu   Descriptional Complexity in Encoded Blum
                                  Static Complexity Spaces . . . . . . . . 917

International Journal of Foundations of Computer Science (IJFCS)
Volume 25, Number 8, December, 2014

   Marie-Pierre Béal and   
                 Olivier Carton   Preface  . . . . . . . . . . . . . . . . 933
                 Arseny M. Shur   Languages with a Finite Antidictionary:
                                  Some Growth Questions  . . . . . . . . . 937
             Manfred Droste and   
                   Heiko Vogler   The Chomsky--Schützenberger Theorem for
                                  Quantitative Context-Free Languages  . . 955
                   Tony Tan and   
                Domagoj Vrgo\vc   Regular Expressions for Querying Data
                                  Graphs . . . . . . . . . . . . . . . . . 971
U\ugur Küçük and   
              A. C. Cem Say and   
             Abuzer Yakaryilmaz   Finite Automata with Advice Tapes  . . . 987
  Zoltán Ésik and   
           Szabolcs Iván   Operational Characterization of
                                  Scattered MCFLs  . . . . . . . . . . . . 1001
           Marcella Anselmo and   
           Dora Giammarresi and   
                  Maria Madonia   Prefix Picture Codes: a Decidable Class
                                  of Two-Dimensional Codes . . . . . . . . 1017
                Joel D. Day and   
          Daniel Reidenbach and   
          Johannes C. Schneider   On the Dual Post Correspondence Problem  1033
         Jürgen Dassow and   
               Florin Manea and   
            Robert Merca\cs and   
               Mike Müller   Inner Palindromic Closure  . . . . . . . 1049
            Alberto Bertoni and   
         Christian Choffrut and   
            Flavio D'alessandro   On the Decidability of the Intersection
                                  Problem for Quantum Automata and
                                  Context-Free Languages . . . . . . . . . 1065
        Mohamed Faouzi Atig and   
           K. Narayan Kumar and   
               Prakash Saivasan   Adjacent Ordered Multi-Pushdown Systems  1083
               Daniel Go\vc and   
            Narad Rampersad and   
                Michel Rigo and   
                  Pavel Salimov   On the Number of Abelian Bordered Words
                                  (with an Example of Automatic
                                  Theorem-Proving) . . . . . . . . . . . . 1097
            Vincent Carnino and   
               Sylvain Lombardy   Factorizations and Universal Automaton
                                  of Omega Languages . . . . . . . . . . . 1111
            Oscar H. Ibarra and   
                 Bala Ravikumar   Some Decision Questions Concerning the
                                  Time Complexity of Language Acceptors    1127
              Martin Kutrib and   
            Andreas Malcher and   
             Matthias Wendlandt   Stateless One-Way Multi-Head Finite
                                  Automata with Pebbles  . . . . . . . . . 1141
              Silvia Bonomo and   
            Sabrina Mantaci and   
            Antonio Restivo and   
            Giovanna Rosone and   
            Marinella Sciortino   Sorting Conjugates and Suffixes of Words
                                  in a Multiset  . . . . . . . . . . . . . 1161
                      Anonymous   Author Index: Volume 25 (2014) . . . . . 1177


International Journal of Foundations of Computer Science (IJFCS)
Volume 26, Number 1, January, 2015

                  Puwen Wei and   
                  Yuliang Zheng   On the Construction of Public Key
                                  Encryption with Sender Recovery  . . . . 1
            Sanpawat Kantabutra   Fast Sequential and Parallel Vertex
                                  Relabelings of $ K_{m, m} $  . . . . . . 33
              Ratnik Gandhi and   
             Samaresh Chatterji   Applications of Algebra for Some Game
                                  Theoretic Problems . . . . . . . . . . . 51
              Jon M. Corson and   
                  Lance L. Ross   Automata with Counters that Recognize
                                  Word Problems of Free Products . . . . . 79
    Uraz Cengiz Türker and   
   Hüsnü Yenigün   Complexities of Some Problems Related to
                                  Synchronizing, Non-Synchronizing and
                                  Monotonic Automata . . . . . . . . . . . 99
                  Wen Chean Teh   On Core Words and the Parikh Matrix
                                  Mapping  . . . . . . . . . . . . . . . . 123
               Qunying Liao and   
                       Juan Zhu   A Note on Optimal Constant Dimension
                                  Codes  . . . . . . . . . . . . . . . . . 143
                   Boris Ryabko   Complexity of Approximating Functions on
                                  Real-Life Computers  . . . . . . . . . . 153
                Xianyong Li and   
               Xiaofan Yang and   
                      Li He and   
                     Cui Yu and   
                     Jing Zhang   Conditional Fault Tolerance of Hypermesh
                                  Optical Interconnection Networks . . . . 159

International Journal of Foundations of Computer Science (IJFCS)
Volume 26, Number 2, February, 2015

                 Koji Nuida and   
                 Takuro Abe and   
                Shizuo Kaji and   
             Toshiaki Maeno and   
                Yasuhide Numata   A Mathematical Problem for Security
                                  Analysis of Hash Functions and
                                  Pseudorandom Generators  . . . . . . . . 169
        Fatemeh Rajabi-Alni and   
                Alireza Bagheri   Constrained Point Set Embedding of a
                                  Balanced Binary Tree . . . . . . . . . . 195
               Hae-Sung Eom and   
                 Yo-Sub Han and   
                    Kai Salomaa   State Complexity of $k$-Union and
                                  $k$-Intersection for Prefix-Free Regular
                                  Languages  . . . . . . . . . . . . . . . 211
                 Yihua Ding and   
              James Z. Wang and   
              Pradip K. Srimani   New Self-Stabilizing Algorithms for
                                  Minimal Weakly Connected Dominating Sets 229
                   Kai Feng and   
               Shiying Wang and   
                  Guozhen Zhang   Link Failure Tolerance in the
                                  Arrangement Graphs . . . . . . . . . . . 241
             Stephen Fenner and   
                     Yong Zhang   Quantum Algorithms for a Set of Group
                                  Theoretic Problems . . . . . . . . . . . 255
              Tina M. Kouri and   
              Daniel Pascua and   
                Dinesh P. Mehta   Random Models and Analyses for Chemical
                                  Graphs . . . . . . . . . . . . . . . . . 269

International Journal of Foundations of Computer Science (IJFCS)
Volume 26, Number 3, April, 2015

   Stéphane Devismes and   
   Sébastien Tixeuil and   
             Masafumi Yamashita   Weak vs. Self vs. Probabilistic
                                  Stabilization  . . . . . . . . . . . . . 293
               Subrata Saha and   
    Sanguthevar Rajasekaran and   
                Rampi Ramprasad   Novel Randomized Feature Selection
                                  Algorithms . . . . . . . . . . . . . . . 321
               Eric Rowland and   
                Jeffrey Shallit   Automatic Sets of Rational Numbers . . . 343
                 Xingqin Qi and   
               Edgar Fuller and   
                   Rong Luo and   
                Guodong Guo and   
                  Cunquan Zhang   Laplacian Energy of Digraphs and a
                                  Minimum Laplacian Energy Algorithm . . . 367
               Jozef Gruska and   
                 Daowen Qiu and   
                 Shenggen Zheng   Potential of Quantum Finite Automata
                                  with Exact Acceptance  . . . . . . . . . 381
        Alexander Grigoriev and   
               Bert Marchal and   
              Natalya Usotskaya   A Note on the Minimum $H$-Subgraph Edge
                                  Deletion . . . . . . . . . . . . . . . . 399

International Journal of Foundations of Computer Science (IJFCS)
Volume 26, Number 4, June, 2015

                 Joan Boyar and   
              Kim S. Larsen and   
              Abyayananda Maiti   The Frequent Items Problem in Online
                                  Streaming Under Various Performance
                                  Measures . . . . . . . . . . . . . . . . 413
                 Jaros\law Rudy   Dynamic Random-Access Stored-Program
                                  Machine for Runtime Code Modification    441
         Cristian S. Calude and   
            Damien Desfontaines   Anytime Algorithms for Non-Ending
                                  Computations . . . . . . . . . . . . . . 465
            Jan Christensen and   
     Anders Nicolai Knudsen and   
                  Kim S. Larsen   Soccer is Harder Than Football . . . . . 477
                 Xishun Zhu and   
             Xiangyong Zeng and   
                      Yuan Chen   Some Binomial and Trinomial
                                  Differentially $4$-Uniform Permutation
                                  Polynomials  . . . . . . . . . . . . . . 487
           Arnaud Casteigts and   
            Paola Flocchini and   
               Bernard Mans and   
                 Nicola Santoro   Shortest, Fastest, and Foremost
                                  Broadcast in Dynamic Networks  . . . . . 499
             Tiziana Calamoneri   Optimal $ L(j, k) $-Edge-Labeling of
                                  Regular Grids  . . . . . . . . . . . . . 523

International Journal of Foundations of Computer Science (IJFCS)
Volume 26, Number 5, August, 2015

               Arto Salomaa and   
               Francis Chin and   
               Oscar Ibarra and   
                   Sartaj Sahni   Alberto Apostolico . . . . . . . . . . . iii
                 Xiwang Cao and   
                         Lei Hu   Two Boolean Functions with Five-Valued
                                  Walsh Spectra and High Nonlinearity  . . 537
               Thomas E. O'Neil   Complement, Complexity, and Symmetric
                                  Representation . . . . . . . . . . . . . 557
               Shiying Wang and   
                   Kai Feng and   
                      Yubao Guo   Sufficient Conditions for Maximally
                                  k-Isoperimetric Edge Connectivity of
                                  Graphs . . . . . . . . . . . . . . . . . 583
                Guangkui Xu and   
                     Xiwang Cao   Constructing New Piecewise
                                  Differentially $4$-Uniform Permutations
                                  from Known APN Functions . . . . . . . . 599
                Tzu-Hsin Ho and   
               Li-Hsing Yen and   
               Chien-Chao Tseng   Simple-Yet-Efficient Construction and
                                  Revocation of Group Signatures . . . . . 611
             Abdullah N. Arslan   Fast Algorithms for Local Similarity
                                  Queries in Two Sequences . . . . . . . . 625
                 Friedrich Otto   Asynchronous Parallel Communicating
                                  Systems of Pushdown Automata . . . . . . 643

International Journal of Foundations of Computer Science (IJFCS)
Volume 26, Number 6, September, 2015

         Aysun Aytaç and   
                   Tufan Turaci   Vulnerability Measures of Transformation
                                  Graph $ G^{xy+} $  . . . . . . . . . . . 667
            Jan van Leeuwen and   
       Ji\vrí Wiedermann   Separating the Classes of Recursively
                                  Enumerable Languages Based on Machine
                                  Size . . . . . . . . . . . . . . . . . . 677
               Hae-Sung Eom and   
                     Yo-Sub Han   State Complexity of Boundary of
                                  Prefix-Free Regular Languages  . . . . . 697
          Zbyn\vek K\vrivka and   
               Alexander Meduna   Jumping Grammars . . . . . . . . . . . . 709
            Laura Giambruno and   
            Sabrina Mantaci and   
         Jean Néraud and   
                    Carla Selmi   A Generalization of Girod's
                                  Bidirectional Decoding Method to Codes
                                  with a Finite Deciphering Delay  . . . . 733
             Brahim Neggazi and   
             Nabil Guellati and   
            Mohammed Haddad and   
            Hamamache Kheddouci   Efficient Self-Stabilizing Algorithm for
                                  Independent Strong Dominating Sets in
                                  Arbitrary Graphs . . . . . . . . . . . . 751
        Javad Akbari Torkestani   Algorithms for Steiner Connected
                                  Dominating Set Problem Based on Learning
                                  Automata Theory  . . . . . . . . . . . . 769

International Journal of Foundations of Computer Science (IJFCS)
Volume 26, Number 7, November, 2015

              Markus Holzer and   
                  Martin Kutrib   Preface  . . . . . . . . . . . . . . . . 803
             Javier Esparza and   
       Michael Luttenberger and   
             Maximilian Schlund   FPSOLVE: A Generic Solver for Fixpoint
                                  Equations Over Semirings . . . . . . . . 805
            Giovanni Pighizzini   Investigations on Automata and Languages
                                  Over a Unary Alphabet  . . . . . . . . . 827
        Georgios Ch. Sirakoulis   The Computational Paradigm of Cellular
                                  Automata in Crowd Evacuation . . . . . . 851
               Ivone Amorim and   
  António Machiavelo and   
            Rogério Reis   On the Number of Linear Finite
                                  Transducers  . . . . . . . . . . . . . . 873
        Maria Paola Bianchi and   
           Carlo Mereghetti and   
                Beatrice Palano   On the Power of One-Way Automata with
                                  Quantum and Classical States . . . . . . 895
          Janusz Brzozowski and   
                 Marek Szyku\la   Large Aperiodic Semigroups . . . . . . . 913
            Marius Dumitran and   
                 Javier Gil and   
               Florin Manea and   
                 Victor Mitrana   Bounded Prefix-Suffix Duplication:
                                  Language Theoretic and Algorithmic
                                  Results  . . . . . . . . . . . . . . . . 933
          Vladimir V. Gusev and   
            Elena V. Pribavkina   Reset Thresholds of Automata with Two
                                  Cycle Lengths  . . . . . . . . . . . . . 953
                Oscar H. Ibarra   On the Ambiguity and Finite-Valuedness
                                  Problems in Acceptors and Transducers    967
                Andreas Maletti   The Power of Weighted
                                  Regularity-Preserving Multi Bottom-Up
                                  Tree Transducers . . . . . . . . . . . . 987

International Journal of Foundations of Computer Science (IJFCS)
Volume 26, Number 8, December, 2015

      Zoltán Ésik   Preface  . . . . . . . . . . . . . . . . 1007
             Hermann Gruber and   
                  Markus Holzer   From Finite Automata to Regular
                                  Expressions and Back --- A Summary on
                                  Descriptional Complexity . . . . . . . . 1009
           Christof Löding   Simplification Problems for
                                  Deterministic Pushdown Automata on
                                  Infinite Words . . . . . . . . . . . . . 1041
               Sebastian Maneth   A Survey on Decidable Equivalence
                                  Problems for Tree Transducers  . . . . . 1069
            Henning Bordihn and   
              Martin Kutrib and   
                Andreas Malcher   Returning Parallel Communicating Finite
                                  Automata with Communication Bounds:
                                  Hierarchies, Decidabilities, and
                                  Undecidabilities . . . . . . . . . . . . 1101
            Vincent Carnino and   
               Sylvain Lombardy   On Determinism and Unambiguity of
                                  Weighted Two-Way Automata  . . . . . . . 1127
                Chen Fei Du and   
            Jeffrey Shallit and   
                 Arseny M. Shur   Optimal Bounds for the Similarity
                                  Density of the Thue--Morse Word with
                                  Overlap-Free and $ 7 / 3$-Power-Free
                                  Infinite Binary Words  . . . . . . . . . 1147
             Henning Fernau and   
              Rudolf Freund and   
                  Markus Holzer   The Finite Index Restriction Meets
                                  Hybrid Modes in Cooperating Distributed
                                  Grammar Systems  . . . . . . . . . . . . 1167
                 Arne Meier and   
             Michael Thomas and   
           Heribert Vollmer and   
                Martin Mundhenk   Erratum: The Complexity of
                                  Satisfiability for Fragments of CTL and
                                  CTL$^\star $ . . . . . . . . . . . . . . 1189
                      Anonymous   Author Index Volume 26 (2015)  . . . . . 1191


International Journal of Foundations of Computer Science (IJFCS)
Volume 27, Number 1, January, 2016

                    Peng Wu and   
                     Minsoo Ryu   EDZL Scheduling and Schedulability
                                  Analysis for Performance Asymmetric
                                  Multiprocessors  . . . . . . . . . . . . 1
           Slavcho Shtrakov and   
                   Ivo Damyanov   On the Computational Complexity of
                                  Finite Operations  . . . . . . . . . . . 15
                  Wen Chean Teh   Separability of $M$-Equivalent Words by
                                  Morphisms  . . . . . . . . . . . . . . . 39
             Changyuan Wang and   
               Daiyuan Peng and   
                 Limengnan Zhou   New Constructions of Optimal
                                  Frequency-Hopping Sequence Sets with
                                  Low-Hit-Zone . . . . . . . . . . . . . . 53
              Marin Bertier and   
            Matthieu Perrin and   
         Cédric Tedeschi   On the Complexity of Concurrent Multiset
                                  Rewriting  . . . . . . . . . . . . . . . 67
                Lunzhi Deng and   
                 Jiwen Zeng and   
                   Huawei Huang   Efficient Certificateless Proxy
                                  Signature Scheme . . . . . . . . . . . . 85

International Journal of Foundations of Computer Science (IJFCS)
Volume 27, Number 2, February, 2016

                    Arseny Shur   Preface  . . . . . . . . . . . . . . . . 101
                  Yuri Gurevich   Past Present . . . . . . . . . . . . . . 103
             Sven De Felice and   
                   Cyril Nicaud   Average Case Analysis of Brzozowski's
                                  Algorithm  . . . . . . . . . . . . . . . 109
              Jorge Almeida and   
                Emanuele Rodaro   Semisimple Synchronizing Automata and
                                  the Wedderburn--Artin Theory . . . . . . 127
           Dmitry Berdinsky and   
           Bakhadyr Khoussainov   Cayley Automatic Representations of
                                  Wreath Products  . . . . . . . . . . . . 147
              Markus Holzer and   
               Sebastian Jakobi   Minimal and Hyper-Minimal Biautomata . . 161
              Martin Kutrib and   
            Andreas Malcher and   
             Matthias Wendlandt   Set Automata . . . . . . . . . . . . . . 187
         Salvatore La Torre and   
          Margherita Napoli and   
                Gennaro Parlato   Scope-Bounded Pushdown Languages . . . . 215
       Pierre-Alain Reynier and   
               Jean-Marc Talbot   Visibly Pushdown Transducers with
                                  Well-Nested Outputs  . . . . . . . . . . 235
Zuzana Bednárová and   
             Viliam Geffert and   
            Klaus Reinhardt and   
             Abuzer Yakaryilmaz   New Results on the Minimum Amount of
                                  Useful Space . . . . . . . . . . . . . . 259
         Abuzer Yakaryilmaz and   
              A. C. Cem Say and   
         H. Gökalp Demirci   Debates with Small Transparent Quantum
                                  Verifiers  . . . . . . . . . . . . . . . 283

International Journal of Foundations of Computer Science (IJFCS)
Volume 27, Number 3, April, 2016

Szilárd Zsolt Fazekas and   
    Kayoko Shikishima-Tsuji and   
               Akihiro Yamamura   Preface  . . . . . . . . . . . . . . . . 301
                  Jing Tian and   
                  Yong Shao and   
                 Xianzhong Zhao   Out Subword-Free Languages and Its
                                  Subclasses . . . . . . . . . . . . . . . 305
            Yoshiyuki Kunimochi   Some Properties of Extractable Codes and
                                  Insertable Codes . . . . . . . . . . . . 327
                  Peter Leupold   General Idempotency Languages Over Small
                                  Alphabets  . . . . . . . . . . . . . . . 343
           Alexander Meduna and   
                Ond\vrej Soukup   Simple Matrix Grammars and Their
                                  Leftmost Variants  . . . . . . . . . . . 359
        Kayoko Shikishima-Tsuji   Regularity of Iterative Hairpin
                                  Completions of Crossing $ (2, 2)$-Words  375
         Hiroyuki Chigahara and   
Szilárd Zsolt Fazekas and   
               Akihiro Yamamura   One-Way Jumping Finite Automata  . . . . 391

International Journal of Foundations of Computer Science (IJFCS)
Volume 27, Number 4, June, 2016

         Janusz Januszewski and   
               \Lukasz Zielonka   Improved Online Algorithms for $2$-Space
                                  Bounded $2$-Dimensional Bin Packing  . . 407
            Michael Forsyth and   
           Amlesh Jayakumar and   
      Jarkko Peltomäki and   
                Jeffrey Shallit   Remarks on Privileged Words  . . . . . . 431
                Shanding Xu and   
                 Xiwang Cao and   
                    Guangkui Xu   Optimal Frequency-Hopping Sequence Sets
                                  Based on Cyclotomy . . . . . . . . . . . 443
               Yongjia Wang and   
                   Xi Xiong and   
                    Haining Fan   $ {\rm GF}(2^n) $ Redundant
                                  Representation Using Matrix Embedding
                                  for Irreducible Trinomials . . . . . . . 463
               Somnath Bera and   
             Kalpana Mahalingam   Some Algebraic Aspects of Parikh
                                  $q$-Matrices . . . . . . . . . . . . . . 479
               Zongtian Wei and   
                  Nannan Qi and   
                    Xiaokui Yue   Vertex-Neighbor-Scattering Number of
                                  Bipartite Graphs . . . . . . . . . . . . 501
      Carole J. Etherington and   
        Matthew W. Anderson and   
                  Eric Bach and   
              Jon T. Butler and   
         Pantelimon St\uanic\ua   A Parallel Approach in Computing
                                  Correlation Immunity up to Six Variables 511

International Journal of Foundations of Computer Science (IJFCS)
Volume 27, Number 5, August, 2016

               Ali Alatabbi and   
       Costas S. Iliopoulos and   
             Alessio Langiu and   
                M. Sohel Rahman   Algorithms for Longest Common Abelian
                                  Factors  . . . . . . . . . . . . . . . . 529
                  Wen Chean Teh   Parikh Matrices and Strong
                                  $M$-Equivalence  . . . . . . . . . . . . 545
                Vojt\vech Vorel   Subset Synchronization and Careful
                                  Synchronization of Binary Finite
                                  Automata . . . . . . . . . . . . . . . . 557
                Savio S. H. Tse   Belated Analyses of Three Credit-Based
                                  Adaptive Polling Algorithms  . . . . . . 579
              Xianfang Wang and   
                   Jian Gao and   
                    Fang-Wei Fu   Secret Sharing Schemes from Linear Codes
                                  over $ F_p + \nu F_p $ . . . . . . . . . 595
                 Eddy Caron and   
              Ajoy K. Datta and   
               Franck Petit and   
         Cédric Tedeschi   Self-Stabilizing Prefix Tree Based
                                  Overlay Networks . . . . . . . . . . . . 607
           Julien Cassaigne and   
          Idrissa Kaboré   Abelian Complexity and Frequencies of
                                  Letters in Infinite Words  . . . . . . . 631
           Alexander Meduna and   
                Ond\vrej Soukup   Corrigendum: ``Simple Matrix Grammars
                                  and Their Leftmost Variants [3]''  . . . 651

International Journal of Foundations of Computer Science (IJFCS)
Volume 27, Number 6, September, 2016

              Wenming Zhang and   
                   E. Zhang and   
                  Feifeng Zheng   Online Two Stage $k$-Search Problem and
                                  Its Competitive Analysis . . . . . . . . 653
                  Jiyong Lu and   
                  Jun Zhang and   
                 Xuan Guang and   
                    Fang-Wei Fu   Multiple Repair Localities with Distinct
                                  Erasure Tolerance  . . . . . . . . . . . 665
               Pascal Caron and   
         Jean-Gabriel Luque and   
             Ludovic Mignot and   
                   Bruno Patrou   State Complexity of Catenation Combined
                                  with a Boolean Operation: A Unified
                                  Approach . . . . . . . . . . . . . . . . 675
                 Sang-Ki Ko and   
               Hae-Sung Eom and   
                     Yo-Sub Han   Operational State Complexity of
                                  Subtree-Free Regular Tree Languages  . . 705
                    Ersin Aslan   Weak-Rupture Degree of Graphs  . . . . . 725
      Ferhan Nihan Altundag and   
             Goksen Bacak-Turan   Neighbor Rupture Degree of Harary Graphs 739
            Adrian Atanasiu and   
                  Wen Chean Teh   A New Operator over Parikh Languages . . 757
      Édouard Bonnet and   
                 Florian Sikora   A Note on Edge Isoperimetric Numbers and
                                  Regular Graphs . . . . . . . . . . . . . 771

International Journal of Foundations of Computer Science (IJFCS)
Volume 27, Number 7, November, 2016

       Lakshmanan Kuppusamy and   
           Indhumathi Raman and   
             Kamala Krithivasan   On Succinct Description of Certain
                                  Context-Free Languages by Ins-Del and
                                  Matrix Ins-Del Systems . . . . . . . . . 775
    Peter Kostolányi and   
                Branislav Rovan   Automata with Auxiliary Weights  . . . . 787
               David Caissy and   
                   Andrzej Pelc   Exploration of Faulty Hamiltonian Graphs 809
                 Satoshi Fujita   On the Power of Lookahead in Greedy
                                  Scheme for Finding a Minimum CDS for
                                  Unit Disk Graphs . . . . . . . . . . . . 829
                 Hui-Jie Xu and   
               Wan-Dong Cai and   
                  Gui-Rong Chen   Forums-Oriented Research on the
                                  Spreading and Inhibition of Rumors . . . 845
                 Yo-Sub Han and   
                 Sang-Ki Ko and   
                 Timothy Ng and   
                    Kai Salomaa   State Complexity of Insertion  . . . . . 863
                  Zibi Xiao and   
             Xiangyong Zeng and   
                     Zhimin Sun   $2$-Adic Complexity of Two Classes of
                                  Generalized Cyclotomic Binary Sequences  879

International Journal of Foundations of Computer Science (IJFCS)
Volume 27, Number 8, December, 2016

               Francis Chin and   
            Oscar H. Ibarra and   
                Sartaj K. Sahni   Announcement . . . . . . . . . . . . . . 895--896
                  Haibo Liu and   
                   Qunying Liao   Some New Constructions for Generalized
                                  Zero-Difference Balanced Functions . . . 897--908
             Saeid Alirezazadeh   On Pseudovarieties of Forest Algebras    909--942
                Chen Fei Du and   
             Hamoon Mousavi and   
             Luke Schaeffer and   
                Jeffrey Shallit   Decision Algorithms for
                                  Fibonacci-Automatic Words, III:
                                  Enumeration and Abelian Properties . . . 943--964
                 Sang-Ki Ko and   
                 Ha-Rim Lee and   
                     Yo-Sub Han   State Complexity of Regular Tree
                                  Languages for Tree Matching  . . . . . . 965--980
                Toru Fujita and   
                Koji Nakano and   
                    Yasuaki Ito   Fast Simulation of Conway's Game of Life
                                  Using Bitwise Parallel Bulk Computation
                                  on a GPU . . . . . . . . . . . . . . . . 981--1004
                      Anonymous   Author Index Volume 27 (2016)  . . . . . 1005


International Journal of Foundations of Computer Science (IJFCS)
Volume 28, Number 1, January, 2017

                Guangkui Xu and   
                 Xiwang Cao and   
                    Shanding Xu   Several Classes of Quadratic Ternary
                                  Bent, Near-Bent and $2$-Plateaued
                                  Functions  . . . . . . . . . . . . . . . ??
                 Rongjia Li and   
                    Chenhui Jin   Meet-in-the-Middle Attack on $ 11$-Round
                                  $3$D Block Cipher  . . . . . . . . . . . 
         Vecdi Aytaç and   
         Zeynep Nihan Berberler   Binding Number and Wheel Related Graphs  
               Frank Gurski and   
        Patrick Gwydion Poullie   Interval Routing Schemes for
                                  Circular-Arc Graphs  . . . . . . . . . . 
              Dongfang Zhou and   
                 Jianxi Fan and   
             Cheng-Kuan Lin and   
                Jingya Zhou and   
                        Xi Wang   Cycles Embedding in Exchanged Crossed
                                  Cube . . . . . . . . . . . . . . . . . . 
             Samir Elouasbi and   
                   Andrzej Pelc   Deterministic Rendezvous with Detection
                                  Using Beeps  . . . . . . . . . . . . . . 

International Journal of Foundations of Computer Science (IJFCS)
Volume 28, Number 2, February, 2017

                 Xiang Wang and   
                    Fang-Wei Fu   Deterministic Construction of Compressed
                                  Sensing Matrices from Codes  . . . . . . ??
             Quentin Bramas and   
       Sébastien Tixeuil   The Random Bit Complexity of Mobile
                                  Robots Scattering  . . . . . . . . . . . 
                  Michael Coons   Regular Sequences and the Joint Spectral
                                  Radius . . . . . . . . . . . . . . . . . 
             George Lagogiannis   Query-Optimal Partially Persistent
                                  B-Trees with Constant Worst-Case Update
                                  Time . . . . . . . . . . . . . . . . . . 
               Zuling Chang and   
                  Pinhui Ke and   
                 Yongcheng Zhao   Some Enumeration Results on Binary $
                                  2^n$-Periodic Sequences  . . . . . . . . 
                  Stefan Arnold   Identifying Generalized Reed--Muller
                                  Codewords by Quantum Queries . . . . . . 

International Journal of Foundations of Computer Science (IJFCS)
Volume 28, Number 3, April, 2017

     Alexandros Palioudakis and   
                Kai Salomaa and   
                   Selim G. Akl   Worst Case Branching and Other Measures
                                  of Nondeterminism  . . . . . . . . . . . 195
                    Jing Li and   
                Yuxing Yang and   
                    Xiaohui Gao   Hamiltonicity of the Torus Network Under
                                  the Conditional Fault Model  . . . . . . 211
              Markus Holzer and   
               Sebastian Jakobi   More on Minimizing Finite Automata with
                                  Errors --- Nondeterministic Machines . . 229
              Wen Chean Teh and   
                Adrian Atanasiu   Minimal Reaction Systems Revisited and
                                  Reaction System Rank . . . . . . . . . . 247
              Jean Mairesse and   
              Ir\`ene Marcovici   Uniform Sampling of Subshifts of Finite
                                  Type on Grids and Trees  . . . . . . . . 263
                     Meng Zhang   Fast Convolutions of Packed Strings and
                                  Pattern Matching with Wildcards  . . . . 289

International Journal of Foundations of Computer Science (IJFCS)
Volume 28, Number 4, June, 2017

              Zahra Moslehi and   
                Alireza Bagheri   Separating Bichromatic Point Sets by
                                  Minimal Triangles with a Fixed Angle . . 309
           Benjamin Russell and   
                  Susan Stepney   The Geometry of Speed Limiting Resources
                                  in Physical Models of Computation  . . . 321
         Goksen Bacak-Turan and   
                       Ekrem Oz   Neighbor Rupture Degree of
                                  Transformation Graphs $ G^{xy-} $  . . . 335
               Zhiqiang Sun and   
                         Lei Hu   Several Classes of Boolean Functions
                                  with Four-Valued Walsh Spectra . . . . . 357
             Dima Grigoriev and   
             Laszlo B. Kish and   
             Vladimir Shpilrain   Yao's Millionaires' Problem and
                                  Public-Key Encryption Without
                                  Computational Assumptions  . . . . . . . 379
                  Pinhui Ke and   
                  Zhifan Ye and   
             Zhengchun Zhou and   
                      Jian Shen   Autocorrelation of the Modified Binary
                                  Two-Prime Sidelnikov Sequence  . . . . . 391
               Rachid Hadid and   
       Mehmet Hakan Karaata and   
                Vincent Villain   A Stabilizing Algorithm for Finding Two
                                  Node-Disjoint Paths in Arbitrary
                                  Networks . . . . . . . . . . . . . . . . 411

International Journal of Foundations of Computer Science (IJFCS)
Volume 28, Number 5, August, 2017

                 Yo-Sub Han and   
                    Kai Salomaa   Preface  . . . . . . . . . . . . . . . . 437
  Zoltán Fülöp   In Memoriam Zoltán Ésik (1951--2016) . . . 441
      Christos A. Kapoutsis and   
                Lamana Mulaffer   A Logical Characterization of Small
                                  2NFAs  . . . . . . . . . . . . . . . . . 445
            Shinnosuke Seki and   
                 Andrew Winslow   The Complexity of Fixed-Height Patterned
                                  Tile Self-Assembly . . . . . . . . . . . 465
          Aleksandrs Belovs and   
          J. Andres Montoya and   
      Abuzer Yakaryìlmaz   On a Conjecture by Christian Choffrut    483
        Holger Bock Axelsen and   
              Markus Holzer and   
                  Martin Kutrib   The Degree of Irreversibility in
                                  Deterministic Finite Automata  . . . . . 503
               Markus Teichmann   Regular Approximation of Weighted Linear
                                  Context-Free Tree Languages  . . . . . . 523
            Martin Sulzmann and   
             Kenny Zhuo Ming Lu   Derivative-Based Diagnosis of Regular
                                  Expression Ambiguity . . . . . . . . . . 543
                 Akio Fujiyoshi   A Practical Algorithm for the Uniform
                                  Membership Problem of Labeled
                                  Multidigraphs of Tree-Width 2 for
                                  Spanning Tree Automata . . . . . . . . . 563
                Suna Bensch and   
     Johanna Björklund and   
                  Martin Kutrib   Deterministic Stack Transducers  . . . . 583
       Jorge Calvo-Zaragoza and   
                Jose Oncina and   
            Colin de la Higuera   Computing the Expected Edit Distance
                                  from a String to a Probabilistic
                                  Finite-State Automaton . . . . . . . . . 603
               Daniel Pr\ru\vsa   Complexity of Matching Sets of
                                  Two-Dimensional Patterns by
                                  Two-Dimensional On-Line Tessellation
                                  Automaton  . . . . . . . . . . . . . . . 623

International Journal of Foundations of Computer Science (IJFCS)
Volume 28, Number 6, September, 2017

               Jinguang Han and   
Yogachandran Rahulamathavan and   
                   Willy Susilo   Preface  . . . . . . . . . . . . . . . . 641
               Chunguang Ma and   
                   Juyan Li and   
                 Weiping Ouyang   Lattice-Based Identity-Based Homomorphic
                                  Conditional Proxy Re-Encryption for
                                  Secure Big Data Computing in Cloud
                                  Environment  . . . . . . . . . . . . . . 645
            Rashed Mazumder and   
              Atsuko Miyaji and   
                     Chunhua Su   Probably Secure Keyed-Function Based
                                  Authenticated Encryption Schemes for Big
                                  Data . . . . . . . . . . . . . . . . . . 661
                 Youwen Zhu and   
                 Xingxin Li and   
                  Jian Wang and   
                 Yining Liu and   
                      Zhiguo Qu   Practical Secure Na\"\ive Bayesian
                                  Classification Over Encrypted Big Data
                                  in Cloud . . . . . . . . . . . . . . . . 683
                    Gang Yu and   
                Xiaoxiao Ma and   
                 Zhenfu Cao and   
                 Guang Zeng and   
                     Wenbao Han   Accountable CP-ABE with Public
                                  Verifiability: How to Effectively
                                  Protect the Outsourced Data in Cloud . . 705
             Yangguang Tian and   
                Guomin Yang and   
                      Yi Mu and   
               Shiwei Zhang and   
               Kaitai Liang and   
                        Yong Yu   One-Round Attribute-Based Key Exchange
                                  in the Multi-Party Setting . . . . . . . 725
                 Fucai Zhou and   
                    Su Peng and   
                    Jian Xu and   
                      Zifeng Xu   Identity-Based Batch Provable Data
                                  Possession with Detailed Analyses  . . . 743
               Jianye Huang and   
                Qiong Huang and   
                    Chunhua Pan   A Black-Box Construction of Strongly
                                  Unforgeable Signature Scheme in the
                                  Leakage Setting  . . . . . . . . . . . . 761
             Chin-Ling Chen and   
               Jungpil Shin and   
               Yu-Ting Tsai and   
        Aniello Castiglione and   
             Francesco Palmieri   Securing Information Exchange in VANETs
                                  by Using Pairing-Based Cryptography  . . 781
                Jiameng Sun and   
                 Binrui Zhu and   
                   Jing Qin and   
                 Jiankun Hu and   
                    Qianhong Wu   Confidentiality-Preserving Publicly
                                  Verifiable Computation . . . . . . . . . 799

International Journal of Foundations of Computer Science (IJFCS)
Volume 28, Number 7, November, 2017

                    Lei Sun and   
                 Fangwei Fu and   
                       Jian Liu   On the Conjecture About the Linear
                                  Structures of Rotation Symmetric Boolean
                                  Functions  . . . . . . . . . . . . . . . 819
         Aysun Aytaç and   
Zeynep Nihan Odaba\cs Berberler   Robustness of Regular Caterpillars . . . 835
              Jianghong Wei and   
                Xinyi Huang and   
                 Wenfen Liu and   
                     Xuexian Hu   Cost-Effective and Scalable Data Sharing
                                  in Cloud Storage Using Hierarchical
                                  Attribute-Based Encryption with Forward
                                  Security . . . . . . . . . . . . . . . . 843
             Gokarna Sharma and   
                   Costas Busch   The Bursty Steiner Tree Problem  . . . . 869
                    Jie Lin and   
                  Yue Jiang and   
            E. James Harner and   
             Bing-Hua Jiang and   
                    Don Adjeroh   IDPM: An Improved Degenerate Pattern
                                  Matching Algorithm for Biological
                                  Sequences  . . . . . . . . . . . . . . . 889
                   Lili Guo and   
                    Xi Wang and   
             Cheng-Kuan Lin and   
                Jingya Zhou and   
                     Jianxi Fan   A Fault-Free Unicast Algorithm in the
                                  Generalized Hypercube with Restricted
                                  Faulty Vertices  . . . . . . . . . . . . 915
         Vaishali M. Wadhwa and   
                    Deepak Garg   Approximation Algorithm for Resource
                                  Allocation Problems with Time Dependent
                                  Penalties  . . . . . . . . . . . . . . . 931

International Journal of Foundations of Computer Science (IJFCS)
Volume 28, Number 8, December, 2017

        Mohamed Faouzi Atig and   
            Benedikt Bollig and   
                Peter Habermehl   Emptiness of Ordered Multi-Pushdown
                                  Automata is 2ETIME-Complete  . . . . . . 945
                 Wenyi Hong and   
                    Zhenbo Wang   Improved Approximation Algorithm for the
                                  Combination of Parallel Machine
                                  Scheduling and Vertex Cover  . . . . . . 977
                  Yinkui Li and   
                 Mingzhe Du and   
                 Hongyan Li and   
                   Xiaolin Wang   Edge Rupture Degree of Graphs  . . . . . 993
             Sepinoud Azimi and   
             Charmi Panchal and   
             Andrzej Mizera and   
                      Ion Petre   Multi-Stability, Limit Cycles, and
                                  Period-Doubling Bifurcation with
                                  Reaction Systems . . . . . . . . . . . . 1007
Joel Antonio Trejo-Sánchez and   
José Alberto Fernández-Zepeda and   
Julio César Ramírez-Pacheco   A Self-Stabilizing Algorithm for a
                                  Maximal $2$-Packing in a Cactus Graph
                                  Under Any Scheduler  . . . . . . . . . . 1021
                Pingshan Li and   
                         Min Xu   The Super Spanning Connectivity of
                                  Arrangement Graphs . . . . . . . . . . . 1047
                      Anonymous   Author Index Volume 28 (2017)  . . . . . 1073


International Journal of Foundations of Computer Science (IJFCS)
Volume 29, Number 1, January, 2018

                Vojt\vech Vorel   On Basic Properties of Jumping Finite
                                  Automata . . . . . . . . . . . . . . . . 1
               Martin Lück   Quirky Quantifiers: Optimal Models and
                                  Complexity of Computation Tree Logic . . 17
        Safia Kedad-Sidhoum and   
             Florence Monna and   
Grégory Mounié and   
                 Denis Trystram   A Family of Scheduling Algorithms for
                                  Hybrid Parallel Platforms  . . . . . . . 63
               Nianfeng Lin and   
              Damei Lü and   
                    Jinhua Wang   $ L(2, 1) $-Edge-Labelings of the
                                  Edge-Path-Replacement of a Graph . . . . 91
Alejandro López-Ortiz and   
           Cynthia B. Perez and   
           Jazmín Romero   Arbitrary Overlap Constraints in Graph
                                  Packing Problems . . . . . . . . . . . . 101
    Ghajendran Poovanandran and   
                  Wen Chean Teh   On $M$-Equivalence and Strong
                                  $M$-Equivalence for Parikh Matrices  . . 123

International Journal of Foundations of Computer Science (IJFCS)
Volume 29, Number 2, February, 2018

               Igor Potapov and   
                 Pavel Semukhin   Preface  . . . . . . . . . . . . . . . . 139
               Hideo Bannai and   
               Travis Gagie and   
           Shunsuke Inenaga and   
  Juha Kärkkäinen and   
              Dominik Kempa and   
        Marcin Pi\katkowski and   
                 Shiho Sugimoto   Diverse Palindromic Factorization is
                                  NP-Complete  . . . . . . . . . . . . . . 143
          Dietmar Berwanger and   
          Marie van den Bogaard   Consensus Game Acceptors and Iterated
                                  Transductions  . . . . . . . . . . . . . 165
        Maria Paola Bianchi and   
          Juraj Hromkovi\vc and   
            Ivan Ková\vc   On the Size of Two-Way Reasonable
                                  Automata for the Liveness Problem  . . . 187
          Christopher Czyba and   
            Wolfgang Thomas and   
           Christopher Spinrath   Finite Automata Over Infinite Alphabets:
                                  Two Models with Transitions for Local
                                  Change . . . . . . . . . . . . . . . . . 213
              Joey Eremondi and   
            Oscar H. Ibarra and   
                  Ian McQuillan   On the Density of Context-Free and
                                  Counter Languages  . . . . . . . . . . . 233
              Markus Holzer and   
           Sebastian Jakobi and   
                  Martin Kutrib   Minimal Reversible Deterministic Finite
                                  Automata . . . . . . . . . . . . . . . . 251
         Ismaël Jecker and   
                Emmanuel Filiot   Multi-Sequential Word Relations  . . . . 271
               Ines Klimann and   
          Matthieu Picantin and   
                 Dmytro Savchuk   A Connected $3$-State Reversible Mealy
                                  Automaton Cannot Generate an Infinite
                                  Burnside Group . . . . . . . . . . . . . 297
                 Timothy Ng and   
            David Rappaport and   
                    Kai Salomaa   State Complexity of Neighbourhoods and
                                  Approximate Pattern Matching . . . . . . 315

International Journal of Foundations of Computer Science (IJFCS)
Volume 29, Number 3, April, 2018

         Michelangelo Bucci and   
          Gwenaël Richomme   Greedy Palindromic Lengths . . . . . . . 331
           Khodakhast Bibak and   
            Bruce M. Kapron and   
       Venkatesh Srinivasan and   
László Tóth   On an Almost-Universal Hash Function
                                  Family with Applications to
                                  Authentication and Secrecy Codes . . . . 357
          Parisa Derakhshan and   
                  Walter Hussak   Optimal Bounds for Disjoint Hamilton
                                  Cycles in Star Graphs  . . . . . . . . . 377
              Pardis Kavand and   
                    Ali Mohades   A Time-Space Trade-off for the Shortest
                                  Path Tree in a Simple Polygon  . . . . . 391
               Somnath Bera and   
         Kalpana Mahalingam and   
              K. G. Subramanian   Properties of Parikh Matrices of Binary
                                  Words Obtained by an Extension of a
                                  Restricted Shuffle Operator  . . . . . . 403
Luan Carlos de Sena Monteiro Ozelim and   
   Andre Luis Brasil Cavalcante   The Iota-Delta Function as an
                                  Alternative to Boolean Formalism . . . . 415
               Masaki Nakanishi   Quantum Pushdown Automata with Garbage
                                  Tape . . . . . . . . . . . . . . . . . . 425
     Zeynep Nihan Berberler and   
                     Esin Yigit   Link Vulnerability in Networks . . . . . 447

International Journal of Foundations of Computer Science (IJFCS)
Volume 29, Number 4, June, 2018

                Jarkko Kari and   
              Alexander Okhotin   Preface  . . . . . . . . . . . . . . . . 457
          Patrizio Angelini and   
          Giordano Da Lozzo and   
        Marco Di Bartolomeo and   
        Valentino Di Donato and   
        Maurizio Patrignani and   
           Vincenzo Roselli and   
              Ioannis G. Tollis   Algorithms and Bounds for $L$-Drawings
                                  of Directed Graphs . . . . . . . . . . . 461
            Harout Aydinian and   
        Ferdinando Cicalese and   
            Christian Deppe and   
               Vladimir Lebedev   A Combinatorial Model of Two-Sided
                                  Search . . . . . . . . . . . . . . . . . 481
        Maria Paola Bianchi and   
Hans-Joachim Böckenhauer and   
    Tatjana Brülisauer and   
                Dennis Komm and   
                Beatrice Palano   Online Minimum Spanning Tree with Advice 505
            Olivier Bournez and   
         Oleksiy Kurganskyy and   
                   Igor Potapov   Reachability Problems for
                                  One-Dimensional Piecewise Affine Maps    529
           Elisabet Burjons and   
          Juraj Hromkovi\vc and   
Rastislav Královi\vc and   
  Richard Královi\vc and   
        Xavier Muñoz and   
                   Walter Unger   Online Graph Coloring Against a
                                  Randomized Adversary . . . . . . . . . . 551
                M. W. Gazda and   
              T. A. C. Willemse   Cooking Your Own Parity Game Preorders
                                  Through Matching Plays . . . . . . . . . 571
         Jan Clemens Gehrke and   
               Klaus Jansen and   
         Stefan E. J. Kraft and   
               Jakob Schikowski   A PTAS for Scheduling Unrelated Machines
                                  of Few Different Types . . . . . . . . . 591
          Heikki Hyyrö and   
               Shunsuke Inenaga   Dynamic RLE-Compressed Edit Distance
                                  Tables Under General Weighted Cost
                                  Functions  . . . . . . . . . . . . . . . 623
          Dmitry Kravchenko and   
          Nikolajs Nahimovs and   
               Alexander Rivosh   Grover's Search with Faults on Some
                                  Marked Elements  . . . . . . . . . . . . 647
                  Kent Kwee and   
                 Friedrich Otto   Nondeterministic Ordered Restarting
                                  Automata . . . . . . . . . . . . . . . . 663
          Nikolajs Nahimovs and   
               Alexander Rivosh   Quantum Walks on Two-Dimensional Grids
                                  with Multiple Marked Locations . . . . . 687