Special Issue Dedicated to Jetty Kleijn on the Occasion of

This special issue is dedicated to Giancarlo Mauri on the occasion of his 70th birthday.Giancarlo is a well-known prolific

Reaction system is a model of interactive computations which was motivated by the functioning of the living cell. It is an idealized mathematical model, also because it abstracts from the complex nature of the physical systems where only partial, incomplete information is available (e.g., about the ir states). The framework of rough sets was developed to deal with such incomplete information. In this paper we establish a connection between reaction systems and rough sets. This is done in a somewhat broader perspective of the relationship between “pure” mathematical models and “realistic models” that take into account the limitation of perceiving physical reality.

This special issue celebrates the 85th birthday of Andrzej Ehrenfeucht, an iconic scientist. He has contributed many seminal results and opened new research directions in mathematical logic, theoretical computer science, and natural computing. His research is characterized by originality and elegance -he is famous for discovering unique approaches to and elegant structures within problems he works on.

International audience

on the occasion of his 65th birthday.

Image reconstruction from collected data is an inverse problem that frequently appears in several applications.It is encountered in various research areas, such as biomedical imaging, reconstruction algorithms, image processing, stereology, and mathematical morphology.It turns out that the same methodologies and strategies can be frequently adapted to different frames and disciplines.One of the main tools is the Radon Transform, and its inversion formula which is used, in particular, in many problems of tomographic research where the information is usually acquired by means of data obtained from X-rays projections.Since the 1990s specialistic meetings have been organized devoted to both theoretical advances and practical applications of Tomography.Among them, the Meeting on Tomography and Applications, now in its 6th edition, succeeds in attracting some of the main researchers involved in the various aspects of Tomography.The presentations consists of technical contributions as well as talks outlining the state-ofthe-arts and proposing future research directions.The main purpose of this edition of the meeting was to focus on connections and overlaps among Discrete Tomography, Geometric Tomography, and Computerized Tomography, with a special focus on applications.This special issue consists of invited papers.Some of them have been presented at the 6th Meeting on Tomography and Applications held at Politecnico di Milano on April 26-27, 2012, but in order to provide a better perspective on current research also additional papers were invited.The papers went through a thorough refereeing process and the accepted papers are presented in this issue.The reminder of this preface consists of two parts.In the first part we provide brief overviews for each of the papers from this issue.In the second part we provide summaries for talks presented at the 6th Meeting on Tomography and Applications.In this way the reader can get a better insight into the nature of the meeting and hence also into the current research in the area covered by this special issue.This paper exploits the possibilities of using the Discrete Algebraic Reconstruction Technique (DART) that performs extremely well for the discrete tomography reconstruction problem, with the data obtained from the Magnetic Resonance imaging (MRI).The MRI is a well-known technique that uses a magnetic field to produce images of various structures like organs, soft tissues, bone, or biological samples.The actual M RI reconstruction methods either use fast inversion Fourier transform techniques from a huge number of measurements, or apply compressed sensing methods that use few measurements, but must be used under some a priori assumptions.In this paper a new type of a prior knowledge about the homogeneity of the unknown structure (that reflects the poorness of grey levels in the MRI image) is exploited.The authors adapt the DART technique to this scenario, they carry on experiments on MRI data obtaining extremely accurate reconstructions, and they prove that DART outperforms a commonly used reconstruction method.• K.J. Batenburg, W. Fortes, and R. Tijdeman, Approximate discrete reconstruction algorithm.The paper presents an approximate algorithm to reconstruct images with a small number of grey levels from projections, i.e., quantitative data on the number of pixels, weighted with respect to their grey level, along a finite set of directions.This problem is one of the most studied in the field of Discrete Tomography, and a range of reconstruction algorithms have been proposed in the literature with most of them assuming the presence of only two grey levels.However, since the general problem is not polynomially solvable, all these algorithms do not guarantee the exact reconstruction of the image, and moreover the error, i.e., the misclassified pixels, depends on the particular problem instance and so it cannot be bounded sharply.The authors approach the reconstruction problem by means of a mixed technique that relies both on algebraic methods for the solution of linear equation systems and on combinatorics.The algorithm they define requires that the grey levels of the image belong to a fixed set of real values.The reconstructed solution is really close to the unknown starting image, and the difference between the given projections and the projections of this reconstructed image is bounded.A remarkable fact is that this bound is explicitly computable, and moreover it is independent of the image size and scales linearly with the number of projection angles.• R.A. Fiorini, and G. Laguteta, Discrete Tomography Data Footprint Reduction by Information Conservation.The authors deal with the problem concerning the storage of a huge amount of collected data.One of the aims of Discrete Tomography is the reconstruction of nanocrystals at atomic resolution.This is carried out through suitable algorithms which allow a fast and accurate reconstruction from a limited number of projection images.These algorithms produce a large amount of available data, and one of the underlying problems is their storage in a smaller space.The usually employed processes to achieve this are known as Data Footprint Reduction (DFR), including, for instance, deduplication and lossless compression.However, they fail to match high end data imaging application requirements, so that no contemporary lossless compression/decompression algorithm is completely satisfactory.In this paper a proposal is presented for an original and convenient algorithm for numeric images that offers both Arbitrary Bit Depth (ABD) resolution and Dynamic Upscale Regeneration (DUR), with full information conservation, at no extra computational cost.An original application example is presented and critically discussed.

