Fundamenta Informaticae - Volume 73, issue 1-2

Article Type: Other

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. i-i, 2006

Authors: Calude, Cristian S. | Câmpeanu, Cezar | Dumitrescu, Monica

Article Type: Research Article

Abstract: How likely is that a randomly given (non-) deterministic finite automaton recognizes no word? A quick reflection seems to indicate that not too many finite automata accept no word; but, can this intuition be confirmed? In this paper we offer a statistical approach which allows us to conclude that for automata, with a large enough number of states, the probability that a given (non-) deterministic finite automaton recognizes no word is close to zero. More precisely, we will …show, with a high degree of accuracy (i.e., with precision higher than 99% and level of confidence 0.9973), that for both deterministic and non-deterministic finite automata: a) the probability that an automaton recognizes no word tends to zero when the number of states and the number of letters in the alphabet tend to infinity, b) if the number of states is fixed and rather small, then even if the number of letters of the alphabet of the automaton tends to infinity, the probability is strictly positive. The result a) is obtained via a statistical analysis; for b) we use a combinatorial and statistical analysis. The present analysis shows that for all practical purposes the fraction of automata recognizing no words tends to zero when the number of states and the number of letters in the alphabet grow indefinitely. From a theoretical point of view, the result can motivate the search for "certitude" that is, a proof of the fact established here in probabilistic terms. In the last section we critically discuss the result and the method used in this paper. Show more

Keywords: Finite automata, emptiness problem, statistical analysis, sampling method

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 1-18, 2006

Authors: Ceterchi, Rodica

Article Type: Research Article

Abstract: An algebraic characterization of simple splicing languages given in [6] is extended to semi-simple splicing languages.

Keywords: DNA computing, splicing, algebraic characterization

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 19-25, 2006

Authors: Ciobanu, Gabriel | Păun, Gheorghe | Pérez-Jiménez, Mario J.

Article Type: Research Article

Abstract: We consider two complexity parameters related to the graph of reachable configurations of a given P system, namely the outdegree as a measure of the degree of non-determinism, and the indegree as a measure of the degree of confluence. These parameters can be defined for both the generative and the accepting mode of using a P system. We investigate here these parameters in what concerns hierarchies and decidability issues. We prove that all hierarchies have only …two levels and that all considered decidability problems have a negative answer. Show more

Keywords: Membrane computing, non-determinism, descriptional complexity, decidability

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 27-36, 2006

Authors: Csuhaj-Varjú, Erzsébet | Mateescu, Alexandru

Article Type: Research Article

Abstract: In this paper we discuss some relationships between cooperating distributed (CD) grammar systems and the basic process algebra (BPA) calculus. We associate different types of process graphs from this calculus to CD grammar systems which describe the behavior of the components of the system under cooperation. We prove that these process graphs form a subalgebra of the graph model of BPA. It is also shown that for certain restricted variants of CD grammar systems and for …certain types of these process graphs the bisimilarity of two process graphs is decidable. Show more

Keywords: Cooperating distributed grammar systems, basic process algebra, process graph

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 37-50, 2006

Authors: Ding, Cunsheng | Salomaa, Arto

Article Type: Research Article

Abstract: Secret sharing schemes, introduced by Blakley and Shamir independently in 1979, have a number of applications in security systems. One approach to the construction of secret sharing schemes is based on coding theory. In principle, every linear code can be used to construct secret sharing schemes. But only well structured linear codes give secret sharing schemes with nice access structures in the sense that every pair of participants plays the same role in the secret sharing. …In this paper, we construct a class of good linear codes, and use them to obtain a class of secret sharing schemes with nice access structures. Show more

Keywords: Secret sharing, linear codes, access structures

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 51-63, 2006

Authors: Ding, Cunsheng | Salomaa, Arto

Article Type: Research Article

Abstract: The paper investigates inference based on quantities |W|_u , the number of occurrences of a word u as a scattered subword of W. Parikh matrices recently introduced are useful tools for such investigations. We introduce and study universal languages for Parikh matrices. We also obtain results concerning the inference from numbers |W|_u to W, as well as from certain entries of a Parikh matrix to other entries.

Keywords: Subword, scattered subword, number of subwords, Parikh matrix, inference from subwords, ambiguity

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 65-79, 2006

Authors: Domaratzki, Michael | Rozenberg, Grzegorz | Salomaa, Kai

