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: Gao, Yuan | Salomaa, Kai | Yu, Sheng
Article Type: Research Article
Abstract: We consider the transition complexity of regular languages based on the incomplete deterministic finite automata. We establish tight bounds for the transition complexity of Boolean operations, in the case of union the upper and lower bounds differ by a multiplicative constant two. We show that the transition complexity results for union and complementation are very different from the state complexity results for the same operations. However, for intersection, the transition complexity bounds turn out to be similar to the corresponding bounds for state complexity.
Keywords: transition complexity, deterministic finite automaton, incomplete automaton, regular languages, Boolean operations
DOI: 10.3233/FI-2011-533
Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 143-158, 2011
Authors: Holzer, Markus | Klein, Andreas | Kutrib, Martin | Ruepp, Oliver
Article Type: Research Article
Abstract: We show that the popular pencil puzzle NURIKABE is intractable from the computational complexity point of view, that is, it is NP-complete, even when the involved numbers are 1 and 2 only. To this end, we show how to simulate Boolean gates by the puzzle under consideration. Moreover, we also study some NURIKABE variants, which remain NP-complete, too.
DOI: 10.3233/FI-2011-534
Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 159-174, 2011
Authors: Honkala, Juha
Article Type: Research Article
Abstract: We study the DT0L sequence equivalence problem for marked morphisms. We show that to decide this problem it is enough to consider initial terms involving at most 2n morphisms where n is the cardinality of the underlying alphabet.
Keywords: DT0L system, DT0L sequence equivalence problem, marked morphism, decidability
DOI: 10.3233/FI-2011-535
Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 175-182, 2011
Authors: Ilie, Lucian | Smyth, William F.
Article Type: Research Article
Abstract: Unique substrings appear scattered in the stringology literature and have important applications in bioinformatics. In this paper we initiate a study of minimum unique substrings in a given string; that is, substrings that occur exactly once while all their substrings are repeats. We discover a strong duality between minimum unique substrings and maximum repeats which, in particular, allows fast computation of one from the other. We give several optimal algorithms, some of which are very simple and efficient. Their combinatorial properties are investigated and a number of open problems are proposed.
DOI: 10.3233/FI-2011-536
Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 183-195, 2011
Authors: Karhumäki, Juhani | Saarela, Aleksi
Article Type: Research Article
Abstract: We show by a simple reduction that the unique decipherability problem in the language monoid of regular languages over a non-unary alphabet is undecidable.
DOI: 10.3233/FI-2011-537
Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 197-200, 2011
Authors: Kari, Lila | Seki, Shinnosuke | Kopecki, Steffen
Article Type: Research Article
Abstract: Hairpin completion is an abstract operation modeling a DNA bio-operation which receives as input a DNA strand w = xαy\bar{α}, and outputs w' = xαy\bar{α}\bar{x}, where \bar{x} denotes the Watson-Crick complement of x. In this paper, we focus on the problem of finding conditions under which the iterated hairpin completion of a given word is regular. According to the numbers of words α and \bar{α} that initiate hairpin completion and how they are scattered, we classify the set of all words w. For some basic classes of words w containing small numbers of occurrences of α and \bar{α}, we prove …that the iterated hairpin completion of w is regular. For other classes with higher numbers of occurrences of α and \bar{α}, we prove a necessary and sufficient condition for the iterated hairpin completion of a word in these classes to be regular. Show more
Keywords: combinatorics on words, commutativity of words, DNA computing, iterated hairpin completion, regularity test, single-primer hairpin completion
DOI: 10.3233/FI-2011-538
Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 201-215, 2011
Authors: Kleijn, Jetty | Koutny, Maciej
Article Type: Research Article
Abstract: In membrane systems, biochemical reactions taking place in the compartments of a cell are abstracted to evolution rules that specify which and how many objects are consumed and produced. The recently proposed reaction systems also investigate processes carried by biochemical reactions, but the resulting computational model is remarkably different. A key difference is that in reaction systems, biochemical reactions are modeled using a qualitative rather than a quantitative approach. In this paper, we introduce so-called set membrane systems, a variant of membrane systems with qualitative evolution rules inspired by reaction systems. We then relate set membrane systems to Petri nets …which leads to a new class of Petri nets: set-nets with localities. This Petri net model provides a faithful match with the operational semantics of set membrane systems. Show more
Keywords: membrane system, reaction system, biochemistry, natural computing, Petri net, set-net, locality, inhibitor, promoter
DOI: 10.3233/FI-2011-539
Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 217-230, 2011
Authors: Kunc, Michal | Okhotin, Alexander
Article Type: Research Article
Abstract: The number of states in a two-way nondeterministic finite automaton (2NFA) needed to represent intersection of languages given by an m-state 2NFA and an n-state 2NFA is shown to be at least m+n and at most m+n+1. For the union operation, the number of states is exactly m+n. The lower bound is established for languages over a one-letter alphabet. The key point of the argument is the following number-theoretic lemma: for all m, n ≥ 2 with m, n ≠ 6 (and with finitely many other exceptions), there exist partitions m = p1 +. . .+ pk and …n = q1 +. . .+ql , where all numbers p1 , . . . , pk , q1 , . . . , ql ≥ 2 are powers of pairwise distinct primes. For completeness, an analogous statement about partitions of any two numbers m, n ∉ {4, 6} (with a few more exceptions) into sums of pairwise distinct primes is established as well. Show more
Keywords: Finite automata, two-way automata, state complexity, partitions into sums of primes
DOI: 10.3233/FI-2011-540
Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 231-239, 2011
Authors: Morita, Kenichi
Article Type: Research Article
Abstract: A two-way reversible multi-head finite automaton (RMFA) is introduced as a simple model of reversible computing, and its language accepting capability is studied. We show that various non-regular context-free languages, and non-context-free context-sensitive languages are accepted by RMFAs with a few heads. For example, we give an RMFA with three heads that accepts the language consisting of all words whose length is a prime number. A construction method of a garbage-less RMFA from a given RFMA is also shown.
Keywords: reversible computing, multi-head finite automaton, language recognition
DOI: 10.3233/FI-2011-541
Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 241-254, 2011
Authors: Okubo, Fumiya | Yokomori, Takashi
Article Type: Research Article
Abstract: Hairpin completion and its variant called bounded hairpin completion are operations on formal languages, inspired by a hairpin formation in molecular biology. Another variant called hairpin lengthening has been recently introduced, and the related closure properties and algorithmic problems concerning several families of languages have been studied. In this paper, we introduce a new operation of this kind, called hairpin incompletion which is not only an extension of bounded hairpin completion, but also a restricted (bounded) variant of hairpin lengthening. Further, the hairpin incompletion operation provides a formal language theoretic framework that models a bio-molecular technique nowadays known as Whiplash …PCR. We study the closure properties of language families under both the operation and its iterated version. We show that a family of languages closed under intersection with regular sets, concatenation with regular sets, and finite union is closed under one-sided iterated hairpin incompletion, and that a family of languages containing all linear languages and closed under circular permutation, left derivative and substitution is also closed under iterated hairpin incompletion. Show more
DOI: 10.3233/FI-2011-542
Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 255-269, 2011
Authors: Pan, Linqiang | Wang, Jun | Hoogeboom, Hendrik Jan
Article Type: Research Article
Abstract: In a biological system, if a long enough time interval is given, an enabled chemical reaction will finish its reaction in the given time interval. With this motivation, it is natural to impose a bound on the time interval when an enabled spiking rule in a spiking neural P system (SN P system, for short) remains unused. In this work, a new working mode of SN P systems is defined, which is called limited asynchronous mode. In an SN P system working in limited asynchronous mode, if a rule is enabled at some step, this rule is not obligatorily used. …From this step on, if the unused rule may be used later, it should be used in the given time interval. If further spikes make the rule non-applicable, then the computation continues in the new circumstances. The computation result of a computation in an SN P system working in limited asynchronous mode is defined as the total number of spikes sent into the environment by the system. It is proved that limited asynchronous SN P systems with standard spiking rules are universal. If the number of spikes present in each neuron of a limited asynchronous SN P system with standard spiking rules is bounded during a computation, then the power of a limited asynchronous SN P system with standard spiking rules falls drastically, and we get a characterization of semilinear sets of numbers. Show more
Keywords: Membrane computing, Spiking neural P system, Asynchronous mode, Turing Computability
DOI: 10.3233/FI-2011-543
Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 271-293, 2011
Authors: Pérez-Jiménez, Mario J. | Riscos-Núñez, Agustín | Rius-Font, Miquel | Romero-Campero, Francisco J.
Article Type: Research Article
Abstract: In 1936 A. Turing showed the existence of a universal machine able to simulate any Turing machine given its description. In 1956, C. Shannon formulated for the first time the problem of finding the smallest possible universal Turing machine according to some critera to measure its size such as the number of states and symbols. Within the framework of Membrane Computing different studies have addressed this problem: small universal symport/antiport P systems (by considering the number of membranes, the weight of the rules and the number of objects as a measure of the size of the system), small universal splicing …P systems (by considering the number of rules as a measure of the size of the system), and small universal spiking neural P systems (by considering the number of neurons as a measure of the size of the system). In this paper the problem of determining the smallest possible efficient P system is explicitly formulated. Efficiency within the framework of Membrane Computing refers to the capability of solving computationally hard problems (i.e. problems such that classical electronic computer cannot solve instances of medium/large size in any reasonable amount of time) in polynomial time. A descriptive measure to define precisely the notion of small P system is presented in this paper. Show more
Keywords: Membrane Computing, Small universal P Systems, Small effcient P systems, SAT problem
DOI: 10.3233/FI-2011-544
Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 295-308, 2011
Authors: Raghavan, Rama | Ramesh, H. | Gheorghe, Marian | Krishna, Shankara Narayanan
Article Type: Research Article
Abstract: Here we continue the study of bio-Turing machines introduced in [2] and further investigated in [17]. We introduce a restricted model of bio-Turing machine and we investigate its computational power, a hierarchy of languages accepted, and deterministic and nondeterministic variants. A comprehensive example illustrating the modelling power of the introduced machine ends the paper.
DOI: 10.3233/FI-2011-545
Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 309-320, 2011
Authors: Tran, Nicholas
Article Type: Research Article
Abstract: This paper introduces and studies two notions of easy sets without hard subsets: i) 𝒞-hollow sets are defined to be sets in P that have no 𝒞 – P subsets for (presumably) superclasses 𝒞 of P such as NP, PSPACE, E, NE, RE, etc.; and ii) 𝒞-scant sets are defined to be sets in P that have no many-one 𝒞-complete subsets. These sets complement well-studied objects in complexity such as P-printable sets, immune sets and complexity cores. First, characterizations of 𝒞-hollow sets and 𝒞-scant sets are obtained in terms of universally easy sets, introduced and studied in [7] as an …automatic method for generating easy instances of intractable problems. Second, the following results regarding existence of 𝒞-hollow sets are obtained: infinite NP-hollow tally (equivalently, P-printable) sets exist iff some nondeterministic time complexity class equals its deterministic counterpart; in contrast, infinite E/NE/RE-hollow sets do not exist. Finally, it is shown that P-printable-immune sets in P are 𝒞-scant for E and NE. Show more
DOI: 10.3233/FI-2011-546
Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 321-328, 2011
Authors: Verlan, Sergey | Margenstern, Maurice
Article Type: Research Article
Abstract: Splicing test tube systems are one of the first distributed computing models based on splicing. The model introduces (test) tubes where the splicing operation is applied, which are arranged in a communication network with filters that permits to redistribute the words between the tubes at each step. We show that the computational completeness can be achieved with two tubes when the communication graph does not have self-loops. We also construct a universal splicing test tube system with 2 tubes having 23 rules.
Keywords: Splicing, test tube systems, universality
DOI: 10.3233/FI-2011-547
Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 329-342, 2011
Authors: Yen, Hsu-Chun
Article Type: Research Article
Abstract: Although randomization often increases the degree of flexibility in system design, analyzing system properties in the probabilistic framework introduces additional difficulties and challenges in comparison with their nonprobabilistic counterparts. In this paper, we focus on probabilistic versions of two problems frequently encountered in discrete event systems, namely, the reachability and forbidden-state problems. Our main concern is to see whether there exists a (or for every) non-blocking or fair control policy under which a given finite- or infinite-state system can be guided to reach (or avoid) a set of goal states with probability one. For finite-state systems, we devise algorithmic approaches …which result in polynomial time solutions to the two problems. For infinite-state systems modelled as Petri nets, the problems are undecidable in general. For the class of persistent Petri nets, we establish a valuation approach through which the convergence behavior of a system is characterized, which in turn yields solutions to the reachability and forbidden-state problems. Show more
Keywords: Forbidden-state avoidance, Petri net, probabilistic controlled transition system, reachability
DOI: 10.3233/FI-2011-548
Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 343-359, 2011
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