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: Męski, Artur | Koutny, Maciej | Penczek, Wojciech
Article Type: Research Article
Abstract: Reaction systems are a formal model for computational processes inspired by the functioning of the living cell. This paper introduces reaction systems with discrete concentrations, which are an extension of reaction systems allowing for quantitative modelling. We demonstrate that although reaction systems with discrete concentrations are semantically equivalent to the original qualitative reaction systems, they provide much more succinct representations in terms of the number of entities being used. We define a variant of Linear Time Temporal Logic interpreted over models of reaction systems with discrete concentrations. We provide its suitable encoding in SMT, together with bounded model checking, and …present experimental results demonstrating the scalability of the verification method for reaction systems with discrete concentrations. Show more
Keywords: reaction systems, bounded model checking, linear time temporal logic
DOI: 10.3233/FI-2017-1567
Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 289-306, 2017
Authors: Nobile, Marco S. | Porreca, Antonio E. | Spolaor, Simone | Manzoni, Luca | Cazzaniga, Paolo | Mauri, Giancarlo | Besozzi, Daniela
Article Type: Research Article
Abstract: Reaction systems represent a theoretical framework based on the regulation mechanisms of facilitation and inhibition of biochemical reactions. The dynamic process defined by a reaction system is typically derived by hand, starting from the set of reactions and a given context sequence. However, this procedure may be error-prone and time-consuming, especially when the size of the reaction system increases. Here we present HERESY, a simulator of reaction systems accelerated on Graphics Processing Units (GPUs). HERESY is based on a fine-grained parallelization strategy, whereby all reactions are simultaneously executed on the GPU, therefore reducing the overall running time of the simulation. …HERESY is particularly advantageous for the simulation of large-scale reaction systems, consisting of hundreds or thousands of reactions. By considering as test case some reaction systems with an increasing number of reactions and entities, as well as an increasing number of entities per reaction, we show that HERESY allows up to 29× speed-up with respect to a CPU-based simulator of reaction systems. Finally, we provide some directions for the optimization of HERESY, considering minimal reaction systems in normal form. Show more
Keywords: reaction systems, general-purpose GPU computing, high-performance computing, simulation
DOI: 10.3233/FI-2017-1568
Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 307-321, 2017
Authors: Okubo, Fumiya | Yokomori, Takashi
Article Type: Research Article
Abstract: New morphic characterizations in the form of a noted Chomsky-Schützenberger theorem are established for the classes of regular languages, of context-free languages and of languages accepted by chemical reaction automata. Our results include the following: (i) Each λ-free regular language R can be expressed as R = h (Tk ∩ FR ) for some 2-star language FR , an extended 2-star language Tk and a weak coding h . (ii) Each λ-free context-free language L can be expressed as L = h (Dn ∩ FL …) for some 2-local language FL and a projection h . (iii) A language L is accepted by a chemical reaction automaton iff there exist a 2-local language FL and a weak coding h such that L = h (Bn ∩ FL ), where Dn and Bn are a Dyck set and a partially balanced language defined over the n -letter alphabet, respectively. These characterizations improve or shed new light on the previous results. Show more
Keywords: Regular languages, Context-free languages, Chemical reaction automata, Morphic characterizations, Star languages, Local languages
DOI: 10.3233/FI-2017-1569
Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 323-341, 2017
Authors: Polkowski, Lech T.
Article Type: Research Article
Abstract: This work is dedicated to Profesor Andrzej Ehrenfeucht, the eleve of the Warsaw School of Logic and Mathematics on the occasion of His 85th Birthday. We propose to exploit certain of the milestone ideas created by this School and to apply them to data analysis in the framework of the rough set theory proposed by Professor Zdzisław Pawlak. To wit, we apply the idea of fractional truth states due to Jan Łukasiewicz, mereology created by Stanisław Leśniewski and the betweenness relation used by Alfred Tarski as one of primitive predicates in His axiomatization of Euclidean geometry. These ideas applied in …problems of approximate reasoning permit us to formalize calculus of granules of knowledge and use it in preprocessing of data before applying a classification algorithm. Introduction of a mereological version of betweenness relation to data allows for partitioning of data into the kernel and the residuum, both sub-data sets providing a faithful representation of the whole data set and reducing the size of data without any essential loss of accuracy of classification. In the process of algorithmic construction of the partition of data into the kernel and the residuum, we exploit the Dual Indiscernibility Matrix which further allows us to introduce notions of a pair classifier and, more generally, k -classifier yet to be studied. Show more
Keywords: truth values, mereology, betweenness relation, rough sets, shuffled simplices, dual indiscernibility matrix, kernel, residuum, pair classifier
DOI: 10.3233/FI-2017-1570
Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 343-358, 2017
Authors: Rogers, Trent A. | Seki, Shinnosuke
Article Type: Research Article
Abstract: RNA sequences start folding immediately as they are synthesized by RNA polymerase (cotranscriptional folding). The oritatami system (OS) is a novel mathematical model to study computational aspects of cotranscriptional folding. In this paper, we first provide a survey throughout existing research topics and results on oritatami systems and offer research directions of significance. Simulation of an oritatami system in a different ratio (delay) of transcription speed to the speed of folding is one of them. We will introduce a simple notion of simulation, and prove that there is an OS of delay δ that cannot be simulated by any …oritatami system at larger delay. Show more
Keywords: Oritatami system, RNA cotranscriptional folding, Molecular self-assembly, Turing universality, Simulation
DOI: 10.3233/FI-2017-1571
Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 359-372, 2017
Authors: Valencia-Cabrera, Luis | Orellana-Martín, David | Martínez-del-Amor, Miguel A. | Riscos-Núñez, Agustín | Pérez-Jiménez, Mario J.
Article Type: Research Article
Abstract: Membrane computing is a computing paradigm providing a class of distributed parallel computing devices of a biochemical type whose process units represent biological membranes. In the cell-like basic model, a hierarchical membrane structure formally described by a rooted tree is considered. It is well known that families of such systems where the number of membranes can only decrease during a computation (for instance by dissolving membranes), can only solve in polynomial time problems in class P . P systems with active membranes is a variant where membranes play a central role in their dynamics. In the seminal version, membranes …have an electrical polarization (positive, negative, or neutral) associated in any instant, and besides being dissolved, they can also replicate by using division rules. These systems are computationally universal, that is, equivalent in power to deterministic Turing machines, and computationally efficient, that is, able to solve computationally hard problems in polynomial time. If polarizations in membranes are removed and dissolution rules are forbidden, then only problems in class P can be solved in polynomial time by these systems (even in the case when division rules for non-elementary membranes are permitted). In that framework it has been shown that by considering minimal cooperation (left-hand side of such rules consists of at most two symbols) and minimal production (only one object is produced by the application of such rules) in object evolution rules, such systems provide efficient solutions to NP -complete problems. In this paper, minimal cooperation and minimal production in communication rules instead of object evolution rules is studied, and the computational efficiency of these systems is obtained in the case where division rules for non-elementary membranes are permitted. Show more
Keywords: Membrane Computing, polarizationless P systems with active membranes, cooperative rules, the P versus NP problem, SAT problem
DOI: 10.3233/FI-2017-1572
Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 373-385, 2017
Article Type: Other
Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 387-388, 2017
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
USA
Tel: +1 703 830 6300
Fax: +1 703 830 2300
[email protected]
For editorial issues, like the status of your submitted paper or proposals, write to [email protected]
IOS Press
Nieuwe Hemweg 6B
1013 BG Amsterdam
The Netherlands
Tel: +31 20 688 3355
Fax: +31 20 687 0091
[email protected]
For editorial issues, permissions, book requests, submissions and proceedings, contact the Amsterdam office [email protected]
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
[email protected]
For editorial issues, like the status of your submitted paper or proposals, write to [email protected]
如果您在出版方面需要帮助或有任何建, 件至: [email protected]