Article Type: Research Article

Abstract: We introduce generalized trajectories where the individual symbols are interpreted as operations performed on the operand words. The various previously considered trajectory-based operations can all be expressed in this formalism. It is shown that the generalized operations can simulate Turing machine computations. We consider the equivalence problem and a notion of unambiguity that is sufficient to make equivalence decidable for regular sets of trajectories under nonincreasing interpretations.

Keywords: Formal languages, decidability, trajectories, regularity, unambiguity

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 81-97, 2006

Authors: Droste, Manfred | Kari, Jarkko | Steinby, Paula

Article Type: Research Article

Abstract: We continue investigations of weighted finite automata (WFA) as devices to compute real functions. Based on eigenvalues of the transition matrices of automata we provide a simple necessary condition for continuity and smoothness properties of the functions they compute. Using this condition we show that polynomials are the only smooth functions computed by WFA and that any WFA computing a polynomial of degree k must have at least k+1 states. The results answer problems left open …in [7]. Show more

Keywords: Weighted finite automata, continuity, smoothness

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 99-106, 2006

Authors: Dumitrescu, Sorina

Article Type: Research Article

Abstract: We address the problem of designing optimal prefix-free codes over an encoding alphabet with unequal integer letter costs. The most efficient algorithm proposed so far has O(n^{C+2} ) time complexity, where n is the number of codewords and C is the maximum letter cost. For the special case when the encoding alphabet is binary, a faster solution was proposed, namely of O(n^C ) time complexity, based on a more sophisticated modeling of the problem, …and on exploiting the Monge property of the cost function. However, those techniques seemed not to extend to the r-letter alphabet. This work proves that, on the contrary, the generalization to the r-letter case is possible, thus leading to a O(n^C ) time complexity algorithm for the case of arbitrary number of letters. Show more

Keywords: Prefix-free codes, unequal letter costs, lopsided trees, optimization, Monge property

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 107-117, 2006

Authors: Halava, Vesa | Harju, Tero | Karhumäki, Juhani

Article Type: Research Article

Abstract: In the infinite Post Correspondence Probleman instance (h,g) consists of two morphisms h and g, and the problem is to determine whether or not there exists an infinite word α such that h(α)=g(α). In the general case this problemwas shown to be undecidable by K. Ruohonen (1985). Recently, it was proved that the infinite PCP is undecidable already when the domain alphabet of the morphisms consists of at least 9 letters. Here we show that the …problem is undecidable for instances where the morphisms have a domain of 6 letters, when we restrict to solutions of ω-languages of the form R^{ω} where R is a given regular language. Show more

Keywords: Post Correspondence Problem, infinite word, semi-Thue system, regular language, undecidability

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 119-125, 2006

Authors: Honkala, Juha

Article Type: Research Article

Abstract: We show that it is undecidable whether or not a given N-rational series assumes all nonnegative values. As a consequence we see that it is undecidable whether the image of a given N-rational series equals the image of a given N-rational sequence. We discuss also related results concerning DT0L and D0L length sets.

Keywords: N-rational series, decidability

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 127-132, 2006

Authors: Ibarra, Oscar H. | Woodworth, Sara | Yen, Hsu-Chun | Dang, Zhe

Article Type: Research Article

Abstract: The original definition of P systems calls for rules to be applied in a maximally parallel fashion. However, in some cases a sequential model may be a more reasonable assumption. Here we study the computational power of different variants of sequential P systems. Initially we look at cooperative systems operating on symbol objects and without prioritized rules, but which allow membrane dissolution and bounded creation rules. We show that they are equivalent to vector addition systems …and, hence, nonuniversal. When these systems are used as language acceptors, they are equivalent to communicating P systems which, in turn, are equivalent to partially blind multicounter machines. In contrast, if such cooperative systems are allowed to create an unbounded number of new membranes (i.e., with unbounded membrane creation rules) during the course of the computation, then they become universal. We then consider systems with prioritized rules operating on symbol objects. We show two types of results: there are sequential P systems that are universal and sequential P systems that are nonuniversal. In particular, both communicating and cooperative P systems are universal, even if restricted to 1-deterministic systems with one membrane. However, the reachability problem for multi-membrane catalytic P systems with prioritized rules is NP-complete and, hence, these systems are nonuniversal. Show more