This paper continues an investigation into bridging two research areas concerned with natural computing: membrane computing and reaction systems. More specifically, the paper considers a transfer of two assumptions/axioms of reaction systems, non-permanency and the threshold assumption, into the framework of membrane computing. It is proved that: (1) spiking neural P systems with non-permanency of spikes assumption characterize the semilinear sets of numbers, and (2) symport/antiport P systems with threshold assumption (translated as ω multiplicity of objects) can solve SAT in polynomial time. Also, several open research problems are stated.

This special issue celebrates the 60th birthday of Professor Tero Harju (the actual birthday date is June 28, 2012).It consists of 20 original contributions written by his friends, colleagues and former students.The topics of this issue cover a broad spectrum of theoretical computer science and discrete mathematics, from automata theory via combinatorics on words to biomodelling -this coverage ref ects an impressive range of scientif c interest and research contributions by Tero.He made impressive scientif c contributions to many research areas including formal languages and automata theory, combinatorics on words, semigroup theory, computability theory, DNA computing, and biomodelling.Many of his results belong to highlights of those areas.His contributions to science are twofold: he solved many very challenging technical problems and he was also instrumental in shaping new research directions.One can mention here his solutions of famous open problems such as the equivalence problem of multitape f nite automata and Duval's conjecture on periodicity of words as examples of the former, and his work on regularity of splicing systems and the work on a formal framework for gene assembly in cilliates as examples of the latter.Tero is a Full Professor in the department of mathematics of University of Turku, Finland, and a member of Finnish Academy of Sciences.Although he stayed at a number of scientif c institutions abroad, his real nest is the combination of the department in Turku and his home in Lieto, not far from Turku.Still, thanks to the Internet and many travels to conferences where he presents his results, he has an impressive number of co-authors, mostly in Europe and North America.All four of us have extensive experience of working with Tero.The working sessions are long and intense, but they are often punctuated by bursts of laughing when Tero utters one of his one-liners: he has a wonderful sense of dry intellectual humor.Another characteristic feature of Tero is his remarkable modesty -he just lets his results speak for him.No wonder that Tero is popular in the scientif c community -the response to our call for papers to this special issue was enthusiastic indeed.

Ciliates have developed a unique nuclear dualism, having two nuclei of different functionality: the germline micronucleus and the somatic macronucleus. The way that ciliates assemble the macronuclear genes after cell mating constitutes one of the most intricate DNA processings in living organisms. This processing is also very interesting from the computational point of view. In this paper, we investigate the operations of loop excision and hairpin excision/reinsertion used in the assembly process. In particular, we consider three levels of formalization of this process, culminating in graph reduction systems.

A membrane computing system (also called P system) consists of computing cells which are organized hierarchically by the inclusion relation: cells may include cells, which again may include cells, etc. Each cell is enclosed by its membrane. Each cell is an independent computing agent with its own computing program, which produces objects. The interaction between cells consists of the exchange of objects through membranes. The output of a computation is a partially ordered set of objects which leave the system through its external membrane. The fundamental properties of computations in such P systems with external output are investigated. These include the computing power, normal forms, and basic decision problems.

The potential for cross-fertilization between the fields of DNA based computing and evolutionary computation is outlined both from a principal point of view and by means of an experimental investigation concerning the NP-hard maximum clique problem. A simple evolutionary approach to maximum clique is introduced and the hypothesis is tested whether the increase in population size possible by realizing evolutionary computation with DNA yields the expected improvement in solution quality. Results obtained for a limited range of population sizes up to 10/sup 4/ indicate that the hypothesis holds for about two-third of the investigated problem instances (which were taken from the DIMACS library).

We consider structured processes that compute changes of valuation functions defined for functional structures, where both the domain and range of each function are the set of sequences over a carrier set. By introducing consistency conditions and certain restrictions on the underlying graph, we obtain a determinism result guaranteeing that for each valuation the structured process computes a unique change of context, i.e., the process defines a partial function on the set of valuations. Employing the determinism theorem we obtain a decomposition result for interpreted trees using a structured process where the edges represent computations in the subtrees.

