International Journal of Foundations of Computer Science, Volume 23

Volume 23, Number 1, January 2012

• 
  Ian McQuillan, Giovanni Pighizzini:
  Preface.
• 
  Martin Kappes, Andreas Malcher, Detlef Wotschke:
  In Memoriam Chandra Kintala. 5-19
• 
  Janusz A. Brzozowski, Baiyu Li, Yuli Ye:
  On the Complexity of the Evaluation of Transient Extensions of Boolean Functions. 21-35
• 
  Cristian S. Calude, Kai Salomaa, Tania Roblot:
  State-Size Hierarchy for Finite-State Complexity. 37-50
• 
  Bo Cui, Yuan Gao, Lila Kari, Sheng Yu:
  State Complexity of Two Combined Operations: Catenation-Star and Catenation-Reversal. 51-66
• 
  Krystian Dudzinski, 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, Bianca Truthe:
  A Comparison of the Descriptional Complexity of Classes of Limited Lindenmayer Systems: Part I. 99-114
• 
  Markus Holzer, Sebastian Jakobi, Martin Kutrib:
  The Magic Number Problem for Subregular Language Families. 115-131
• 
  Przemyslaw Prusinkiewicz, Mitra Shirmohammadi, Faramarz Samavati:
  L-Systems in Geometric Modeling. 133-146
• 
  Adilson Luiz Bonifácio, Arnaldo Vieira Moura, Adenilso da Silva Simão:
  Model Partitions and Compact Test Case Suites. 147-172
• 
  Junping Zhou, Minghao Yin, Xiangtao Li, Jinyan Wang:
  Phase Transitions of EXPSPACE-Complete Problems: a Further Step. 173-184
• 
  Egor Dolzhenko, Natasa Jonoska:
  Two-Dimensional Languages and Cellular Automata. 185-206
• 
  Kalpana Mahalingam, K. G. Subramanian:
  Product of Parikh Matrices and Commutativity. 207-223
• 
  César Domínguez, Dominique Duval:
  A Parameterization Process: from a Functorial Point of View. 225-242

Volume 23, Number 2, February 2012

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

Volume 23, Number 3, April 2012

• 
  Angelo Montanari, Margherita Napoli, Mimmo Parente:
  Preface.
• 
  Davide Bresolin, Pietro Sala, Guido Sciavicco:
  On Begins, Meets and before. 559-583
• 
  Lubos Brim, Jakub Chaloupka:
  Using Strategy Improvement to Stay Alive. 585-608
• 
  Krishnendu Chatterjee, Rupak Majumdar:
  Discounting and Averaging in Games across Time scales. 609-625
• 
  Giovanna D'Agostino, Giacomo Lenzi:
  On Modal μ-Calculus over Finite Graphs with Small Components or Small Tree Width. 627-647
• 
  John Fearnley, Martin Zimmermann:
  Playing Muller Games in a Hurry. 649-668
• 
  Oliver Friedmann, Martin Lange:
  Two Local Strategy Iteration Schemes for Parity Game Solving. 669-685
• 
  Hugo Gimbert, Wieslaw Zielonka:
  Blackwell Optimal Strategies in Priority mean-Payoff Games. 687-711
• 
  Henning Bordihn, Martin Kutrib, Andreas Malcher:
  On the Computational Capacity of Parallel Communicating Finite Automata. 713-732
• 
  Yuechuan Wei, Chao Li, Dan Cao:
  Improved Related-Key Rectangle Attack on the Full has-160 Encryption Mode. 733-747
• 
  Deshuai Dong, Longjiang Qu, Shaojing Fu, Chao Li:
  New Constructions of Vectorial Boolean Functions with Good Cryptographic Properties. 749-760

Volume 23, Number 4, June 2012

Special Issue - Advances in Parallel and Distributed Computational Models

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

Volume 23, Number 5, August 2012

Special Issue - Developments in Language Theory (DLT 2011)

• 
  Giancarlo Mauri, Alberto Leporati:
  Preface. 965-968
• 
  Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis:
  On the Average Size of Glushkov and Partial derivative Automata. 969-984
• 
  Namit Chaturvedi, Jörg Olschewski, Wolfgang Thomas:
  Languages versus ω-Languages in Regular Infinite Games. 985-1000
• 
  Volker Diekert, Alexei G. Myasnikov:
  Group Extensions over Infinite Words. 1001-1020
• 
  Michael Domaratzki, Narad Rampersad:
  Abelian Primitive Words. 1021-1034
• 
  Emilie Charlier, Narad Rampersad, Jeffrey Shallit:
  Enumeration and Decidable Properties of Automatic Sequences. 1035-1066
• 
  Edita Pelantová, Stepán Starosta:
  Almost Rich Words as Morphic Images of Rich Words. 1067-1084
• 
  Yuan Gao, Sheng Yu:
  State Complexity and Approximation. 1085-1098
• 
  A. C. Cem Say, Abuzer Yakaryilmaz:
  Quantum Counter Automata. 1099-1116
• 
  Shenggen Zheng, Daowen Qiu, Lvzhou Li:
  Some Languages Recognized by Two-Way Finite Automata with Quantum and Classical States. 1117-1130
• 
  Pablo Arrighi, Gilles Dowek:
  The Physical Church-Turing Thesis and the Principles of Quantum Theory. 1131-1146
• 
  Guaning Chen, Chih-Wei Yi, Min-Te Sun, Fang-Chun Liu, Wei-Chi Lan:
  Minimum Local Disk Cover Sets for Broadcasting in Heterogeneous Multihop Wireless Networks. 1147-1172
