This special issue collects substantially extended versions of some of the papers presented to LATA 2011 (5th International Conference on Language and Automata Theory and Applications), held in Tarragona, Spain, on May 26-31, 2011. The conference received 91 submissions, 36 papers were accepted for presentation, and finally only 10 papers were selected for this volume.
The LATA conference series has a broad scope, hence the variety of papers included here. Let us briefly introduce the main achievements in each of them:
Dana Angluin, James Aspnes, and Raonne Barbosa Vargas, Mutation systems Citation1
Subject: Mutation systems.
Mutation systems to model the evolution of a string are proposed. Point mutations and a fitness function are defined to this purpose. Connections with finite-state machines and cellular automata are investigated as well as the possibility of universal computation in this new framework.
Witold Charatonik and Agata Chorowska, Parameterized complexity of basic decision problems for tree automata Citation2
Subject: Tree automata.
The parameterized complexity of several decision problems for some classes of automata on finite trees is studied. Some of the results are somehow unexpected and leave a lot of room for further research on open problems that appear to be hard.
Émilie Charlier, Mike Domaratzki, Tero Harju, and Jeffrey Shallit, Composition and orbits of language operations: finiteness and upper bounds Citation3
Subject: Language operations.
This paper generalizes previous results about several operations on languages and compositions on them. It is proved that the number of equivalence classes of the operations considered is finite, hence the orbit of any language is finite and bounded.
Ruth Corran, Michael Hoffmann, Dietrich Kuske, and Richard M. Thomas, On the automaticity of singular Artin monoids of finite type Citation4
Subject: Finite monoids.
It is proved that singular Artin monoids of finite type are automatic. This involves the use of techniques of group theory as well as the overcome of significant obstacles posed by asynchronicity.
Martin Huschenbett, Models for quantitative distributed systems and multi-valued logics Citation5
Subject: Models for distributed systems.
Weighted cellular automata to model concurrency are investigated and particular attention is paid to their expressiveness in comparison with monadic second-order logic. This sort of work has evident relevance for model checking.
Mirosław Kowaluka, Andrzej Lingas and Eva-Marta Lundell, Unique subgraphs are not easier to find Citation6
Subject: Graph algorithms.
The problem of detecting subgraphs or induced subgraphs of a host graph that are isomorphic to a given pattern graph is dealt with. It is concluded that such a problem is computationally hard.
Benedek Nagy and Friedrich Otto, Globally deterministic CD-systems of stateless R-automata with window size 1 Citation7
Subject: Restarting automata.
The accepting power of two classes of deterministic cooperating-distributed systems of stateless deterministic restarting automata with window size 1 is studied.
Alberto Policriti and Alexandru I. Tomescu, Well-quasi-ordering hereditarily finite sets Citation8
Subject: Directed graphs.
This paper is a first step in studying containment relations and well-quasi-orderings on digraphs representing various classes of sets. Previous results concerning hereditarily finite well-founded sets are strengthened and generalized by studying some digraph containment relations between membership digraphs and subclasses of them, well-quasi-ordered by such relations.
Daniel Reidenbach and Markus L. Schmid, Finding shuffle words that represent optimal scheduling of shared memory access Citation9
Subject: Shuffle words.
The problem of computing a shuffle word for given input words over an alphabet that is optimal with respect to the maximum number of different symbols that parenthesize any position in the word is investigated. Its complexity is discussed, and an algorithm is presented.
Arto Salomaa, Kai Salomaa, and Sheng Yu, Undecidability of state complexity Citation10
Subject: Descriptional complexity of language operations.
The state complexity of compositions of regularity-preserving language operations is considered. It is established that determining the state complexity of an operation composed just from intersections and marked concatenations is undecidable.
The simple list of keywords utilized by the authors gives a clear indication of the topics addressed as well as good evidence of the breadth in scope of this special issue: asynchronous automata; automatic groups; automatic monoids; automaton; cellular automata; classical tree automata; combined operations; complement; cooperating distributed system; Coxeter graphs; determinism; deterministic finite automaton; deterministic finite-state acceptor with translucent letters; distributed systems; extensional digraph; finite automata; formal language; graph algorithms; hereditarily finite set; hyperset; induced subgraph isomorphism; Kleene closure; k-testable languages; language class; marked concatenation; memory access scheduling; multi-valued logics; mutation systems; normal forms; orbit; parameterized complexity theory; point mutations; positive singular Artin monoids; rational relations; rational trace language; restarting automaton; reversible computation; rigid tree automata; shuffle; singular Artin monoids; state complexity; string algorithms; subdivision; subgraph; subgraph isomorphism; t-DAG automata; time complexity; traces; transducers; tree automata with global equality and disequality; undecidability; unique subgraph occurrence; weighted automata; well-quasi-order.
We hope researchers will find the content of this special issue interesting, of high quality and encouraging of future work.
Let us finally thank the authors, the referees, the IJCM editor-in-chief, and Taylor & Francis staff for making this special issue possible.
May 2013
References
- Angluin , D. , Aspnes , J. and Barbosa Vargas , R. 2013 . Mutation systems . Int. J. Comput. Math. , 90 ( 6 ) : 1132 – 1149 .
- Charatonik , W. and Chorowska , A. 2013 . Parameterized complexity of basic decision problems for tree automata . Int. J. Comput. Math. , 90 ( 6 ) : 1150 – 1170 .
- Charlier , É. , Domaratzki , M. , Harju , T. and Shallit , J. 2013 . Composition and orbits of language operations: finiteness and upper bounds . Int. J. Comput. Math. , 90 ( 6 ) : 1171 – 1196 .
- Corran , R. , Hoffmann , M. , Kuske , D. and Thomas , R. M. 2013 . On the automaticity of singular Artin monoids of finite type . Int. J. Comput. Math. , 90 ( 6 ) : 1197 – 1222 .
- Huschenbett , M. 2013 . Models for quantitative distributed systems and multi-valued logics . Int. J. Comput. Math. , 90 ( 6 ) : 1223 – 1246 .
- Kowaluk , M. , Lingas , A. and Lundell , E.-M. 2013 . Unique subgraphs are not easier to find . Int. J. Comput. Math. , 90 ( 6 ) : 1247 – 1253 .
- Nagy , B. and Otto , F. 2013 . Globally deterministic CD-systems of stateless R-automata with window size 1 . Int. J. Comput. Math. , 90 ( 6 ) : 1254 – 1277 .
- Policriti , A. and Tomescu , A. I. 2013 . Well-quasi-ordering hereditarily finite sets . Int. J. Comput. Math. , 90 ( 6 ) : 1278 – 1291 .
- Reidenbach , D. and Schmid , M. L. 2013 . Finding shuffle words that represent optimal scheduling of shared memory access . Int. J. Comput. Math. , 90 ( 6 ) : 1292 – 1309 .
- Salomaa , A. , Salomaa , K. and Yu , S. 2013 . Undecidability of state complexity . Int. J. Comput. Math. , 90 ( 6 ) : 1310 – 1320 .