91 (1) 2009

Machines, Computations and Universality, Part I. Preface i-ii
On Networks of Evolutionary Processors with Nodes of Two Types
Artiom Alhazov, Jürgen Dassow, Carlos Martín-Vide, Yurii Rogozhin, Bianca Truthe 1-15
We discuss the power of networks of evolutionary processors where only two types of nodes are allowed. We prove that (up to an intersection with a monoid) every recursively enumerable language can be generated by a network with one deletion and one insertion node. Networks with an arbitrary number of deletion and substitution nodes only produce finite languages, and for each finite language one deletion node or one substitution node is sufficient. Networks with an arbitrary number of insertion and substitution nodes only generate context-sensitive languages, and (up to an intersection with a monoid) every context-sensitive language can be generated by a network with one substitution node and one insertion node. All results are optimal with respect to the number of nodes.
Partial Halting and Minimal Parallelism Based on Arbitrary Rule Partitions
Artiom Alhazov, Rudolf Freund, Marion Oswald, Sergey Verlan 17-34
We consider a new variant of the halting condition in P systems, i.e., a computation in a P system is already called halting if not for all membranes a rule is applicable anymore at the same time, whereas usually a computation is called halting if no rule is applicable anymore in the whole system. This new variant of partial halting is especially investigated for several variants of P systems using membrane rules with permitting contexts and working in different transition modes, especially for minimal parallelism. Both partial halting and minimal parallelism are based on an arbitrary set of subsets from the set of rules assigned to the membranes.
Satisfiability Parsimoniously Reduces to the Tantrix Rotation Puzzle Problem
Dorothea Baumeister and Jörg Rothe 35-51
Holzer and Holzer [10] proved that the Tantrix rotation puzzle problem is NP-complete. They also showed that for infinite rotation puzzles, this problem becomes undecidable. We study the counting version and the unique version of this problem. We prove that the satisfiability problem parsimoniously reduces to the Tantrix rotation puzzle problem. In particular, this reduction preserves the uniqueness of the solution, which implies that the unique Tantrix rotation puzzle problem is as hard as the unique satisfiability problem, and so is DP-complete under polynomial-time randomized reductions, where DP is the second level of the boolean hierarchy over NP.
Universality for Turing Machines, Inductive Turing Machines and Evolutionary Algorithms
Mark Burgin, Eugene Eberbach 53-77
The aim of this paper is the development of foundations for evolutionary computations. To achieve this goal, a mathematical model of evolutionary automata is introduced and studied. The main classes of evolutionary automata considered in this paper are evolutionary Turing machines and evolutionary inductive Turing machines. Various subclasses and modes of evolutionary computation are defined. Problems of existence of universal objects in these classes are explored. Relations between Turing machines, inductive Turing machines, evolutionary Turing machines, and evolutionary inductive Turing machines are investigated.
Skolem Machines
John Fisher, Marc Bezem 79-103
The Skolem machine is a Turing-complete machine model where the instructions are first-order formulas of a specific form. We introduce Skolem machines and prove their logical correctness and completeness. Skolem machines compute queries for the Geolog language, a rich fragment of first-order logic. The concepts of Geolog trees and complete Geolog trees are defined, and these tree concepts are used to show logical correctness and completeness of Skolem machine computations. The universality of Skolem machine computations is demonstrated. Lastly, the paper outlines implementation design issues using an abstract machine model approach.
More on the Size of Higman-Haines Sets: Effective Constructions
Hermann Gruber, Markus Holzer, Martin Kutrib 105-121
A not so well-known result in formal language theory is that the Higman-Haines sets for any language are regular [11, Theorem 4.4]. It is easily seen that these sets cannot be effectively computed in general. The Higman-Haines sets are the languages of all scattered subwords of a given language as well as the sets of all words that contain some word of a given language as a scattered subword. Recently, the exact level of unsolvability of Higman-Haines sets was studied in [8]. Here we focus on language families whose Higman-Haines sets are effectively constructible. In particular, we study the size of descriptions of Higman-Haines sets for the lower classes of the Chomsky hierarchy, namely for the family of regular, linear context-free, and context-free languages. We prove upper and lower bounds on the size of descriptions of these sets for general and unary languages.
Four Small Universal Turing Machines
Turlough Neary and Damien Woods 123-144
We present universal Turing machines with state-symbol pairs of (5,5), (6,4), (9,3) and (15,2). These machines simulate our new variant of tag system, the bi-tag system and are the smallest known single-tape universal Turing machines with 5, 4, 3 and 2-symbols, respectively. Our 5-symbol machine uses the same number of instructions (22) as the smallest known universal Turing machine by Rogozhin. Also, all of the universal machines we present here simulate Turing machines in polynomial time.
Array P Systems and t-Communication
K. G. Subramanian, Rosihan M. Ali, Atulya K. Nagar, Maurice Margenstern 145-159
The two areas of grammar systems and P systems, which have provided interesting computational models in the study of formal string language theory have been in the recent past effectively linked in [4] by incorporating into P systems, a communication mode called t-mode of cooperating distributed grammar systems. On the other hand cooperating array grammar systems [5] and array P systems [1] have been developed in the context of two-dimensional picture description. In this paper, motivated by the study of [4], these two systems are studied by linking them through the t-communication mode, thus bringing out the picture description power of these systems.
A Small Five-State Non-Optimum-Time Solution to the Firing Squad Synchronization Problem - A Geometrical Approach -
Hiroshi Umeo and Takashi Yanagihara 161-178
An existence or non-existence of five-state firing squad synchronization protocol has been a long-standing, famous open problem for a long time. In this paper, we answer partially to this problem by proposing a small five-state firing squad synchronization algorithm that can synchronize any one-dimensional cellular array of length n=2^k in 3n-3 steps for any positive integer k.
Small Semi-Weakly Universal Turing Machines
Damien Woods, Turlough Neary 179-195
We present three small universal Turing machines that have 3 states and 7 symbols, 4 states and 5 symbols, and 2 states and 13 symbols, respectively. These machines are semi-weakly universal which means that on one side of the input they have an infinitely repeated word, and on the other side there is the usual infinitely repeated blank symbol. This work can be regarded as a continuation of early work by Watanabe on semi-weak machines. One of our machines has only 17 transition rules, making it the smallest known semi-weakly universal Turing machine. Interestingly, two of our machines are symmetric with Watanabe's 7-state and 3-symbol, and 5-state and 4-symbol machines, even though we use a different simulation technique.