• 
  Andrzej Ehrenfeucht, Michael G. Main, Grzegorz Rozenberg, Allison Thompson Brown:
  Stability and Chaos in reaction Systems. 1173-

Volume 23, Number 6, September 2012

Special Issue - Automata and Formal Languages (AFL 2011)

• 
  Pál Dömösi, Zoltán Ésik:
  Preface. 1185-1188
• 
  Francine Blanchet-Sadri:
  Algorithmic Combinatorics on Partial Words. 1189-1206
• 
  Andreas Maletti, Daniel Quernheim:
  Unweighted and Weighted Hyper-Minimization. 1207-1226
• 
  Jean-Éric Pin:
  Equational Descriptions of Languages. 1227-1240
• 
  Gilles Benattar, Béatrice Bérard, Didier Lime, John Mullins, Olivier H. Roux, Mathieu Sassolas:
  Channel Synthesis for Finite Transducers. 1241-1260
• 
  Janusz A. Brzozowski, Bo Liu:
  Quotient Complexity of Star-Free Languages. 1261-1276
• 
  Szilárd Zsolt Fazekas, Peter Leupold, Kayoko Shikishima-Tsuji:
  On Non-Primitive Palindromic Context-Free Languages. 1277-1290
• 
  Oscar H. Ibarra, Shinnosuke Seki:
  Characterizations of Bounded semilinear Languages by One-Way and Two-Way Deterministic Machines. 1291-1306
• 
  Lila Kari, Zhi Xu:
  De Bruijn Sequences Revisited. 1307-1322
• 
  Manfred Kufleitner, Alexander Lauser:
  Around dot-Depth One. 1323-1340

Regular Papers

• 
  Keqin Li:
  Probing High-Capacity Peers to Reduce Download times in P2P File Sharing Systems with Stochastic Service Capacities. 1341-1370
• 
  Michalis Christou, Maxime Crochemore, Costas S. Iliopoulos:
  Identifying All Abelian Periods of a String in quadratic Time and Relevant Problems. 1371-1384
• 
  Jana Hadravová, Stepan Holub:
  Large Simple Binary Equality Words. 1385-1404
• 
  Orly Yahalom:
  Testing for forbidden Posets in Ordered Rooted Forests. 1405-

Volume 23, Number 7, November 2012

Special Issue - The Frontier Between Decidability and Undecidability and Related Problems

• 
  Jérôme Durand-Lose, Maurice Margenstern, Klaus Sutner:
  Preface. 1419-1422
• 
  Artiom Alhazov, Yurii Rogozhin, Sergey Verlan:
  On Small Universal Splicing Systems. 1423-1438
• 
  David Auger, Olivier Teytaud:
  The Frontier of Decidability in Partially Observable Recursive Games. 1439-1450
• 
  Amir M. Ben-Amram, Lars Kristiansen:
  On the Edge of Decidability in Complexity Analysis of Loop Programs. 1451-1464
• 
  Mark Burgin:
  Decidability and Universality in the Axiomatic Theory of Computability and Algorithms. 1465-1480
• 
  Olivier Finkel:
  Three Applications to Rational Relations of the High Undecidability of the Infinite Post Correspondence Problem in a Regular ω-Language. 1481-1498
• 
  Klaus Meer:
  Some Initial Thoughts on Bounded Query Computations over the Reals. 1499-1510
• 
  Yunyun Niu, K. G. Subramanian, Ibrahim Venkat, Rosni Abdullah:
  A Tissue P System Based solution to quadratic Assignment Problem. 1511-1522

Regular Papers

• 
  Hammadi Bennoui, Allaoua Chaoui, Kamel Barkaoui:
  On Structural Analysis of Interacting Behavioral Petri Nets for Distributed Causal Model-Based Diagnosis. 1523-1542
• 
  Chung-Shou Liao, Louxin Zhang:
  Approximating the Spanning k-Tree forest Problem. 1543-1554
• 
  Alexander Meduna, Petr Zemek:
  Jumping Finite Automata. 1555-1578

Volume 23, Number 8, December 2012

Special Issue - WORDS 2011

• 
  Zuzana Masáková, Stepan Holub:
  Preface. 1579-1582
• 
  Irina A. Gorbunova, Arseny M. Shur:
  On Pansiot Words Avoiding 3-Repetitions. 1583-1594
• 
  Elena A. Petrova, Arseny M. Shur:
  Constructing Premaximal Binary Cube-Free Words of any Level. 1595-1610
• 
  Luke Schaeffer, Jeffrey Shallit:
  The Critical Exponent is Computable for Automatic Sequences. 1611-1626
• 
  Daniel Dombek:
  Substitutions over Infinite Alphabet Generating (-β)-Integers. 1627-1640
• 
  Bastian Bischoff, James D. Currie, Dirk Nowotka:
  Unary Patterns with involution. 1641-1652
• 
  Steven Widmer:
  Permutation Complexity and the Letter Doubling Map. 1653-1676
• 
  Fabio Burderi:
  Full Monoids and Maximal Codes. 1677-1690
• 
  Michaël Cadilhac, Alain Finkel, Pierre McKenzie:
  Bounded Parikh Automata. 1691-1710
• 
  Stefano Crespi-Reghizzi, Pierluigi San Pietro:
  From Regular to Strictly Locally Testable Languages. 1711-1728

Regular Papers

• 
  Shuming Zhou, Lanxiang Chen, Jun-Ming Xu:
  Conditional Fault Diagnosability of Dual-Cubes. 1729-1748
• 
  Juha Honkala:
  Equality Sets of Morphic Word Sequences. 1749-