International Journal of Foundations of Computer Science, Volume 19

Volume 19, Number 1, February 2008

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

Volume 19, Number 2, April 2008

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

Volume 19, Number 3, June 2008

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

Volume 19, Number 4, August 2008

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

Volume 19, Number 5, October 2008

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

Volume 19, Number 6, December 2008

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