Last update:
Wed Sep 27 06:23:29 MDT 2023
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
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
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 . . . . . . . . . . . . . . ??
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
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
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
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
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
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
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
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
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
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
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
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
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
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 . . . . . . . . . . . . . . . ??
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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 $ (3 k + 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
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 . . . . . . . . . . . . . . . . ??
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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 $ a b*c $, with
Applications . . . . . . . . . . . . . . 699
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
Pawe\l 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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
Przemys\law 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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
Guangkui Xu and
Xiwang Cao and
Shanding Xu Several Classes of Quadratic Ternary
Bent, Near-Bent and $2$-Plateaued
Functions . . . . . . . . . . . . . . . 1--18
Rongjia Li and
Chenhui Jin Meet-in-the-Middle Attack on $ 11$-Round
$3$D Block Cipher . . . . . . . . . . . 19--28
Vecdi Aytaç and
Zeynep Nihan Berberler Binding Number and Wheel Related Graphs 29--38
Frank Gurski and
Patrick Gwydion Poullie Interval Routing Schemes for
Circular-Arc Graphs . . . . . . . . . . 30--60
Dongfang Zhou and
Jianxi Fan and
Cheng-Kuan Lin and
Jingya Zhou and
Xi Wang Cycles Embedding in Exchanged Crossed
Cube . . . . . . . . . . . . . . . . . . 61--76
Samir Elouasbi and
Andrzej Pelc Deterministic Rendezvous with Detection
Using Beeps . . . . . . . . . . . . . . 77--97
Xiang Wang and
Fang-Wei Fu Deterministic Construction of Compressed
Sensing Matrices from Codes . . . . . . 99--109
Quentin Bramas and
Sébastien Tixeuil The Random Bit Complexity of Mobile
Robots Scattering . . . . . . . . . . . 111--133
Michael Coons Regular Sequences and the Joint Spectral
Radius . . . . . . . . . . . . . . . . . 135--140
George Lagogiannis Query-Optimal Partially Persistent
B-Trees with Constant Worst-Case Update
Time . . . . . . . . . . . . . . . . . . 141--169
Zuling Chang and
Pinhui Ke and
Yongcheng Zhao Some Enumeration Results on Binary $
2^n$-Periodic Sequences . . . . . . . . 171--184
Stefan Arnold Identifying Generalized Reed--Muller
Codewords by Quantum Queries . . . . . . 185--194
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
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
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
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
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
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
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
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
Michelangelo Bucci and
Gwenaël Richomme Greedy Palindromic Lengths . . . . . . . 331--356
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--375
Parisa Derakhshan and
Walter Hussak Optimal Bounds for Disjoint Hamilton
Cycles in Star Graphs . . . . . . . . . 377--389
Pardis Kavand and
Ali Mohades A Time-Space Trade-off for the Shortest
Path Tree in a Simple Polygon . . . . . 391--402
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--413
Luan Carlos de Sena Monteiro Ozelim and
Andre Luis Brasil Cavalcante The Iota-Delta Function as an
Alternative to Boolean Formalism . . . . 415--423
Masaki Nakanishi Quantum Pushdown Automata with Garbage
Tape . . . . . . . . . . . . . . . . . . 425--446
Zeynep Nihan Berberler and
Esin Yigit Link Vulnerability in Networks . . . . . 447--456
Jarkko Kari and
Alexander Okhotin Preface . . . . . . . . . . . . . . . . 457--459
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--480
Harout Aydinian and
Ferdinando Cicalese and
Christian Deppe and
Vladimir Lebedev A Combinatorial Model of Two-Sided
Search . . . . . . . . . . . . . . . . . 481--504
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--527
Olivier Bournez and
Oleksiy Kurganskyy and
Igor Potapov Reachability Problems for
One-Dimensional Piecewise Affine Maps 529--549
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--569
M. W. Gazda and
T. A. C. Willemse Cooking Your Own Parity Game Preorders
Through Matching Plays . . . . . . . . . 571--590
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--621
Heikki Hyyrö and
Shunsuke Inenaga Dynamic RLE-Compressed Edit Distance
Tables Under General Weighted Cost
Functions . . . . . . . . . . . . . . . 623--645
Dmitry Kravchenko and
Nikolajs Nahimovs and
Alexander Rivosh Grover's Search with Faults on Some
Marked Elements . . . . . . . . . . . . 647--662
Kent Kwee and
Friedrich Otto Nondeterministic Ordered Restarting
Automata . . . . . . . . . . . . . . . . 663--685
Nikolajs Nahimovs and
Alexander Rivosh Quantum Walks on Two-Dimensional Grids
with Multiple Marked Locations . . . . . 687--700
Alexandre Blondin Massé and
Sre\vcko Brlek and
Christophe Reutenauer Preface . . . . . . . . . . . . . . . . 701--704
V. Berthé and
F. Dolce and
F. Durand and
J. Leroy and
D. Perrin Rigidity and Substitutive Dendric Words 705--720
Émilie Charlier and
Wolfgang Steiner Permutations and Negative Beta-Shifts 721--740
Cedric Chauve and
Julien Courtiel and
Yann Ponty Counting, Generating, Analyzing and
Sampling Tree Alignments . . . . . . . . 741--767
Nicolas Bedon Complementation of Branching Automata
for Scattered and Countable $N$-Free
Posets . . . . . . . . . . . . . . . . . 769--799
Luc Dartois and
Ismaël Jecker and
Pierre-Alain Reynier Aperiodic String Transducers . . . . . . 801--824
Jörg Endrullis and
Juhani Karhumäki and
Jan Willem Klop and
Aleksi Saarela Degrees of Infinite Words, Polynomials
and Atoms . . . . . . . . . . . . . . . 825--843
Daniil Gasnikov and
Arseny M. Shur Square-Free Partial Words with Many
Wildcards . . . . . . . . . . . . . . . 846--860
Jozef Jirásek, Jr. and
Galina Jirásková and
Juraj \vSebej Operations on Unambiguous Finite
Automata . . . . . . . . . . . . . . . . 861--876
Andreas Maletti Compositions of Tree-to-Tree Statistical
Machine Translation Models . . . . . . . 877--892
Florin Manea and
Dirk Nowotka and
Markus L. Schmid On the Complexity of Solving Restricted
Word Equations . . . . . . . . . . . . . 893--909
Henryk Michalewski and
Micha\l Skrzypczak On the Strength of Unambiguous Tree
Automata . . . . . . . . . . . . . . . . 911--933
Dirk Nowotka and
Aleksi Saarela One-Variable Word Equations and
Three-Variable Constant-Free Word
Equations . . . . . . . . . . . . . . . 935--950
Ludovic Mignot and
Nadia Ouali-Sebti and
Djelloul Ziadi An Efficient Algorithm for the
Construction of the Equation Tree
Automaton . . . . . . . . . . . . . . . 951--978
Andreas Darmann and
Janosch Döcker and
Britta Dorn The Monotone Satisfiability Problem with
Bounded Variable Appearances . . . . . . 979--993
Shuli Zhao and
Weihua Yang and
Shurong Zhang and
Liqiong Xu Component Edge Connectivity of
Hypercubes . . . . . . . . . . . . . . . 995--1001
Yu-Liang Liu and
Jou-Ming Chang Realizing Exchanged Crossed Cube
Communication Patterns on Linear Array
WDM Optical Networks . . . . . . . . . . 1003--1021
Heewon Chung and
Myungsun Kim Encoding of Rational Numbers and Their
Homomorphic Computations for FHE-Based
Applications . . . . . . . . . . . . . . 1023--1044
Younes Guellouma and
Hadda Cherroun From Tree Automata to Rational Tree
Expressions . . . . . . . . . . . . . . 1045--1062
Caixue Zhou and
Guangyong Gao and
Zongmin Cui and
Zhiqiang Zhao Certificate-Based Generalized Ring
Signcryption Scheme . . . . . . . . . . 1063--1088
Meng Zhang and
Yi Zhang Space-Efficient Representations for
Glushkov Automata . . . . . . . . . . . 1089--1105
Hong Wang and
Jie Guan and
Lin Ding On Equivalence Relations of State
Diagram of Cascade Connection of an LFSR
into an NFSR . . . . . . . . . . . . . . 1107--1117
Ömür Kìvanç Kürkçü and
Ersin Aslan A Comparison Between Edge Neighbor
Rupture Degree and Edge Scattering
Number in Graphs . . . . . . . . . . . . 1119--1142
Minjia Shi and
Hongwei Zhu and
Liqin Qian and
Patrick Solé On Self-Dual Four Circulant Codes . . . 1143--1150
Canan Çiftçi and
Aysun Aytaç Exponential Independence Number of Some
Graphs . . . . . . . . . . . . . . . . . 1151--1164
Wen Chean Teh Compositions of Functions and
Permutations Specified by Minimal
Reaction Systems . . . . . . . . . . . . 1165--1179
Shuo Yan and
Yunyong Zhang and
Binfeng Yan and
Lin Yan and
Jinfeng Kou Data Associations Between Two Hierarchy
Trees . . . . . . . . . . . . . . . . . 1181--1201
Toshihiro Koga Context-Freeness of Parsing Expression
Languages is Undecidable . . . . . . . . 1203--1213
Mehdy Roayaei and
MohammadReza Razzazi Parameterized Complexity of Directed
Steiner Network with Respect to Shared
Vertices and Arcs . . . . . . . . . . . 1215--1230
Mostafa Nouri-Baygi The Computational Complexity of and
Approximation Algorithms for Variants of
the Component Selection Problem . . . . 1231--1245
Costas S. Iliopoulos and
Fatima Vayani Preface . . . . . . . . . . . . . . . . 1247--1248
Kamil Salikhov Improved Compression of DNA Sequencing
Data with Cascading Bloom Filters . . . 1249--1255
Andreas Poyias and
Simon J. Puglisi and
Rajeev Raman m-Bonsai: A Practical Compact Dynamic
Trie . . . . . . . . . . . . . . . . . . 1257--1278
Djamal Belazzougui and
Travis Gagie and
Veli Mäkinen and
Marco Previtali and
Simon J. Puglisi Bidirectional Variable-Order de Bruijn
Graphs . . . . . . . . . . . . . . . . . 1279--1295
Andreia Sofia Teixeira and
Francisco Fernandes and
Alexandre P. Francisco SpliceTAPyR --- An Efficient Method for
Transcriptome Alignment . . . . . . . . 1297--1310
Micha\ll Adamczyk and
Mai Alzamel and
Panagiotis Charalampopoulos and
Jakub Radoszewski Palindromic Decompositions with Gaps and
Errors . . . . . . . . . . . . . . . . . 1311--1329
Carl Barton and
Chang Liu and
Solon P. Pissis Fast Average-Case Pattern Matching on
Weighted Sequences . . . . . . . . . . . 1331--1343
Maryam Abdollahyan and
Greg Elgar and
Fabrizio Smeraldi Identifying Potential Regulatory
Elements by Transcription Factor Binding
Site Alignment Using Partial Order
Graphs . . . . . . . . . . . . . . . . . 1345--1354
Jamie J. Alnasir and
Hugh P. Shanahan Transcriptomics: Quantifying Non-Uniform
Read Distribution Using MapReduce . . . 1355--1372
Anonymous Author Index Volume 29 (2018) . . . . . 1373--1379
Émilie Charlier and
Julien Leroy and
Michel Rigo Preface . . . . . . . . . . . . . . . . 1--4
Simon Beier and
Markus Holzer and
Martin Kutrib Operational State Complexity and
Decidability of Jumping Finite Automata 5--27
Michiel de Bondt and
Henk Don and
Hans Zantema Lower Bounds for Synchronizing Word
Lengths in Partial Automata . . . . . . 29--60
Alice L. L. Gao and
Sergey Kitaev and
Wolfgang Steiner and
Philip B. Zhang On a Greedy Algorithm to Construct
Universal Cycles for Permutations . . . 61--72
Zsolt Gazdag and
Krisztián Tichler and
Erzsébet Csuhaj-Varjú A Pumping Lemma for Permitting
Semi-Conditional Languages . . . . . . . 73--92
François Gonze and
Vladimir V. Gusev and
Raphaël M. Jungers and
Balázs Gerencsér and
Mikhail V. Volkov On the Interplay Between \vCerný and
Babai's Conjectures . . . . . . . . . . 93--114
Michal Hospodár and
Galina Jirásková and
Peter Mlynár\vcik Descriptional Complexity of the Forever
Operator . . . . . . . . . . . . . . . . 115--134
Michal Kunc and
Jan Meitner The Generalized Rank of Trace Languages 135--169
Gwenaël Richomme Characterization of Infinite LSP Words
and Endomorphisms Preserving the LSP
Property . . . . . . . . . . . . . . . . 171--196
Markus Chimani and
Giuseppe Di Battista and
Fabrizio Frati and
Karsten Klein Advances on Testing $c$-Planarity of
Embedded Flat Clustered Graphs . . . . . 197--230
Rolf Klein and
Elmar Langetepe and
Barbara Schwarzwald and
Christos Levcopoulos and
Andrzej Lingas On a Fire Fighter's Problem . . . . . . 231--246
Guangyan Zhou and
Rui Kang On the Lower Bounds of $ (1, 0)$-Super
Solutions for Random $k$-SAT . . . . . . 247--254
Min-Shiang Hwang and
Cheng-Chi Lee and
Shih-Ting Hsu An ElGamal-like Secure Channel Free
Public Key Encryption with Keyword
Search Scheme . . . . . . . . . . . . . 255--273
Xianping Liu and
Yuan Chen and
Yunge Xu and
Zhimin Sun Triple-Cycle Permutations Over Finite
Fields of Characteristic Two . . . . . . 272--292
Ulrike Große and
Christian Knauer and
Fabian Stehn and
Joachim Gudmundsson and
Michiel Smid Fast Algorithms for Diameter-Optimally
Augmenting Paths and Trees . . . . . . . 293--313
Yoann Dieudonné and
Shlomi Dolev and
Franck Petit and
Michael Segal Explicit Communication Among Stigmergic
Robots . . . . . . . . . . . . . . . . . 315--332
Miguel Couceiro and
Miklós Maróti and
Tamás Waldhauser and
László Zádori Computing Version Spaces in the
Qualitative Approach to Multicriteria
Decision Aid . . . . . . . . . . . . . . 333--353
Cristina G. Fernandes and
Carlos E. Ferreira and
Flávio K. Miyazawa and
Yoshiko Wakabayashi Prices of Anarchy of Selfish $2$D Bin
Packing Games . . . . . . . . . . . . . 355--374
Joan Boyar and
Faith Ellen Tight Bounds for Restricted Grid
Scheduling . . . . . . . . . . . . . . . 375--405
Daitao Huang and
Minjia Shi and
Patrick Solé Double Circulant Self-Dual and LCD Codes
Over $ \mathbb {Z}_{p^2} $ . . . . . . . 407--416
Esin Yi\ugit and
Zeynep Nihan Berberler A Note on the Link Residual Closeness of
Graphs Under Join Operation . . . . . . 417--424
Barun Gorain and
Partha Sarathi Mandal Approximation Algorithms for Barrier
Sweep Coverage . . . . . . . . . . . . . 425--448
Olivier Finkel Incompleteness Theorems, Large
Cardinals, and Automata Over Finite
Words . . . . . . . . . . . . . . . . . 449--467
Xiaofang Xu and
Chunlei Li and
Xiangyong Zeng Nonsingular Polynomials from Feedback
Shift Registers . . . . . . . . . . . . 469--487
Yong Yu and
Guomin Yang and
Huaxiong Wang Preface: Special Issue Cryptography and
Provable Security . . . . . . . . . . . 489--492
Yi-Fan Tseng and
Chun-I Fan and
Cheng-Wei Sung On the Anonymity of Multi-Receiver
Identity-Based Encryption Based on
Fujisaki--Okamoto Transformation . . . . 493--509
Fatemeh Rezaeibagha and
Yi Mu and
Shiwei Zhang and
Xiaofen Wang Provably Secure (Broadcast) Homomorphic
Signcryption . . . . . . . . . . . . . . 511--529
Zhongyuan Yao and
Yi Mu ACE with Compact Ciphertext Size and
Decentralized Sanitizers . . . . . . . . 531--549
Wenjuan Meng and
Jianhua Ge and
Tao Jiang Secure Data Deduplication with Reliable
Data Deletion in Cloud . . . . . . . . . 551--570
Zifeng Xu and
Fucai Zhou and
Yuxi Li and
Jian Xu and
Qiang Wang Privacy-Preserving Subgraph Matching
Protocol for Two Parties . . . . . . . . 571--588
Qiqi Lai and
Bo Yang and
Zhe Xia and
Yannan Li and
Yuan Chen and
Zhenlong Li Novel Identity-Based Hash Proof System
with Compact Master Public Key from
Lattices in the Standard Model . . . . . 589--606
Yupu Hu and
Zhizhu Lian and
Jiangshan Chen and
Baocang Wang and
Shanshan Zhang Algebraic Attacks Against Several Weak
Variants of GVW 13 ABE . . . . . . . . . 607--618
Burong Kang and
Xinyu Meng and
Lei Zhang and
Yinxia Sun Nonce-Based Key Agreement Protocol
Against Bad Randomness . . . . . . . . . 619--633
Xiangxin Liu and
Xiaoyuan Yang and
Yiliang Han and
Xu An Wang A Secure and Efficient Code-Based
Signature Scheme . . . . . . . . . . . . 635--645
Libing Wu and
Yubo Zhang and
Kim-Kwang Raymond Choo and
Debiao He Pairing-Free Identity-Based Encryption
with Authorized Equality Test in Online
Social Networks . . . . . . . . . . . . 647--664
Yinghui Zhang and
Menglei Yang and
Dong Zheng and
Tiantian Zhang and
Rui Guo and
Fang Ren Leakage-Resilient Hierarchical
Identity-Based Encryption with Recipient
Anonymity . . . . . . . . . . . . . . . 665--681
Hossein Teimoori Faal A Multiset Version of Even-Odd
Permutations Identity . . . . . . . . . 683--691
Pingshan Li and
Min Xu Fault-Free Hamiltonian Cycles in
Balanced Hypercubes with Conditional
Edge Faults . . . . . . . . . . . . . . 693--717
Ghajendran Poovanandran and
Wen Chean Teh Strong $ (2 \cdot t) $ and Strong $ (3
\cdot t) $ Transformations for Strong
$M$-Equivalence . . . . . . . . . . . . 719--733
Gang Wang and
Min-Yao Niu and
Fang-Wei Fu Bounds on Subspace Codes Based on
Orthogonal Space Over Finite Fields of
Characteristic 2 . . . . . . . . . . . . 735--757
Priti Kumari and
Pramod Kumar Kewat 2-Adic and Linear Complexities of a
Class of Whiteman's Generalized
Cyclotomic Sequences of Order Four . . . 759--779
Aysun Aytaç and
Betül Atay Atakul Exponential Domination Critical and
Stability in Some Graphs . . . . . . . . 781--791
Shu-Li Zhao and
Rong-Xia Hao The Generalized Connectivity of
Bubble-Sort Star Graphs . . . . . . . . 793--809
Hüseyin Tokat and
Alpay Kirlangiç On the Domination Integrity . . . . . . 811--826
Cezar Câmpeanu and
Giovanni Pighizzini Preface . . . . . . . . . . . . . . . . 827--829
Shaull Almagor and
Denis Kuperberg and
Orna Kupferman Sensing as a Complexity Measure . . . . 831--873
Marcella Anselmo and
Dora Giammarresi and
Maria Madonia Sets of Pictures Avoiding Overlaps . . . 875--898
Sabine Broda and
António Machiavelo and
Nelma Moreira and
Rogério Reis On Average Behaviour of Regular
Expressions in Strong Star Normal Form 899--920
Janusz A. Brzozowski and
Sylvie Davies Most Complex Non-Returning Regular
Languages . . . . . . . . . . . . . . . 921--957
Jürgen Dassow Operational Accepting State Complexity:
The Unary and Finite Case . . . . . . . 959--978
Rachel Faran and
Orna Kupferman A Parametrized Analysis of Algorithms on
Hierarchical Graphs . . . . . . . . . . 979--1003
Rudolf Freund and
Vladimir Rogojin and
Sergey Verlan Variants of Networks of Evolutionary
Processors with Polarizations and a
Small Number of Processors . . . . . . . 1005--1027
Kitti Gelle and
Szabolcs Iván Recognizing Union--Find Trees is
NP-Complete, Even Without Rank Info . . 1029--1045
Yo-Sub Han and
Hwee Kim and
Trent A. Rogers and
Shinnosuke Seki Self-Attraction Removal from Oritatami
Systems . . . . . . . . . . . . . . . . 1047--1067
Markus Holzer and
Martin Kutrib One-Time Nondeterministic Computations 1069--1089
Jozef Jirásek, Jr. and
Matú Palmovský and
Juraj \vSebej Kuratowski Algebras Generated by
Prefix-, Suffix-, Factor-, and
Subword-Free Languages Under Star and
Complementation . . . . . . . . . . . . 1091--1115
Galina Jirásková and
Ivana Kraj\vnáková Square on Deterministic, Alternating,
and Boolean Finite Automata . . . . . . 1117--1134
Chris Keeler and
Kai Salomaa Branching Measures and Nearly Acyclic
NFAs . . . . . . . . . . . . . . . . . . 1135--1155
Giovanna J. Lavado and
Luca Prigioniero Concise Representations of Reversible
Automata . . . . . . . . . . . . . . . . 1157--1175
Marina Maslennikova Reset Complexity of Ideal Languages Over
a Binary Alphabet . . . . . . . . . . . 1177--1196
Timothy Ng and
David Rappaport and
Kai Salomaa State Complexity of Suffix Distance . . 1197--1216
Alexander Okhotin and
Kai Salomaa State Complexity of the Quotient
Operation on Input-Driven Pushdown
Automata . . . . . . . . . . . . . . . . 1217--1235
Qiang Fu and
Ruihu Li and
Fangwei Fu and
Yi Rao On the Construction of Binary Optimal
LCD Codes with Short Length . . . . . . 1237--1245
Xirong Xu and
Huifeng Zhang and
Sijia Zhang and
Yuansheng Yang Fault-Tolerant Panconnectivity of
Augmented Cubes $ A Q_n $ . . . . . . . 1247--1278
Sraban Kumar Mohanty and
G. Sajith An Input/Output Efficient Algorithm for
Hessenberg Reduction . . . . . . . . . . 1279--1300
Liqiong Xu and
Shuming Zhou and
Weihua Yang Fault-Tolerant Maximal
Local-Connectivity on Cayley Graphs
Generated by Transpositions . . . . . . 1301--1315
Maksims Dimitrijevs and
Abuzer Yakaryìlmaz Uncountable Realtime Probabilistic
Classes . . . . . . . . . . . . . . . . 1317--1333
Özlem Salehi and
Abuzer Yakaryìlmaz and
A. C. Cem Say New Results on Vector and Homing Vector
Automata . . . . . . . . . . . . . . . . 1335--1361
Lucas Mol and
Narad Rampersad and
Jeffrey Shallit and
Manon Stipulanti Cobham's Theorem and Automaticity . . . 1363--1379
Anonymous Author Index Volume 30 (2019) . . . . . 1381--1387
Erzsébet Csuhaj-Varjú and
Florin Manea Preface --- Special Issue: A Collection
of Papers in Honour of the 60th Birthday
of Victor Mitrana . . . . . . . . . . . 1--6
Fernando Arroyo Montoro and
Sandra Gómez-Canaval and
Karina Jiménez Vega and
Alfonso Ortega de la Puente A Linear Time Solution for $N$-Queens
Problem Using Generalized Networks of
Evolutionary Polarized Processors . . . 7--21
Somnath Bera and
Rodica Ceterchi and
Kalpana Mahalingam and
K. G. Subramanian Parikh $q$-Matrices and $q$-Ambiguous
Words . . . . . . . . . . . . . . . . . 23--36
Henning Bordihn and
György Vaszil Deterministic Lindenmayer Systems with
Dynamic Control of Parallelism . . . . . 37--51
Paolo Bottoni and
Anna Labella and
Grzegorz Rozenberg Networks of Reaction Systems . . . . . . 53--71
Jürgen Dassow and
Bianca Truthe Networks with Evolutionary Processors
and Ideals and Codes as Filters . . . . 73--89
Szilárd Zsolt Fazekas and
Robert Merca\cs and
Daniel Reidenbach On the Prefix--Suffix Duplication
Reduction . . . . . . . . . . . . . . . 91--102
Luis Fernando de Mingo López and
Nuria Gómez Blas and
Angel Luis Castellanos Peñuela and
Juan Bautista Castellanos Peñuela Swarm Intelligence Models: Ant Colony
Systems Applied to BNF Grammars Rule
Derivation . . . . . . . . . . . . . . . 103--116
Andrei P\uaun and
Florin-Daniel B\^\ilb\^\ie Universality of SNQ P Systems Using One
Type of Spikes and Restrictive Rule
Application . . . . . . . . . . . . . . 117--132
José M. Sempere On Compensation Loops in Genomic
Duplications . . . . . . . . . . . . . . 133--142
Cristina T\^\irn\uauc\ua and
José L. Balcázar and
Domingo Gómez-Pérez Closed-Set-Based Discovery of
Representative Association Rules . . . . 143--156
Eunkyung Kim and
Hyang-Sook Lee and
Jeongeun Park Towards Round-Optimal Secure Multiparty
Computations: Multikey FHE Without a CRS 157--174
Yinxia Sun and
Futai Zhang and
Anmin Fu and
Zhe Xia CCA-Secure and Revocable Certificateless
Encryption with Ciphertext Evolution . . 175--191
Jiaxian Lv and
Yi Wang and
Jinshu Su and
Rongmao Chen and
Wenjun Wu Security of Auditing Protocols Against
Subversion Attacks . . . . . . . . . . . 193--206
Hatem M. Bahig and
Dieaa I. Nassr and
Ashraf Bhery and
Abderrahmane Nitaj A Unified Method for Private Exponent
Attacks on RSA Using Lattices . . . . . 207--231
Yuejuan Han and
Lantao You and
Cheng-Kuan Lin and
Jianxi Fan Communication Performance Evaluation of
the Locally Twisted Cube . . . . . . . . 233--252
Tatsuya Akutsu and
Avraham A. Melkman and
Takeyuki Tamura Improved Hardness of Maximum Common
Subgraph Problems on Labeled Graphs of
Bounded Treewidth and Bounded Degree . . 253--273
Manjanna Basappa and
Ramesh K. Jallu and
Gautam K. Das Constrained $k$-Center Problem on a
Convex Polygon . . . . . . . . . . . . . 275--291
Minghui Yang and
Jiejing Wen On the $k$-error Linear Complexity of
Subsequences of $d$-ary Sidel'nikov
Sequences Over Prime Field $ \mathbb
{F}_d$ . . . . . . . . . . . . . . . . . 293--300
Zhongxiao Wang and
Xiangyu Wang and
Tian Tian Constructing de Bruijn Sequences Based
on a New Necessary Condition . . . . . . 301--312
Mei-Mei Gu and
Jou-Ming Chang and
Rong-Xia Hao On Component Connectivity of
Hierarchical Star Networks . . . . . . . 313--326
Gang Wang and
Min-Yao Niu and
Fang-Wei Fu Constructions of $ (r, t)$-LRC Based on
Totally Isotropic Subspaces in
Symplectic Space Over Finite Fields . . 327--339
Hironori Ando and
Satoshi Fujita Tight Bounds on the Upload Capacity to
Enable Two-Hop Delivery in Peer-to-Peer
Video Streaming Systems . . . . . . . . 341--354
Ke Chen and
Adrian Dumitrescu Selection Algorithms with Small Groups 355--369
Jing Li and
Chris Melekian and
Shurong Zuo and
Eddie Cheng Unpaired Many-to-Many Disjoint Path
Covers on Bipartite $k$-Ary $n$-Cube
Networks with Faulty Elements . . . . . 371--383
Subhrangsu Mandal and
Arobinda Gupta Convergecast Tree on Temporal Graphs . . 385--409
Masamichi Kuroda Monomial Generalized Almost Perfect
Nonlinear Functions . . . . . . . . . . 411--419
Sanjib Sadhu and
Sasanka Roy and
Soumen Nandi and
Subhas C. Nandy and
Suchismita Roy Efficient Algorithm for Computing the
Triangle Maximizing the Length of Its
Smallest Side Inside a Convex Polygon 421--443
Shunzhe Zhang and
Dong Li and
Huiqing Liu On $g$-Extra Conditional Diagnosability
of Twisted Hypercubes under MM$^\star $
Model . . . . . . . . . . . . . . . . . 445--459
Markus Hittmeir A Reduction of Integer Factorization to
Modular Tetration . . . . . . . . . . . 461--481
Ahmet Çevik Palindromic Characteristic of Committed
Graphs and Some Model Theoretic
Properties . . . . . . . . . . . . . . . 483--498
Shanding Xu and
Xiwang Cao and
Jiafu Mi and
Chunming Tang Simplified Bounds on FHSs Set and Its
Strictly Optimal Construction . . . . . 499--513
Benedek Nagy On the Membership Problem of Permutation
Grammars --- A Direct Proof of
NP-Completeness . . . . . . . . . . . . 515--525
Grzegorz Madejski and
Andrzej Szepietowski Membership Problem for Two-Dimensional
General Row Jumping Finite Automata . . 527--538
Andreas Kosmatopoulos and
Athanasios Tsakalidis and
Kostas Tsichlas A Space-Optimal Hidden Surface Removal
Algorithm for Iso-Oriented Rectangles 539--549
Juyan Li and
Chunguang Ma and
Zhen Gu Multi-use Deterministic Public Key Proxy
Re-Encryption from Lattices in the
Auxiliary-Input Setting . . . . . . . . 551--567
Lianhua Wang and
Xiaoni Du Linear Complexity of Binary Threshold
Sequences Derived from Generalized
Polynomial Quotient with Prime-Power
Modulus . . . . . . . . . . . . . . . . 569--581
Saeid Alirezazadeh and
Khadijeh Alibabaei Weak Separation Problem for Tree
Languages . . . . . . . . . . . . . . . 583--593
Hayam Alamro and
Mai Alzamel and
Costas S. Iliopoulos and
Solon P. Pissis and
Wing-Kin Sung and
Steven Watts Efficient Identification of $k$-Closed
Strings . . . . . . . . . . . . . . . . 595--610
Ameneh Farhadian Almost Every $n$-Vertex Graph is
Determined by Its $ 3 \log_2 n$-Vertex
Subgraphs . . . . . . . . . . . . . . . 611--619
Zi Jing Chern and
K. G. Subramanian and
Azhana Ahmad and
Wen Chean Teh A New Study of Parikh Matrices
Restricted to Terms . . . . . . . . . . 621--638
Ömer E\ugecio\uglu and
Elif Saygì and
Zülfükar Saygì $k$-Fibonacci Cubes: A Family of
Subgraphs of Fibonacci Cubes . . . . . . 639--661
Shinnosuke Seki Special Issue Developments in Language
Theory 2018 --- Preface . . . . . . . . 663--665
Jason Bell and
Thomas F. Lidbetter and
Jeffrey Shallit Additive Number Theory via Approximation
by Regular Languages . . . . . . . . . . 667--687
Shaull Almagor and
Michaël Cadilhac and
Filip Mazowiecki and
Guillermo A. Pérez Weak Cost Register Automata are Still
Powerful . . . . . . . . . . . . . . . . 689--709
Emmanuel Filiot and
Nicolas Mazzocchi and
Jean-François Raskin A Pattern Logic for Automata with
Outputs . . . . . . . . . . . . . . . . 711--748
Patrick Landwehr and
Christof Löding Projection for Büchi Tree Automata with
Constraints between Siblings . . . . . . 749--775
Costanza Catalano and
Raphaël M. Jungers The Synchronizing Probability Function
for Primitive Sets of Matrices . . . . . 777--803
Simon Beier and
Markus Holzer Decidability of Right One-Way Jumping
Finite Automata . . . . . . . . . . . . 805--825
Lukas Fleischer The Intersection Problem for Finite
Semigroups . . . . . . . . . . . . . . . 827--842
Nicolas Baudru and
Pierre-Alain Reynier From Two-Way Transducers to Regular
Function Expressions . . . . . . . . . . 843--873
Zexia Shi and
Lei Sun and
Fang-Wei Fu New Constructions of Codebooks Nearly
Meeting the Welch Bound . . . . . . . . 875--889
Kalpana Mahalingam and
Ujjwal Kumar Mishra and
Rama Raghavan Watson--Crick Jumping Finite Automata 891--913
Nata\vsa Jonoska and
Masahico Saito and
Hwee Kim and
Brad Mostowski Symbol Separation in Double Occurrence
Words . . . . . . . . . . . . . . . . . 915--928
Tongtong Ding and
Min Xu and
Qiang Zhu The Non-inclusive Diagnosability of
Hypercubes under the MM* Model . . . . . 929--940
Parikshit Saikia and
Sushanta Karmakar Distributed Approximation Algorithms for
Steiner Tree in the CONGESTED CLIQUE . . 941--968
Aysun Asena Kunt and
Zeynep Nihan Berberler Efficient Identification of Node
Importance Based on Agglomeration in
Cycle-Related Networks . . . . . . . . . 969--978
Cezar Câmpeanu Implementations and Applications of
Automata 2018: Preface . . . . . . . . . 979--982
Stavros Konstantinidis and
Nelma Moreira and
Rogério Reis and
Joshua Young Regular Expressions and Transducers Over
Alphabet-Invariant and User-Defined
Labels . . . . . . . . . . . . . . . . . 983--1019
Holger Bock Axelsen and
Martin Kutrib and
Andreas Malcher and
Matthias Wendlandt Boosting Reversible Pushdown and Queue
Machines by Preprocessing . . . . . . . 1021--1049
Samira Attou and
Ludovic Mignot and
Djelloul Ziadi The Bottom-Up Position Tree Automaton
and the Father Automaton . . . . . . . . 1051--1068
Laurent Bartholdi and
Thibault Godin and
Ines Klimann and
Camille Noûs and
Matthieu Picantin A New Hierarchy for Automaton Semigroups 1069--1089
Mikhail V. Berlinkov and
Cyril Nicaud Synchronizing Almost-Group Automata . . 1091--1112
Janusz A. Brzozowski and
Lila Kari and
Bai Li and
Marek Szyku\la State Complexity of Overlap Assembly . . 1113--1132
Bruno Guillon and
Giovanni Pighizzini and
Luca Prigioniero Non-Self-Embedding Grammars,
Constant-Height Pushdown Automata, and
Limited Automata . . . . . . . . . . . . 1133--1157
Michal Hospodár and
Markus Holzer The Ranges of Accepting State
Complexities of Languages Resulting from
Some Operations . . . . . . . . . . . . 1159--1177
Oscar H. Ibarra and
Ian McQuillan Semilinearity of Families of Languages 1179--1198
Anonymous Author Index Volume 31 (2020) . . . . . 1199--1204
Tangliu Wen and
Jie Peng and
Jinyun Xue and
Zhen You and
Lan Song Strict Linearizability and Abstract
Atomicity . . . . . . . . . . . . . . . 1--35
Priscila P. Camargo and
Uéverton S. Souza and
Julliano R. Nascimento Remarks on $k$-Clique, $k$-Independent
Set and $2$-Contamination in
Complementary Prisms . . . . . . . . . . 37--52
Chunfang Li and
Shangwei Lin and
Shengjia Li Hamiltonian Cycle Embeddings in Faulty
Hypercubes Under the Forbidden Faulty
Set Model . . . . . . . . . . . . . . . 53--72
Jinhui Liu and
Yong Yu and
Bo Yang and
Jianwei Jia and
Qiqi Lai Cryptanalysis of Cramer--Shoup Like
Cryptosystems Based on Index
Exchangeable Family . . . . . . . . . . 73--91
Vadim E. Levit and
David Tankus Recognizing Generating Subgraphs
Revisited . . . . . . . . . . . . . . . 93--114
Ting Yao and
Shixin Zhu and
Binbin Pang Triple Cyclic Codes Over $ \mathbb {F} q
+ u \mathbb {F}q $ . . . . . . . . . . . 115--135
Litao Guo and
Mingzu Zhang and
Shaohui Zhai and
Liqiong Xu Relation of Extra Edge Connectivity and
Component Edge Connectivity for Regular
Networks . . . . . . . . . . . . . . . . 137--149
Yuxing Yang Super $ C_k $ and Sub-$ C_k $
Connectivity of $k$-Ary $n$-Cube
Networks . . . . . . . . . . . . . . . . 151--162
Toshihiro Koga A Proof of Parikh's Theorem via
Dickson's Lemma . . . . . . . . . . . . 163--173
Ikhlass Ammar and
Yamen El Touati and
John Mullins and
Moez Yeddes Timed Bounded Verification of Inclusion
Based on Timed Bounded Discretized
Language . . . . . . . . . . . . . . . . 175--202
Thijmen J. P. Krebs A More Reasonable Proof of Cobham's
Theorem . . . . . . . . . . . . . . . . 203--207
Yuichi Asahiro and
Jesper Jansson and
Eiji Miyano and
Hirotaka Ono and
T. P. Sandhya Graph Orientation with Edge
Modifications . . . . . . . . . . . . . 209--233
Yali Lv and
Cheng-Kuan Lin and
Guijuan Wang An Exchanged 3-Ary $n$-Cube
Interconnection Network for Parallel
Computation . . . . . . . . . . . . . . 235--252
Rong Wang and
Xiaoni Du and
Cuiling Fan and
Zhihua Niu Infinite Families of 2-Designs from a
Class of Linear Codes Related to
Dembowski--Ostrom Functions . . . . . . 253--267
Zeynep Nihan Berberler and
Halil \. Ibrahim Yildirim and
Tolga \. Iltüzer and
\. Izzet Tunç Agglomeration-Based Node Importance
Analysis in Wheel-Type Networks . . . . 269--288
Xirong Xu and
Huifeng Zhang and
Ziming Wang and
Qiang Zhang and
Peng Zhang $ (n - 2)$-Fault-Tolerant
Edge-Pancyclicity of Crossed Cubes CQn 289--304
Yihong Wang and
Cheng-Kuan Lin and
Shuming Zhou and
Tao Tian Subgraph-based Strong Menger
Connectivity of Hypercube and Exchanged
Hypercube . . . . . . . . . . . . . . . 305--330
Amit Sharma and
P. Venkata Subba Reddy Algorithmic Aspects of Outer-Independent
Total Roman Domination in Graphs . . . . 331--339
Arturo Carpi and
Flavio D'Alessandro On the Commutative Equivalence of
Algebraic Formal Series and Languages 341--367
Jurek Czyzowicz and
Konstantinos Georgiou and
Evangelos Kranakis and
Danny Krizanc and
Lata Narayanan and
Jaroslav Opatrny and
Sunil Shende Search on a Line by Byzantine Robots . . 369--387
Albert Guan A Lightweight Key Agreement Protocol
with Authentication Capability . . . . . 389--404
Shiying Wang The $r$-Extra Diagnosability of Hyper
Petersen Graphs . . . . . . . . . . . . 405--416
Markus Holzer and
Martin Kutrib Preface . . . . . . . . . . . . . . . . 417--418
Cyril Nicaud and
Pablo Rotondo Random Regular Expression Over Huge
Alphabets . . . . . . . . . . . . . . . 419--438
Jürgen Dassow Further Remarks on the Operational
Nonterminal Complexity . . . . . . . . . 439--453
Stavros Konstantinidis and
Mitja Mastnak and
Juraj \vSebej Zero-Avoiding Transducers, Length
Separable Relations, and the Rational
Asymmetric Partition Problem . . . . . . 455--480
Oscar H. Ibarra and
Ian McQuillan Generalizations of Checking Stack
Automata: Characterizations and
Hierarchies . . . . . . . . . . . . . . 481--508
Sang-Ki Ko and
Yo-Sub Han and
Kai Salomaa Generalizations of Code Languages with
Marginal Errors . . . . . . . . . . . . 509--529
Sang-Ki Ko and
Yo-Sub Han Left is Better Than Right for Reducing
Nondeterminism of NFAs . . . . . . . . . 531--550
Benedek Nagy Union-Freeness Revisited --- Between
Deterministic and Nondeterministic
Union-Free Languages . . . . . . . . . . 551--573
Szilárd Zsolt Fazekas and
Hwee Kim and
Ryuichi Matsuoka and
Reoto Morita and
Shinnosuke Seki Linear Bounds on the Size of
Conformations in Greedy Deterministic
Oritatami . . . . . . . . . . . . . . . 575--596
Daniel Gabric and
Narad Rampersad and
Jeffrey Shallit An Inequality for the Number of Periods
in a Word . . . . . . . . . . . . . . . 597--614
Nata\vsa Jonoska and
Dmytro Savchuk Preface . . . . . . . . . . . . . . . . 615--617
Pamela Fleischmann and
Marie Lejeune and
Florin Manea and
Dirk Nowotka and
Michel Rigo Reconstructing Words from
Right-Bounded-Block Words . . . . . . . 619--640
Lukas Fleischer and
Jeffrey Shallit Recognizing Lexicographically Smallest
Words and Computing Successors in
Regular Languages . . . . . . . . . . . 641--662
Johan Kopra On the Interplay of Direct Topological
Factorizations and Cellular Automata
Dynamics on Beta-Shifts . . . . . . . . 663--683
Lila Kari and
Timothy Ng Descriptional Complexity of Semi-Simple
Splicing Systems . . . . . . . . . . . . 685--711
Augusto Modanese Sublinear-Time Language Recognition and
Decision by One-Dimensional Cellular
Automata . . . . . . . . . . . . . . . . 713--731
Florent Koechlin and
Cyril Nicaud and
Pablo Rotondo Simplifications of Uniform Expressions
Specified by Systems . . . . . . . . . . 733--760
Raphaela Löbel and
Michael Luttenberger and
Helmut Seidl On the Balancedness of Tree-to-Word
Transducers . . . . . . . . . . . . . . 761--783
Collin Bleak Normalish Amenable Subgroups of the R.
Thompson Groups . . . . . . . . . . . . 785--800
Oscar H. Ibarra and
Jozef Jirásek, Jr. and
Ian McQuillan and
Luca Prigioniero Space Complexity of Stack Automata
Models . . . . . . . . . . . . . . . . . 801--823
Oscar H. Ibarra and
Sartaj K. Sahni Announcement . . . . . . . . . . . . . . ??
Rishat Ibrahimov and
Kamil Khadiev and
Kri\vsj\=anis Pr\=usis and
Abuzer Yakaryìlmaz Error-Free Affine, Unitary, and
Probabilistic OBDDs . . . . . . . . . . 827--847
Mengyue Cao and
Tongtong Ding and
Min Xu The $ (n, k)$-Modified-Bubble-Sort
Graph: a Generalized
Modified-Bubble-Sort Graph . . . . . . . 849--860
Jiejing Wen and
Fang-Wei Fu On the Construction of Multiply
Constant-Weight Codes . . . . . . . . . 861--870
Ömer E\ugecio\uglu and
Elif Saygì and
Zülfükar Saygì Alternate Lucas Cubes . . . . . . . . . 871--899
Olivier Finkel Two Effective Properties of $ \omega
$-Rational Functions . . . . . . . . . . 901--920
Bo Zhou and
Zhenan Li and
Haiyan Guo Extremal Results on Vertex and Link
Residual Closeness . . . . . . . . . . . 921--941
Huazhong Lü and
Tingzeng Wu Unpaired Many-to-Many Disjoint Path
Cover of Balanced Hypercubest . . . . . 943--956
Chenli Shen and
Wensong Lin NP-Hardness and Approximation Algorithms
for Iterative Pricing on Social Networks
with Externalities . . . . . . . . . . . 957--979
Boris Ryabko A Pseudo-Random Generator Whose Output
is a Normal Sequence . . . . . . . . . . 981--989
Anonymous Author Index Volume 32 (2021) . . . . . 991--995
P. Renjith and
N. Sadagopan Hamiltonian Cycle in $ K_{1, r} $-Free
Split Graphs --- a Dichotomy . . . . . . 1--32
Pingshan Li and
Rong Liu and
Xianglin Liu The (E)FTSM-(edge) Connectivity of
Cayley Graphs Generated by Transposition
Trees . . . . . . . . . . . . . . . . . 33--43
José Carlos Costa and
Conceição Nogueira and
Maria Lurdes Teixeira The Overlap Gap Between Left-Infinite
and Right-Infinite Words . . . . . . . . 45--53
Yen Hung Chen The Clustered Selected-Internal Steiner
Tree Problem . . . . . . . . . . . . . . 55--66
Hongbin Zhuang and
Wenzhong Guo and
Xiaoyan Li and
Ximeng Liu and
Cheng-Kuan Lin The Component Diagnosability of General
Networks . . . . . . . . . . . . . . . . 67--89
Vasco Boavida De Brito and
José Félix Costa and
Diogo Poças The Power of Machines That Control
Experiments . . . . . . . . . . . . . . 91--118
Tien Tran and
Dung T. Huynh Symmetric Connectivity in Wireless
Sensor Networks with $ \pi / 3 $
Directional Antennas . . . . . . . . . . 119--140
Chih-Yuan Lin and
Jia-Jie Liu and
Yue-Li Wang and
William Chung-Kung Yen and
Chiun-Chieh Hsu The Outer-Paired Domination of Graphs 141--148
Hongyu Zhou and
Xinmin Hou Strongly Connected Orientation with
Minimum Lexicographic Order of Indegrees 149--153
Dongqin Cheng Extra Connectivity and Structure
Connectivity of 2-Dimensional Torus
Networks . . . . . . . . . . . . . . . . 155--173
Erzsébet Csuhaj-Varjú and
Pál Dömösi and
György Vaszil Preface . . . . . . . . . . . . . . . . 175--178
Artiom Alhazov and
Rudolf Freund and
Sergiu Ivanov and
Sergey Verlan Tissue P Systems with Vesicles of
Multisets . . . . . . . . . . . . . . . 179--202
Francine Blanchet-Sadri and
Kun Chen and
Kenneth Hawes Dyck Words, Lattice Paths, and Abelian
Borders . . . . . . . . . . . . . . . . 203--226
Manfred Droste and
Zoltán Ésik and
Werner Kuich The Triple-Pair Construction for
Weighted $ \omega $-Pushdown Automata 227--246
Kitti Gelle and
Szabolcs Iván Descriptive Complexity of Reversible
Languages Having Finitely Many Reduced
Automata . . . . . . . . . . . . . . . . 247--262
Bruno Guillon and
Giovanna J. Lavado and
Giovanni Pighizzini and
Luca Prigioniero Weakly and Strongly Irreversible Regular
Languages . . . . . . . . . . . . . . . 263--284
Markus Holzer and
Martin Kutrib and
Andreas Malcher and
Matthias Wendlandt Input-Driven Double-Head Pushdown
Automata . . . . . . . . . . . . . . . . 285--311
Laurette Marais and
Lynette van Zijl Descriptional Complexity of Non-Unary
Self-Verifying Symmetric Difference
Automata . . . . . . . . . . . . . . . . 313--333
Jakub Marti\vsko and
Alexander Meduna and
Zbyn\vek K\vrivka CD Grammar Systems with Two Propagating
Scattered Context Components
Characterize the Family of Context
Sensitive Languages . . . . . . . . . . 335--348
Masaki Nakanishi and
Kamil Khadiev and
Krisjanis Prusis and
Jevgenijs Vihrovs and
Abuzer Yakaryìlmaz Exact Affine Counter Automata . . . . . 349--370
Martin Plátek and
Friedrich Otto and
Franti\vsek Mráz One-Way Restarting Automata and Their
Sensitivities . . . . . . . . . . . . . 371--387
Kalpana Mahalingam and
Palak Pandoh HV-Palindromes in Two-Dimensional Words 389--409
Yijie Han and
Xin He More Efficient Parallel Integer Sorting 411--427
Halil \. Ibrahim Yildirim and
Zeynep Nihan Berberler Isolated Rupture in Thorny Networks . . 429--438
Kai Feng Subnetwork Preclusion of $ (n, k) $-Star
Networks . . . . . . . . . . . . . . . . 439--451
Sunil Kumar and
Harshdeep Singh and
Gaurav Mittal A Novel Approach Towards Degree and
Walsh-Transform of Boolean Functions . . 453--479
Jia-Bao Liu and
Muhammad Javaid and
Mohammad Reza Farahani Preface . . . . . . . . . . . . . . . . 481--487
Konduru Upendra Raju and
Amutha Prabha Nagarajan A Steganography Embedding Method Based
on CDF-DWT Technique for Reversible Data
Hiding Application Using Elgamal
Algorithm . . . . . . . . . . . . . . . 489--512
Salisu Ibrahim Mathematical Modelling and Computational
Analysis of Covid-19 Epidemic in Erbil
Kurdistan Using Modified Lagrange
Interpolating Polynomial . . . . . . . . 513--529
Aldosary Saad and
Abdullah Alharbi Securing Smart City Services in
Cyber-Physical Systems Using the
Computation Annealed Selection Process 531--557
S. Raghavendra and
A. Harshavardhan and
S. Neelakandan and
R. Partheepan and
Ranjan Walia and
V. Chandra Shekhar Rao Multilayer Stacked Probabilistic Belief
Network-Based Brain Tumor Segmentation
and Classification . . . . . . . . . . . 559--582
Changwei Liu and
Kexin Wang and
Aman Wu Management and Monitoring of
Multi-Behavior Recommendation Systems
Using Graph Convolutional Neural
Networks . . . . . . . . . . . . . . . . 583--601
Kun Li and
Yanjun Chen Fuzzy Clustering-Based Financial Data
Mining System Analysis and Design . . . 603--624
R. Priya and
N. Sivakumar Improving the Quality of Service (QoS)
and Resource Allocation in Vehicular
Platoon Using Meta-Heuristic
Optimization Algorithm . . . . . . . . . 625--647
Feng Shi and
Xiaomei Hu Fuzzy Dynamic Obstacle Avoidance
Algorithm for Basketball Robot Based on
Multi-Sensor Data Fusion Technology . . 649--666
Muhammad Faisal Nadeem and
Waqar Ali and
Hafiz Muhammad Afzal Siddiqui Locating Number of Biswapped Networks 667--690
Qi Zhang and
Guang Wen and
Zhixin Chen and
Qin Zhou and
Guoqi Xiang and
Guangchun Yang and
Xuegang Zhang Sensitivity Analysis Contact Reliability
of VH-CATT Cylindrical Gear and Its
Reliability with Material Strength
Degradation . . . . . . . . . . . . . . 691--716
Yangfeng Zheng and
Zheng Shao and
Zhanghao Gao and
Mingming Deng and
Xuesong Zhai Optimizing the Online Learners' Verbal
Intention Classification Efficiency
Based on the Multi-Head Attention
Mechanism Algorithm . . . . . . . . . . 717--733
Zeqiang Ni and
Lei Zhang and
Junqing He Recomputation of Public Capital Based on
PIM and the Effect on China Regional
Economic Growth . . . . . . . . . . . . 735--753
Jiajing Zhang and
Tingting Zhang and
Jinlan Chen Sentiment Analysis of Chinese Reviews
Based on BiTCN-Attention Model . . . . . 755--770
Jian Wu and
Chaoyu Yang Graph Convolutional Network-Guided Mine
Gas Concentration Predictor . . . . . . 771--785
Baixiu Ni and
Ying Wang and
Jingfu Huang and
Guocheng Li Hybrid Enhanced Binary Honey Badger
Algorithm with Quadratic Programming for
Cardinality Constrained Portfolio
Optimization . . . . . . . . . . . . . . 787--803
Ziyi Sun and
Jing Zhang Research on Prediction of Housing Prices
Based on GA-PSO-BP Neural Network Model:
Evidence from Chongqing, China . . . . . 805--818
Liting Yu and
Dongyan Liu and
Nairu Xu Special Aquatic Products Supply Chain
Coordination Considering Bilateral Green
Input in the Context of High-Quality
Development . . . . . . . . . . . . . . 819--844
Wei Zhang and
Zhiguang Li Identifying the Configurations to
Operating Efficiency in China's Life
Insurance Industry Using Fuzzy-Set
Qualitative Comparative Analysis . . . . 845--865
Li-Jun Xu and
Shou-Yu Wei and
Xiao-Qing Lu and
Ze-Hua He and
Jia-Ming Zhu Algorithm Design for Asset Trading Under
Multiple Factors . . . . . . . . . . . . 867--886
Bin Yang and
Jie Wang An Improved Helmet Detection Algorithm
Based on YOLO V4 . . . . . . . . . . . . 887--902
Kai Xie and
Zijian Wei and
Kang Yin and
Songsong Li and
Xinyan Yao and
Xiaoyu Zhou Structural Synthesis of PLC Program for
Real-Time Specification Patterns . . . . 903--929
Salman Mukhtar and
Muhammad Salman and
Ayse Dilek Maden and
Masood Ur Rehman Metric Properties of Non-Commuting Graph
Associated to Two Groups . . . . . . . . 931--952
Havva Kìrgìz and
A. Dilek Maden New Bounds for Some Topological Indices 953--965
Branislav Rovan and
András Varga Finite Approximations and Similarity of
Languages . . . . . . . . . . . . . . . 967--1003
Xiaoqing Liu and
Shuming Zhou and
Hong Zhang and
Baohua Niu The Component (Edge) Connectivity of
Round Matching Composition Networks . . 1005--1018
Zhengqin Yu and
Shuming Zhou and
Hong Zhang Fault-Tolerant Strong Menger (Edge)
Connectivity of DCC Linear Congruential
Graphs . . . . . . . . . . . . . . . . . 1019--1032
Chavdar Dangalchev Additional Closeness of Cycle Graphs . . 1033--1052
Anonymous Author Index Volume 33 (2022) . . . . . 1053--1058
Mingzu Zhang and
Hongxi Liu and
Pingping Li Embedded Edge-Connectivity Reliability
Evaluation of Augmented Hypercube
Interconnection Networks . . . . . . . . 1--10
Vecdi Aytaç and
Tufan Turacì Analysis of Vulnerability of Some
Transformation Networks . . . . . . . . 11--24
Subhash Bhagat and
Abhinav Chakraborty and
Bibhuti Das and
Krishnendu Mukhopadhyaya Optimal Gathering Over Weber Meeting
Nodes in Infinite Grid . . . . . . . . . 25--49
Loris Marchal and
Samuel McCauley and
Bertrand Simon and
Frédéric Vivien Minimizing I/Os in Out-of-Core Task Tree
Scheduling . . . . . . . . . . . . . . . 51--80
Nelma Moreira and
Rogéxrio Reis Special Issue: 25th International
Conference on Developments in Language
Theory (DLT 2021) --- Preface . . . . . 81--83
Stijn Cambie and
Michiel de Bondt and
Henk Don Extremal Binary PFAs with Small Number
of States . . . . . . . . . . . . . . . 85--115
Luc Edixhoven and
Sung-Shik Jongmans Balanced-by-Construction Regular and $
\omega $-Regular Languages . . . . . . . 117--144
Fabian Frei and
Juraj Hromkovi\vc and
Rastislav Královi\vc and
Richard Královi\vc Two-Way Non-Uniform Finite Automata . . 145--162
Vesa Halava and
Tero Harju and
Reino Niskanen and
Igor Potapov Integer Weighted Automata on Infinite
Words . . . . . . . . . . . . . . . . . 163--182
Viktor Henriksson and
Manfred Kufleitner Forbidden Patterns for FO$^2$
Alternation Over Finite and Infinite
Words . . . . . . . . . . . . . . . . . 183--224
Martin Kutrib and
Uwe Meyer Reversible Top-Down Syntax Analysis . . 225--251
Sebastian Maneth and
Helmut Seidl and
Martin Vu Definability Results for Top-Down Tree
Transducers . . . . . . . . . . . . . . 253--287
Mikhail Mrykhin and
Alexander Okhotin The Hardest LL($k$) Language . . . . . . 289--319
Julian Pape-Lange Tight Upper Bounds on Distinct Maximal
(Sub-)Repetitions in Highly Compressible
Strings . . . . . . . . . . . . . . . . 321--345
Lan Lin and
Yixun Lin Graph Bipartization Problem with
Applications to Via Minimization in VLSI
Design . . . . . . . . . . . . . . . . . 347--361
Halil \. Ibrahim Yildirim and
Zeynep Nihan Berberler Isolated Rupture in Composite Networks 363--371
Zhiyao Yang and
Pinhui Ke and
Zhixiong Chen and
Chenhuang Wu Results on the Gowers U2 Norm of
Generalized Boolean Functions . . . . . 373--393
Hong Zhang and
Shuming Zhou and
Qifan Zhang Component Connectivity of Alternating
Group Networks and Godan Graphs . . . . 395--410
Zsolt Gazdag and
Sándor Vágvölgyi The Component Hierarchy of Chain-Free
Cooperating Distributed Regular Tree
Grammars Revisited . . . . . . . . . . . 411--427
Jung-Heum Park Paired 3-Disjoint Path Covers in
Bipartite Torus-Like Graphs with Edge
Faults . . . . . . . . . . . . . . . . . 429--441
Meijie Ma and
Chaoming Guo and
and Xiang-Jun Li Strong Menger Connectivity of Folded
Hypercubes with Faulty Subcube . . . . . 443--451
Jesper Jansson and
Christos Levcopoulos and
and Andrzej Lingas Online and Approximate Network
Construction from Bounded Connectivity
Constraints . . . . . . . . . . . . . . 453--468
Hong Zhang and
Shuming Zhou and
and Baohua Niu Fault-Tolerance of Star Graph Based on
Subgraph Fault Pattern . . . . . . . . . 469--485
Tetsuo Asano Transportation Problem Allowing Sending
and Bringing Back . . . . . . . . . . . 487--505
Tayssir Touili and
Xin Ye Reachability Analysis of Self Modifying
Code . . . . . . . . . . . . . . . . . . 507--536
Manfred Droste and
George Rahonis and
and Arto Salomaa Special Issue: International Colloquium:
Recent Advances of Quantitative Models
in Computer Science (RAQM 2021) ---
Preface . . . . . . . . . . . . . . . . 537--538
Malte Blattmann and
Andreas Maletti Compositions with Constant Weighted
Extended Tree Transducers . . . . . . . 539--558
Maria Pittou and
George Rahonis Modelling Uncertainty in Architectures
of Parametric Component-Based Systems 559--601
Paulina Paraponiari Fuzzy Propositional Configuration Logics 603--631
Manfred Droste and
Zoltán Fülöp and
and Dávid Kószó Decidability Boundaries for the
Finite-Image Property of Weighted Finite
Automata . . . . . . . . . . . . . . . . 633--653
Eugenija A. Bondar and
David Casas and
and Mikhail V. Volkov Completely Reachable Automata: an
Interplay Between Automata, Graphs, and
Trees . . . . . . . . . . . . . . . . . 655--690