Fundamenta Informaticae - Volume 110, issue 1-4

Authors: , Juhani | Karhumäki, | , Gheorghe | Păun, | Rozenberg, Grzegorz | Salomaa, Arto

Article Type: Other

DOI: 10.3233/FI-2011-523

Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. vii-viii, 2011

Authors: Akhtarzada, Ali | Calude, Cristian S. | Hosking, John

Article Type: Research Article

Abstract: Information overload and an abundance of choices create situations where selecting one option becomes extremely difficult or even worse, a guessing game. Collaborative ranking systems are widely used to alleviate this problem by creating intelligent rankings of items based on an aggregation of user opinions. Current ranking systems can still be improved in a number of areas, including accuracy, transparency and flexibility. This paper presents a multi-criteria ranking algorithm that can be used on a non-rigid set of criteria. The system implementing the algorithm fares well with respect to the above qualities.

Keywords: Metric algorithm, intelligent ranking, non-rigid criteria

DOI: 10.3233/FI-2011-524

Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 1-11, 2011

Authors: Alhazov, Artiom | Krassovitskiy, Alexander | Rogozhin, Yurii | Verlan, Sergey

Article Type: Research Article

Abstract: It is known that insertion-deletion (P) systems with two symbols context-free insertion and deletion rules are not computationally complete. It is thus interesting to consider conditions that would allow such systems to reach computational completeness. In this paper we consider insertion-deletion P systems with insertion and deletion operations applied only at the ends of string (we call them exo-operations). We show that such systems with one-symbol insertion and deletion of up to two symbols are computationally complete, and so are systems with insertion of up to two symbols and one-symbol deletion. The question about the computational power of insertion-deletion P …systems with one-symbol insertion and one-symbol deletion operations applied at the ends of string is open. However, the tissue P systems reach computationally completeness even in this case. Show more

DOI: 10.3233/FI-2011-525

Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 13-28, 2011

Authors: Azimi, Sepinoud | Harju, Tero | Langille, Miika | Petre, Ion | Rogojin, Vladimir

Article Type: Research Article

Abstract: The simple intramolecular model for gene assembly in ciliates consists of three molecular operations based on local DNA manipulations. It was shown to predict correctly the assembly of all currently known ciliate gene patterns. Mathematical models in terms of signed permutations and signed strings proved limited in capturing some of the combinatorial details of the simple gene assembly process. A different formalization in terms of overlap-inclusion graphs, recently introduced by Brijder and Hoogeboom, proved well-suited to describe two of the three operations of the model and their combinatorial properties. We introduce in this paper an extension of the framework of …Brijder and Hoogeboom in terms of directed overlap-inclusion graphs where more of the linear structure of the ciliate genes is described. We investigate a number of combinatorial properties of these graphs, including a necessary property in terms of forbidden induced subgraphs. Show more

Keywords: Directed overlap-inclusion graphs, gene assembly in Ciliates, simple operations

DOI: 10.3233/FI-2011-526

Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 29-44, 2011

Authors: Ballier, Alexis | Guillon, Pierre | Kari, Jarkko

Article Type: Research Article

Abstract: We construct a cellular automaton (CA) with a sofic and mixing limit set and then construct a stable CA with the same limit set, showing there exist subshifts that can be limit sets of both stable and unstable CAs, answering a question raised by A. Maass.

DOI: 10.3233/FI-2011-527

Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 45-57, 2011

Authors: Böckenhauer, Hans-Joachim | Hromkovič, Juraj | Sprock, Andreas

Article Type: Research Article

Abstract: In reoptimization, we consider the following scenario: Given an instance of a hard optimization problem together with an optimal solution for it, we want to solve a locally modified instance of the problem. It has recently been shown for several hard optimization problems that their corresponding reoptimization variants remain 𝒩𝒫-hard or even hard to approximate whereas they often admit improved approximation ratios. In this paper, we investigate a generalization of the reoptimization concept where we are given not only one optimal solution but multiple optimal solutions for an instance. We prove, for some variants of the Steiner tree problem and …the traveling salesman problem, that the known reoptimization hardness results carry over to this generalized setting. Moreover, we consider the performance of local search strategies on reoptimization problems. We show that local search does not work for solving TSP reoptimization, even in the presence of multiple solutions. Show more