For a finite set D of nodes let E2(D)={(x, y)[mid ] x, y∈D, x≠y}. We define an inversive Δ2-structure g as a function g[ratio ]E2(D)→Δ into a given group Δ satisfying the property g(x, y)= g(y, x)−1 for all (x, y)∈E2(D). For each function (selector) σ[ratio ]D→Δ there is a corresponding inversive Δ2-structure gσ defined by gσ(x, y)=σ(x)·g (x, y)·σ(y)−1. A function η mapping each g into the group Δ is called an invariant if η(gσ)=η(g) for all g and σ. We study the group of free invariants η of inversive Δ2-structures, where η is defined by a word from the free monoid with involution generated by the set E2(D). In particular, if Δ is abelian, the group of free invariants is generated by triangle words of the form (x0, x1)(x1, x2)(x2, x0).

Continuing the work begun in [14], we consider contextual grammars (as introduced in [6] with linguistic motivation) with parallel derivations, in which the whole current string participates to a derivation step in the sense that it is splitted into substrings to which contexts are adjoined in a parallel manner. The generative power of such grammars is investigated, when the parallelism is total or partial, and when the selection of contexts is limited to strings in sets of a given type (finite, regular etc.) Then we consider the languages consisting of strings which cannot be further derived (we call them blocking languages). Some open problems are also formulated.

We introduce terminally coded (TC) grammars, which generalize parenthesis grammars in the sense that from each word ω generated by a TC grammar we can recover the unlabeled tree t underlying its derivation tree(s). More precisely, there is a length-preserving homomorphism that maps ω to an encoding of t. Basic properties of TC grammars are established. For backwards deterministic TC grammars we give a shift-reduce precedence parsing method without look-ahead, which implies that TC languages can be recognized in linear time. The class of TC languages contains all parenthesis languages, and is contained in the classes of simple precedence languages and NTS languages.

The notion of a square system is introduced and investigated - it is based on a quaternary relation satisfying certain symmetry conditions. The theory of square systems provides a unifying framework for studying decompositions of systems based on hie

A subset X of a 2-structure (a reversible edge-colored directed graph) g is a clan, if X cannot be distinguished by colors from outside of X. We show that if g is primitive, i.e. it has no nontrivial clans, then there exists an edge e or an end verte

The notion of adynamic labeled 2-structure(dℓ2s) is introduced and investigated. It generalizes the notion of a labeled 2-structure (ℓ2s) (Ehrenfeucht and Rozenberg 1990), by making it possible to change the (label) relationships between the nodes. This is achieved by storing in the nodes of a ℓ2s output and input functions that can change the outgoing and incoming labels, respectively. The notion of a clan, which is central in the theory of ℓ2s's is transferred to the framework of dℓ2s's, and the basic properties of clans of dℓ2s's are investigated.

Elementary transition systems are-in a strong categorical sense-the transition system version of a basic system model of net theory called elementary net systems. The structural notion of a region associated with elementary transition systems captures the intuitive idea of a local state as modelled by the conditions of an elementary net system. In this paper we equip elementary transition systems with a refinement operation over the local states (regions). We then show our operation satisfies a number of interesting properties. In particular, this operation supports compositional reasoning. It is very hard if not impossible to define a corresponding operation at the level of nets which enjoys similar properties. This is due to the concrete choice of conditions used to enforce intended behaviour. Thus our results show that the more abstract-but essentially equivalent-model of elementary transition systems is the appropriate framework for theoretical studies concerning refinement operations for elementary net systems.