91 (2) 2009

Machines, Computations and Universality, Part II. Preface i-ii
Intrinsically universal one-dimensional quantum cellular automata in two flavours
Pablo Arrighi, Renan Fargetton, Zizhu Wang 197-230
We give a one-dimensional quantum cellular automaton (QCA) capable of simulating all others. By this we mean that the initial configuration and the local transition rule of any one-dimensional QCA can be encoded within the initial configuration of the universal QCA. Several steps of the universal QCA will then correspond to one step of the simulated QCA. The simulation preserves the topology in the sense that each cell of the simulated QCA is encoded as a group of adjacent cells in the universal QCA. The encoding is linear and hence does not carry any of the cost of the computation. We do this in two flavours: a weak one which requires an infinite but periodic initial configuration and a strong one which needs only a finite initial configuration.
The Complexity of Unary Tiling Recognizable Picture Languages: Nondeterministic and Unambiguous Cases
Alberto Bertoni, Massimiliano Goldwurm, Violetta Lonati 231-249
In this paper we consider the classes REC₁ and UREC₁ of unary picture languages that are tiling recognizable and unambiguously tiling recognizable, respectively. By representing unary pictures by quasi-unary strings we characterize REC₁ (resp. UREC₁) as the class of quasi-unary languages recognized by nondeterministic (resp. unambiguous) linearly space-bounded one-tape Turing machines with constraint on the number of head reversals. We apply such a characterization in two directions. First we prove that the binary string languages encoding tiling recognizable unary square languages lies between NTIME(2ⁿ) and NTIME(4ⁿ); by separation results, this implies there exists a non-tiling recognizable unary square language whose binary representation is a language in NTIME(4ⁿ logn). In the other direction, by means of results on picture languages, we are able to compare the power of deterministic, unambiguous and nondeterministic one-tape Turing machines that are linearly space-bounded and have constraint on the number of head reversals.
Modelling of Complex Systems: Systems as Dataflow Machines
Simon Bliudze, Daniel Krob 251-274
We develop a unified functional formalism for modelling complex systems, that is to say systems that are composed of a number of heterogeneous components, including typically software and physical devices. Our approach relies on non-standard analysis that allows us to model continuous time in a discrete way.
Systems are defined as generalized Turing machines with temporized input, internal and output mechanisms. Behaviors of systems are represented by transfer functions. A transfer function is said to be implementable if it is associated with a system. This notion leads us to define a new class - which is natural in our framework - of computable functions on (usual) real numbers.
We show that our definitions are robust: on one hand, the class of implementable transfer functions is closed under composition; on the other hand, the class of computable functions in our meaning includes analytical functions whose coefficients are computable in the usual way, and is closed under addition, multiplication, differentiation and integration. Our class of computable functions also includes solutions of dynamical and Hamiltonian systems defined by computable functions. Hence, our notion of system appears to take suitably into account physical systems.
Flat Parametric Counter Automata
Marius Bozga, Radu Iosif, Yassine Lakhnech 275-303
In this paper we study the reachability problem for parametric flat counter automata, in relation with the satisfiability problem of three fragments of integer arithmetic. The equivalence between non-parametric flat counter automata and Presburger arithmetic has been established previously by Comon and Jurski. We simplify their proof by introducing finite state automata defined over alphabets of a special kind of graphs (zigzags). This framework allows one to express also the reachability problem for parametric automata with one control loop as the satisfiability of a 1-parametric linear Diophantine systems. The latter problem is shown to be decidable, using a number-theoretic argument. In general, the reachability problem for parametric flat counter automata with more than one loops is shown to be undecidable, by reduction from Hilbert's Tenth Problem. Finally, we study the relation between flat counter automata, integer arithmetic, and another important class of computational devices, namely the 2-way reversal bounded counter machines.
Highly Undecidable Problems about Recognizability by Tiling Systems
Olivier Finkel 305-323
Altenbernd, Thomas and Wöhrle have considered acceptance of languages of infinite two-dimensional words (infinite pictures) by finite tiling systems, with usual acceptance conditions, such as the Büchi and Muller ones, in [1]. It was proved in [9] that it is undecidable whether a Büchi-recognizable language of infinite pictures is E-recognizable (respectively, A-recognizable). We show here that these two decision problems are actually P₂¹-complete, hence located at the second level of the analytical hierarchy, and "highly undecidable". We give the exact degree of numerous other undecidable problems for Büchi-recognizable languages of infinite pictures. In particular, the non-emptiness and the infiniteness problems are S₁¹-complete, and the universality problem, the inclusion problem, the equivalence problem, the determinizability problem, the complementability problem, are all P₂¹-complete. It is also P₂¹-complete to determine whether a given Büchi recognizable language of infinite pictures can be accepted row by row using an automaton model over ordinal words of length w².
Quantum Testers for Hidden Group Properties
Katalin Friedl, Frédéric Magniez, Miklos Santha, Pranab Sen 325-340
We construct efficient or query efficient quantum property testers for two existential group properties which have exponential query complexity both for their decision problem in the quantum and for their testing problem in the classical model of computing. These are periodicity in groups and the common coset range property of two functions having identical ranges within each coset of some normal subgroup. Our periodicity tester is efficient in Abelian groups and generalizes, in several aspects, previous periodicity testers. This is achieved by introducing a technique refining the majority correction process widely used for proving robustness of algebraic properties. The periodicity tester in non-Abelian groups and the common coset range tester are query efficient.
On the Dynamics of Social Balance on General Networks (with an application to XOR-SAT)
Gabriel Istrate 341-356
We study nondeterministic and probabilistic versions of a discrete dynamical system (due to T. Antal, P. L. Krapivsky, and S. Redner [3]) inspired by Heider's social balance theory. We investigate the convergence time of this dynamics on several classes of graphs. Our contributions include:
1. We point out the connection between the triad dynamics and a generalization of annihilating walks to hypergraphs. In particular, this connection allows us to completely characterize the recurrent states in graphs where each edge belongs to at most two triangles.
2. We also solve the case of hypergraphs that do not contain edges consisting of one or two vertices.
3. We show that on the so-called "triadic cycle"graph, the convergence time is linear.
4. We obtain a cubic upper bound on the convergence time on 2-regular triadic simplexes G. This bound can be further improved to a quantity that depends on the Cheeger constant of G. In particular this provides some rigorous counterparts to experimental observations in [25].
We also point out an application to the analysis of the random walk algorithm on certain instances of the 3-XOR-SAT problem.
Universal Hard Interaction for Clockless Computation
Dem Glücklichen schlägt keine Stunde!
Sylvain Lippi 357-394
We give a self-contained presentation of Hard Interaction, a rewriting system on fixed graphs. We discuss the universality of natural subclasses of hard systems and highlight the main ideas that lead to a universal system with 7 rules called Hard Combinators.
On the Computational Power of Querying the History
Alexei Lisitsa, Igor Potapov 395-409
Querying its own history is an important mechanism in the computations, especially those interacting with people or other computations such as transaction processing, electronic data interchange. John McCarthy in his Elephant programming language proposal suggested exploiting the referring to the past as the main programming primitive. In this paper we study the computational power of such primitive. In order to do that we propose a refined formal model, History Dependent Machine (HDM), which uses querying the history as its sole computational primitive. Our main result may be spelled in general terms as: a model with a single agent wandering around a pool of resources and having ability to check its own history for simple temporal properties has a universal computational power. Moreover, HDM can simulate any multicounter machine in real time. Then we show that the computations of HDM may be specified in the extension of propositional linear temporal logic by flexible constants, the abstraction operator and equality. We use then universality of HDM model to show that the above extension with a single flexible constant is not recursively axiomatizable.
Program Schemes, Queues, the Recursive Spectrum and Zero-one Laws
Iain A. Stewart 411-435
We prove that a very basic class of program schemes augmented with access to a queue and an additional numeric universe within which counting is permitted, so that the resulting class is denoted NPSQ₊(1), is such that the class of problems accepted by these program schemes is exactly the class of recursively enumerable problems. The class of problems accepted by the program schemes of the class NPSQ(1) where only access to a queue, and not the additional numeric universe, is allowed is exactly the class of recursively enumerable problems that are closed under extensions. We define an infinite hierarchy of classes of program schemes for which NPSQ(1) is the first class and the union of the classes of which is the class NPSQ. We show that the class of problems accepted by the program schemes of NPSQ is the union of the classes of problems defined by the sentences of all vectorized Lindström logics formed using operators whose corresponding problems are recursively enumerable and closed under extensions, and, as a result, has a zero-one law. Moreover, we also show that this class of problems can be realized as the class of problems defined by the sentences of a particular vectorized Lindström logic. Finally, we show how our results can be applied to yield logical characterizations of complexity classes and provide logical analogues to a number of inequalities and hypotheses from computational complexity theory involving (non-deterministic) complexity classes ranging from NP through to ELEMENTARY.

