Searching for just a few words should be enough to get started. If you need to make more complex queries, use the tips below to guide you.
Purchase individual online access for 1 year to this journal.
Price: EUR 410.00Impact Factor 2024: 0.4
Fundamenta Informaticae is an international journal publishing original research results in all areas of theoretical computer science. Papers are encouraged contributing:
- solutions by mathematical methods of problems emerging in computer science
- solutions of mathematical problems inspired by computer science.
Topics of interest include (but are not restricted to): theory of computing, complexity theory, algorithms and data structures, computational aspects of combinatorics and graph theory, programming language theory, theoretical aspects of programming languages, computer-aided verification, computer science logic, database theory, logic programming, automated deduction, formal languages and automata theory, concurrency and distributed computing, cryptography and security, theoretical issues in artificial intelligence, machine learning, pattern recognition, algorithmic game theory, bioinformatics and computational biology, quantum computing, probabilistic methods, & algebraic and categorical methods.
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
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
USA
Tel: +1 703 830 6300
Fax: +1 703 830 2300
sales@iospress.com
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
IOS Press
Nieuwe Hemweg 6B
1013 BG Amsterdam
The Netherlands
Tel: +31 20 688 3355
Fax: +31 20 687 0091
info@iospress.nl
For editorial issues, permissions, book requests, submissions and proceedings, contact the Amsterdam office info@iospress.nl
Inspirees International (China Office)
Ciyunsi Beili 207(CapitaLand), Bld 1, 7-901
100025, Beijing
China
Free service line: 400 661 8717
Fax: +86 10 8446 7947
china@iospress.cn
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
如果您在出版方面需要帮助或有任何建, 件至: editorial@iospress.nl