Transition systems are a simple and powerful formalism for explaining the operational behaviour of models of concurrency. They provide a common framework for investigating the interrelationships between different approaches to the study of distributed systems. Hence an important question to be answered is: which subclass of transition systems corresponds to a particular model of distribted systems? In this paper we provide an answer to this question for elementary net systems. Within net theory, which is one well-established theory of distributed systems, elementary net systems constitute a basic systems model. Using this model, fundamental concepts such as causality, concurrency, conflict and confusion can be clearly defined and separated from each other (see [ 151). Much is known about the behavioural aspects of elementary net systems in terms of trace theory, nonsequential processes and event structures as shown in [lo]. Trace theory was initiated by Mazurkiewicz [7] (see also [l]). The theory of nonsequential processes originates from the work of Petri [12]; see also [2]. Event structures arose out of the work of Nielsen, Plotkin and Winskel [9] and they now possess a rich theory mainly due to the efforts of Winskel [18]. Elementary net systems also have a strong relationship to transition systems. More precisely, there is a natural way of associating a transition system with each elementary net system in order to explain the operational behaviour of elementary net systems in purely sequential terms. Hence the question arises as to which transition systems correspond to elementary net systems.

After extending two word morphismsfand g to languages, an equationf(X) = g(X) can be written and ItS language soluUons investigated.An elementary characterization of the famdy of all solutions of the equation is ~ven, and it is used to mvesttgate the maximal solution which is the mum subject of this paper.It turns out that going through all propagating morphismsf and g, the family of maximal solutions obtained equals the famdy of complements of recurslvely enumerable languages after intersecting with regular languages and mapping with propagating morphisms.In the general case (of arbitrary morphismsf and g) the corresponding family is larger and includes the full-AFL closure of the family of complements of recursively enumerable languages.

It is well known that regularity of a language implies certain properties known as pumping lemmas or iteration theorems. However, the question of a converse result has been open. We show that the usual form of pumping is very far from implying regularity but that a strengthened pumping property, the block pumping property, is equivalent to regularity. The proof involves use of the finite version of Ramsey’s theorem. We compare our results with recent results of Jaffe and Beauquier and state some open questions.

This paper studies an extension of the notion of a finite index ETOL system. It turns out that by setting some quite natural restrictions on the set of bare derivation trees of an ETOL system (that is derivation trees stripped of labels) one can characterize languages of finite rank. Several properties of the new class of ETOL systems are investigated; in particular their relationship to ETOL systems of finite rank and ETOL systems of finite index is investigated.

0S systems generalize context-free grammars without nontermmals it is shown that it is decidable whether or not two arbitrary 0S systems generate the same set of (derivation) sequences It is obtained as a corollary that it is decidable whether or not two arbitrary context-free grammars have the same sets of derivation sequences KEY WORDS AND PHRASES formal languages, context-free grammars, 0S systems, decision problems cg CATEOOgmS 5 23 IntroductionWhen considering a context-free grammar G = (VN, VT, P, S) from the "computational point of view," one can restrict oneself to G = (VN O VT, P, S), which is "a context-free grammar wRhout nontermmals"; such systems have been investigated, e.g., in [l] and [4].When generalized somewhat, such systems give rise to 0S systems, which can be viewed as the _sequential counterpart of 0L systems (see, e.g., [3]).Studying 0S systems is, m our opinion, a very natural step m a systematic study of the foundations of formal language theory.On the one hand, one hopes m this way to build up a more thorough foundation for the theory of context-free languages; on the other hand, when contrasted with the theory of 0L systems, such a study can shed new light on the basic differences between parallel and sequential rewriting systems.In this paper we view a 0S system as a system for generating sequences of words (all "derivations" in it), and then we consider the basic decision problem: Do two arbitrary 0S :~ "~,~ms generate the same set of sequences?We prove that this problem is decidable and show that as a corollary it yields the following result: It is decidable whether or not two arbitrary context-free grammars generate the same set of derivation sequences. PreliminariesWe assume that the reader is familiar with basics of the theory of context-free grammars

Fixed point languages and equality languages of homomorphisms and dgsm mappings are considered.Some basic properties of these classes of languages are proved, and it is shown how to use them to represent recursively enumerable sets.In particular, very simple languages are introduced which play the same role for the class of recursively enumerable languages that the Dyck languages play for the class of context-free languages.Finally, a new type of acceptor for defining equality languages is introduced.

This extended abstract is a condensed version of the results presented in two technical reports ([16] and [13]). In [16] a systematic treatment of the relationships between parallel rewriting systems (top-down tree transducer, ETOL system) and two-way machines (2-way gsm, tree-walking automaton, checking stack automaton) is given. Particular attention is paid to the effect of restricting the copying power of these devices. In [13] the results of [16] are employed to show that the iteration of nondeterministic top-down tree transducers, of nondeterministic 2-way gsm's and of control on ETOL systems each gives rise to a proper hierarchy.

Formal language theory deals with a variety of classes of languages. Some of these are abstracting features of languages used for communication (as e.g., natural languages, programming languages or languages used in logic), some of them are abstracting features of languages used for description of processes (as e.g. basic classes of L languages) and still others are considered for mathematical reasons. Can we have a criterion for deciding whether a language can serve as a “communication language” (e.g. for man-to-man or man-to-machine communication) ? Our main result (The Basic Unpredictability Inequality) displays a connection between the “rate of unpredictability” and the relative number of subpatterns occurring in a language. After establishing this result we investigate (as samples) two classes of languages: regular languages and DOL languages

This paper presents some such results for various families of L languages without interactions (see, e.g., [2] or [9]). We have chosen to investigate L languages (without interactions) because:

A brief introduction to four areas of theoretical research in computer science and bibliographies for these areas are presented. A common factor in each of these areas is one of parallelism and the study of its effects.

Developmental systems were introduced (Lindenmayer, 1968, 1971) in order to model morphogenetic (pattern-generating) processes in growing, multicellular, filamentous organisms. These systems were originally conceived as linear arrays of interconnected finite automata, each automaton corresponding to a living cell, with the possibility that new automata can be added to the array (cells divide) or be deleted from the array (cells die).