Keywords: Sequential P system, 1-deterministic P system, communicating P system, catalytic system, vector addition system, partially blind counter machine

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 133-152, 2006

Authors: Ilie, Lucian | Popescu, Cristian

Article Type: Research Article

Abstract: Viruses compress their genome to reduce space. One of the main techniques is overlapping genes. We model this process by the shortest common superstring problem. We give an algorithm for computing optimal solutions which is slow in the number of strings but fast (linear) in their total length. This algorithm is used for a number of viruses with relatively few genes. When the number of genes is larger, we compute approximate solutions using the greedy algorithm …which gives an upper bound for the optimal solution. We give also a lower bound for the shortest common superstring problem. The results obtained are then compared with what happens in nature. Remarkably, the compression obtained by viruses is very close to the one achieved by modern computers. Show more

Keywords: Virus, viral genome, genome compression, overlapping genes, shortest common superstring problem, approximate solution, lower bound

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 153-164, 2006

Authors: Kari, Lila | Losseva, Elena

Article Type: Research Article

Abstract: We introduce a type of substitution operation inspired by errors occurring in biologically encoded information. We derive the closure properties of language families in the Chomsky hierarchy under these substitution operations. Moreover, we consider some language equations involving these operations and investigate decidability of the existence of solutions to such equations.

Keywords: Formal languages, Chomshy hierarchy, block substitution

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 165-178, 2006

Authors: Langille, Miika | Petre, Ion

Article Type: Research Article

Abstract: We investigate in this paper a simple intramolecular model for gene assembly in ciliates. Unlike the general intramolecular model, the folds that a micronuclear chromosome may form to assemble the genes is very restricted (minimal) here: between any two pointers there may be at most one coding block. It has been known that the general model is universal, being able to assemble any gene pattern (to sort any signed permutation). The simple model on the other …hand is not universal: there exist signed permutations that cannot be sorted in this model. Remarkably though, all known micronuclear gene patterns in ciliates can indeed be assembled in the simple model. We prove in this paper that while the general model is non-deterministic, the simple model is "weakly deterministic": any gene pattern either has only successful or only unsuccessful sorting strategies. Moreover, although different strategies may lead to different permutations for the same input, these final results have the same structure. Show more

Keywords: Gene assembly, signed permutations, simple operations, determinism

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 179-190, 2006

Authors: Manea, Florin | Mitrana, Victor | Voinescu, Daniel-Claudian

Article Type: Research Article

Abstract: In this paper we continue the study on synchronized shuffle started in [5] by introducing the condition that the two words which are to be shuffled have to synchronize on a predefined set of backbones. As far as the language-theoretic properties of this operation are concerned, we prove that in a trio the closure under shuffle is equivalent to the closure under synchronized shuffle on a regular set of backbones. Based on this result we show …that a set of backbones is regular if and only if the synchronized shuffle of every two regular languages on that set is also regular. Some relationships between this operation and the synchronized shuffle operations introduced in [5] are presented and some open problem are finally discussed. Show more

Keywords: Shuffle, synchronized shuffle, backbone, synchronized shuffle on backbones, formal languages

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 191-202, 2006

Authors: Marcus, Solomon

Article Type: Research Article

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 203-204, 2006

Authors: Mateescu, Alexandru | Freund, Rudolf

Article Type: Research Article

Abstract: We investigate the problem of finding monoids that recognize languages of the form L_1 ⋈_T L_2 where T is an arbitrary set of routes. We present a uniform method based on routes to find such monoids. Many classical operations from the theory of formal languages, such as catenation, bi-catenation, simple splicing, shuffle, literal shuffle, and insertion are shown to be just particular instances of the operation ⋈_T …. Show more

Keywords: Monoid, route, Schützenberger product, shuffle

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 205-211, 2006

Authors: Păun, Gheorghe | Păun, Radu

Article Type: Research Article

Abstract: With inspiration from the economic reality, where numbers are basic entities to work with, we propose a genuinely new kind of P systems, where numerical variables evolve, starting from initial values, by means of production functions and repartition protocols. We prove that non-deterministic systems of this type, using polynomial production functions, characterize the Turing computable sets of natural numbers, while deterministic systems, with polynomial production functions having non-negative coefficients, compute strictly more …than semilinear sets of natural numbers. A series of research topics to be addressed in this framework are mentioned. Show more

Keywords: Membrane computing, economics, Turing computability, universality

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 213-227, 2006