91 (3-4) 2009

Associativity of Infinite Synchronized Shuffles and Team Automata
Maurice H. ter Beek, Jetty Kleijn 437-461
Motivated by different ways to obtain team automata from synchronizing component automata, we consider various definitions of synchronized shuffles of words. A shuffle of two words is an interleaving of their symbol occurrences which preserves the original order of these occurrences within each of the two words. In a synchronized shuffle, however, also two occurrences of one symbol, each from a different word, may be identified as a single occurrence. In case at least one of the words involved is infinite, a (synchronized) shuffle can also be unfair in the sense that an infinite word may prevail from some point onwards even when the other word still has occurrences to contribute to the shuffle. We prove that for the synchronized shuffle operations under consideration, every (fair or unfair) synchronized shuffle can be obtained as a limit of synchronized shuffles of the finite prefixes of the words involved. In addition, it is shown that with the exception of one, all synchronized shuffle operations that we consider satisfy a natural notion of associativity, also in case of unfairness. Finally, using these results, some compositionality results for team automata are established.
Behaviour Preservation of a Biological Regulatory Network when Embedded into a Larger Network
Gilles Bernot, Fariza Tahi 463-485
The main contribution of this work is a mathematical theorem which establishes a necessary and sufficient condition to preserve the behaviour of a genetic regulatory network when it is embedded into a larger network. We adopt the modelling approach of René Thomas, which provides a discrete representation of biological regulatory networks. This framework is entirely formalized using labelled graphs with semantics defined in terms of state graphs with transitions. Our theorem offers the possibility to automatically verify whether a subnetwork has autonomous behaviour. It will allow biologists to better identify relevant sets of genes which should be studied together.
Real Polygonal Covers of Digital Discs - Some Theories and Experiments
Partha Bhowmick, Bhargab B. Bhattacharya 487-505
There are several algorithms for digitization of a real disc (circle) to derive a digital disc, and also for finding the real disc corresponding to a digital disc. However, the correspondence of a digital disc with a regular polygon in the real plane is not well studied. This paper presents some theories and related experiments on setting the correspondence from a digital disc to its polygonal cover in the real plane. For an ideal regular polygon covering a digital disc, all the grid points of the digital disc should lie on and inside the polygon, and vice versa. That an ideal regular polygon corresponding to a digital disc is possible for some of the digital discs, especially for the ones having smaller radii, is shown. Further, for a disc whose ideal regular polygon is not possible, an approximate polygon, tending to the ideal one, is possible, in which the error of approximation can be controlled by the number of vertices of the approximate polygon. These (ideal or approximate) polygonal covers of digital discs have several applications in many problems of point set pattern matching. We have reported the conditions under which an ideal regular polygon always exists corresponding to a digital disc, and the conditions under which the existence of an ideal regular polygon becomes uncertain. Experimental results have been given to demonstrate the possibilities of approximation and the trade-off in terms of error versus the number of vertices in the approximate polygon.
Analysis of Components for Generalization using Multidimensional Scaling
Robertas Damasevicius 507-522
To achieve better software quality, to shorten software development time and to lower development costs, software engineers are adopting generative reuse as a software design process. The usage of generic components allows increasing reuse and design productivity in software engineering. Generic component design requires systematic domain analysis to identify similar components as candidates for generalization. However, component feature analysis and identification of components for generalization usually is done ad hoc. In this paper, we propose to apply a data visualization method, called Multidimensional Scaling (MDS), to analyze software components in the multidimensional feature space. Multidimensional data that represent syntactical and semantic features of source code components are mapped to 2D space. The results of MDS are used to partition an initial set of components into groups of similar source code components that can be further used as candidates for generalization. STRESS value is used to estimate the generalizability of a given set of components. Case studies for Java Buffer and Geom class libraries are presented.
A Further Improved Online/Offline Signature Scheme
Chong-zhi Gao, Zheng-an Yao 523-532
Online/offline signatures are used in a particular scenario where the signer must respond quickly once the message to be signed is presented. In this paper, we present a general method to efficiently convert a trapdoor hash family into an online/offline signature scheme without resorting to any additional signature scheme. We prove that the new scheme is secure in the random oracle model if the underlying trapdoor hash family is collision resistant. Compared to Shamir and Tauman's paradigm, there is an almost 50% reduction in overall computational cost by using the new scheme.
Hypergraphs for Generic Lossless Image Compression
Luc Gillibert and Alain Bretto 533-546
Hypergraphs are a large generalisation of graphs; they are now used for many low-level image processing, by example for noise reduction, edge detection and segmentation [3,4,7]. In this paper we define a generic 2D and 3D-image representation based on a hypergraph. We present the mathematical definition of the hypergraph representation of an image and we show how this representation conducts to an efficient lossless compression algorithm for 2D and 3D-images. Then we introduce both 2D and 3D version of the algorithm and we give some experimental results on some various sets of images: 2D photo, 2D synthetic pictures, 3D medical images and some short animated sequences.
Adjective Sense Disambiguation at the Border Between Unsupervised and Knowledge-Based Techniques
Florentina Hristea, Marius Popescu 547-562
The present paper extends a new word sense disambiguation method [9] to the case of adjectives. The method lies at the border between unsupervised and knowledge-based techniques. It performs unsupervised word sense disambiguation based on an underlying Naïve Bayes model, while using WordNet as knowledge source for feature selection. The proposed extension of the disambiguation method makes ample use of the WordNet semantic relations that are typical of adjectives. Its performance is compared to that of previous approaches that rely on completely different feature sets. Test results show that feature selection using a knowledge source of type WordNet is more effective in the disambiguation of adjective senses than local type features (like part-of-speech tags) are.
A Fast VQ Codebook Generation Algorithm Based on Otsu Histogram Threshold
Chang-Chin Huang, Du-Shiau Tsai, Gwoboa Horng 563-579
In vector quantization, the codebook generation problem can be formulated as a classification problem of dividing N_p training vectors into N_c clusters, where N_p is the training size of input vectors and N_c is the codeword size of codebook. For large N_p and N_c, a traditional search algorithm such as the LBG method can hardly find the global optimal classification and needs a great deal of calculation. In this paper, a novel VQ codebook generation method based on Otsu histogram threshold is proposed. The computational complexity of squared Euclidean distance can be reduced to O(N_plog₂N_c) for a codebook with gray levels. Our method provides better image quality than recent proposed schemes in high compression ratio. The experimental results and the comparisons show that this method can not only reduce the computational complexity of squared Euclidean distance but also find better codewords to improve the quality of the resulted VQ codebook.
Reversible Data Hiding Based on Three-Circular-Pixel Difference Expansion
Ching-Chiuan Lin, Shun-Ping Yang, Nien-Lin Hsueh 581-595
This paper proposes a reversible data hiding scheme based on three-circular-pixel (TCP) difference expansion. To embed a message in an image, the image is divided into three-pixel blocks, each of which is, then, transformed into a TCP block with two differences. When the pixel value of the largest pixel in the TCP block is increased, two differences are increased-one is between the largest and the smallest, and the other is between the largest and the middle. Expanding the two differences in the block by increasing the largest pixel value may make the image less modified. In addition, the number of pixel pairs is increased to two thirds of the number of pixels in the image. Compared to Tian's study, both the visual quality and the embedding capacity of the image are significantly improved.
An Information-Hiding Scheme Based on Quantization-Based Embedding Technique
Tzu-Chuen Lu, Chin-Chen Chang, Yi-Long Liu 597-610
Information hiding is a technique that embeds secret data in digital media for using in a variety of applications, including ownership protection, authentication, access control, annotation and so on. In this paper, we propose an information hiding scheme based on quantization-based embedding technique to conceal information in gray-scale image. The proposed scheme was tested with a variety of gray images. According to the experimental results, hidden information can be extracted correctly and quickly from the stego image. In addition, the stego image has only a little distortion compared with the cover image. The proposed scheme can not only hide a large amount of information in the cover image, but can also repair the stego image such that the repaired image is almost the same as the cover image.
Series-Parallel Automata and Short Regular Expressions
Nelma Moreira and Rogério Reis 611-629
Computing short regular expressions equivalent to a given finite automaton is a hard task. In this work we present a class of acyclic automata for which it is possible to obtain in time O(n²logn) an equivalent regular expression of size O(n). A characterisation of this class is made using properties of the underlying digraphs that correspond to the series-parallel digraphs class. Using this characterisation we present an algorithm for the generation of automata of this class and an enumerative formula for the underlying digraphs with a given number of vertices.
Handling Inconsistency In Distributed Software Requirements Specifications Based On Prioritized Merging
Kedian Mu, Weiru Liu, Zhi Jin, Ruqian Lu, Anbu Yue, David Bell 631-670
Developing a desirable framework for handling inconsistencies in software requirements specifications is a challenging problem. It has been widely recognized that the relative priority of requirements can help developers to make some necessary trade-off decisions for resolving conflicts. However, for most distributed development such as viewpoints-based approaches, different stakeholders may assign different levels of priority to the same shared requirements statement from their own perspectives. The disagreement in the local levels of priority assigned to the same shared requirements statement often puts developers into a dilemma during the inconsistency handling process. The main contribution of this paper is to present a prioritized merging-based framework for handling inconsistency in distributed software requirements specifications. Given a set of distributed inconsistent requirements collections with the local prioritization, we first construct a requirements specification with a prioritization from an overall perspective. We provide two approaches to constructing a requirements specification with the global prioritization, including a merging-based construction and a priority vector-based construction. Following this, we derive proposals for handling inconsistencies from the globally prioritized requirements specification in terms of prioritized merging. Moreover, from the overall perspective, these proposals may be viewed as the most appropriate to modifying the given inconsistent requirements specification in the sense of the ordering relation over all the consistent subsets of the requirements specification. Finally, we consider applying negotiation-based techniques to viewpoints so as to identify an acceptable common proposal from these proposals.