Keywords: Reoptimization, Steinertree, TSP, Multiple Given Solution, Hardness

DOI: 10.3233/FI-2011-528

Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 59-76, 2011

Authors: Bonizzoni, Paola | Ferretti, Claudio | Mary, A. Roslin Sagaya | Mauri, Giancarlo

Article Type: Research Article

Abstract: We propose a new formalism for generating picture languages based on an assembly mechanism of tiles that uses rules having a context and a replacement site. More precisely, a picture language will be generated from a finite set of initial pictures by iteratively applying rewriting rules from a given finite set of rules, called a tiling rule system (TRuS system). We prove that the TRuS systems have a greater generative capacity than the tiling systems of Giammarresi and Restivo. This is due mainly to the use of the notion of replacement site, but we further characterize the difference between these …systems by comparing them to Wang systems. Show more

DOI: 10.3233/FI-2011-529

Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 77-93, 2011

Authors: Cui, Cewei | Dang, Zhe | Fischer, Thomas R.

Article Type: Research Article

Abstract: We introduce (finite and infinite) typical paths of a graph and prove that the typical paths carry all information with probability 1, asymptotically. An automata-theoretic characterization of the typical paths is shown: finite typical paths can be accepted by reversal-bounded multicounter automata and infinite typical paths can be accepted by counting Büchi automata (a generalization of reversal-bounded multicounter automata running on ω-words). We take a statechart example to show how to generate typical paths from a graph using SPIN model checker. The results are useful in automata theory since one can identify an information-concentrated-core of a regular language such that …only words in the information-concentrated-core carry nontrivial information. When the graph is used to specify the system under test, the results are also useful in software testing by providing an information-theoretic approach to select test cases that carry nontrivial information of the system specification. Show more

Keywords: graph, entropy, path

DOI: 10.3233/FI-2011-530

Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 95-109, 2011

Authors: Eğecioğlu, Ömer | Hegedüs, Lászl´ | Nagy, Benedek

Article Type: Research Article

Abstract: We consider stateless counter machines which mix the features of one-head counter machines and a special type of two-head Watson-Crick automata (WK-automata). Our Watson-Crick counter machines are biologically motivated. They have two heads that read the input starting from the two extremes. The reading process is finished when there are no more symbols between the heads, i.e., every letter of the input is processed by either head. Depending on whether the heads are required to advance at each move, we distinguish between realtime and non-realtime machines. If every counter makes at most k alternations between nondecreasing and decreasing modes in …every computation, then the machine is k-reversal. It is reversal bounded if it is k-reversal for some k. In this paper we concentrate on the properties of both deterministic and nondeterministic stateless WK-automata with reversal bounded counters. Show more

DOI: 10.3233/FI-2011-531

Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 111-123, 2011

Authors: Eisman, Gerry | Ravikumar, Bala

Article Type: Research Article

Abstract: Approximate computation is a central concept in algorithms and computation theory. Our notion of approximation is that the algorithm performs correctly on most of the inputs. We propose some finite automata models to study the question of how well a finite automaton can approximately recognize a non-regular language. On the one hand, we show that there are natural problems for which a DFA can correctly solve almost all the instances, but not all instances. An example of such a problem is a decision question about the number of digits in the square of a given integer. On the other hand, …we show that some languages (such as Lmajority = {x ∈ (0 + 1)* | x has more 1′s than 0′s }) can't be approximated by any regular language in a strong sense. We also show that there are problems that are intermediate (between the extremes stated above) in terms of how we well a regular language can approximate it. An example of such a problem is a decision question about the number of digits in the product of two integers. We also present results comparing different models of approximation. Show more

Keywords: finite automata, approximation, majority language, squaring

DOI: 10.3233/FI-2011-532

Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 125-142, 2011