Authors: Paz, Azaria

Article Type: Research Article

Abstract: The relationship between graphoid independency relations (defined in the text) and such relations induced by Probabilistic Distributions (PD) with binary random variables is investigated. It is shown that there are axioms that are sound for a subset of PD-induced relations with binary variables and are independent of the Graphoid axioms (cannot be logically derived from those axioms).

Keywords: Graphoids, probabilistic distributions, independency relations

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 229-236, 2006

Authors: Santean, Nicolae | Yu, Sheng

Article Type: Research Article

Abstract: Bimachines are important conceptual tools used for the characterization of rational word functions (realized by single-valued transducers). Despite the attention received in the past, these sequential machines are far from being exhaustively studied. A natural question which has not been addressed so far is what family of transductions are realized by bimachines that operate nondeterministically. We show that these machines characterize input-unambiguous (IU) rational transductions, i.e., those transductions that can be written …as a composition of rational functions and finite substitutions. Two more families of rational transductions are defined and related in a natural way to IU transductions: input-deterministic transductions and rational transductions with finite codomain (FC). We have shown that FC transductions are recognizable and that they can be expressed as finite union of subsequential functions. Moreover, they can be realized by nondeterministic bimachines. Finally, we have defined the so called restricted nondeterministic bimachines and shown that, surprisingly, they are more powerful than nondeterministic bimachines: they characterize exactly the family of finitely ambiguous rational transductions. Show more

Keywords: Finite transducer, unambiguous automaton, nondeterministic bimachine, rational function, finite substitution

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 237-264, 2006

Authors: Şerbănuţă, Virgil Nicolae | Şerbănuţă, Traian Florin

Article Type: Research Article

Abstract: We deal with the notion of M-unambiguity [5] in connection with the Parikh matrix mapping introduced by Mateescu and others in [7]. M-unambiguity is studied both in terms of words and matrices and several sufficient criteria for M-unambiguity are provided in both cases, nontrivially generalizing the criteria based on the γ-property introduced by Salomaa in [15]. Also, the notion of M-unambiguity with respect to a word is defined in connection with the extended Parikh matrix morphism …[16] and some of the M-unambiguity criteria are lifted from the classical setting to the extended one. This paper is a revised and extended version of [17]. Show more

Keywords: Subword, scattered subword, Parikh matrix, ambiguity

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 265-283, 2006

Authors: Stefanescu, Gheorghe

Article Type: Research Article

Abstract: We present a model and a core programming language appropriate for modeling and programming interactive computing systems. The model consists of rv-systems (interactive systems with registers and voices); it includes register machines, is space-time invariant, is compositional, may describe computations extending in both time and space, and is applicable to open, interactive systems. To achieve modularity in space the model uses voices (a voice is the time dual of a register) – they provide a high …level organization of temporal data and are used to describe interaction interfaces of processes. The programming language uses novel techniques for syntax and semantics to support computation in space paradigm. We describe rv-programs and base their syntax and operational semantics on FIS-es (finite interactive systems) and their grid languages (a FIS is a kind of 2-dimensional automaton specifying both control and interaction used in rv-programs). We also present specification techniques for rv-systems, using relations between input registers and voices and their output counterparts. The paper includes simple specifications for an OO-system and for an interactive game. Show more

Keywords: Interactive systems, programming languages, syntax, semantics, temporal specifications, registers, voices, object-oriented systems, finite interactive systems, rv-systems, rv-programs, grids, space-time duality

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 285-305, 2006

Authors: Vaida, Dragoş

Article Type: Research Article

Abstract: This note begins a study of some elementary properties related to the order structures applied in the algebraic approach to processes semantics. The support examples come from the partially additive semantics developed by Steenstrup (1985) and Manes and Arbib (1986) and from process algebra of Baeten and Weijland (1990). The main sources for the algebraic theory are F.A. Smith (1966) and Golan (1999). We show that different properties can be extended to partially additive distributive algebras …more general than sum-ordered partial semirings. One establishes that the support examples constitute multilattices, in the sense of Benado (1955). By the examples, the ordering considered, and the references, this preliminary study is related to Rudeanu et al. (2004) and to the algebraic approach to languages due to Mateescu, e.g., (1996), (1989), (1994). Show more

Keywords: Partial additive semantics, process algebra, semirings

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 307-319, 2006