Fundamenta Informaticae - Volume 168, issue 1

Authors: Jiang, Suxia | Wang, Yanfeng | Xu, Fei | Deng, Junli

Article Type: Research Article

Abstract: Communication P systems with channel states (CC P systems, for short) are a class of distributed parallel computing models, where communication (symport/antiport) rules associated with channel states are executed in a sequential manner on membrane channels. In this work, communication P systems with channel states working in flat maximally parallel manner are considered and the computational power is investigated. Specifically, it is proved that communication P systems with channel states using symport rules of length two are Turing universal when having one membrane and any number of channel states, or two membranes and three channel states. Furthermore, membrane division is …introduced into communication P systems with channel states, communication P systems with channel states and membrane division (CCD P systems, for short) are proposed. We provide a uniform solution to the Hamiltonian path problem (HPP) by CCD P systems working in a flat maximally parallel manner. Show more

Keywords: Bio-inspired computing, Membrane computing, Cell-like P system, Symport/antiport rule, Channel state, Flat maximal parallelism

DOI: 10.3233/FI-2019-1821

Citation: Fundamenta Informaticae, vol. 168, no. 1, pp. 1-24, 2019

Authors: Kłopotek, Mieczysław A.

Article Type: Research Article

Abstract: This paper, constituting an extension to the conference paper [1], corrects the proof of the Theorem 2 from the Gower’s paper [2, page 5]. The correction is needed in order to establish the existence of the kernel function used commonly in the kernel trick e.g. for k -means clustering algorithm, on the grounds of distance matrix. The correction encompasses the missing if-part proof and dropping unnecessary conditions.

Keywords: kernel trick, k-means, Gower Theorem, Euclidean embedding, kernel function

DOI: 10.3233/FI-2019-1822

Citation: Fundamenta Informaticae, vol. 168, no. 1, pp. 25-43, 2019

Authors: Koga, Toshihiro

Article Type: Research Article

Abstract: Let ∑ be an alphabet which has at least two symbols. The density of L ⊆ ∑* is defined as D (L ) := limn |L ∩ ∑n |/|∑n | ∈ [0, 1], provided that the limit exists. In 2015, R. Sin’ya has discovered an interesting relation between regular languages and their densities: If L ⊆ ∑* is a regular language, then D (L ) = 0 if and only if there exists s ∈ ∑* such that ∑*s ∑* ∩ L = ø. In this paper, we give a simple …proof of this theorem, obtaining it as a simple consequence of the pumping lemma for regular languages. Show more

Keywords: Formal languages, Regular languages, Density

DOI: 10.3233/FI-2019-1823

Citation: Fundamenta Informaticae, vol. 168, no. 1, pp. 45-49, 2019

Authors: Marquer, Yoann

Article Type: Research Article

Abstract: According to the Church-Turing Thesis, effectively calculable functions are functions computable by a Turing machine. Models that compute these functions are called Turing-complete. For example, we know that common imperative languages (such as C , Ada or Python ) are Turing complete (up to unbounded memory). Algorithmic completeness is a stronger notion than Turing-completeness. It focuses not only on the input-output behavior of the computation but more importantly on the step-by-step behavior. Moreover, the issue is not limited to partial recursive functions, it applies to any set of functions. A model could compute all the desired functions, but …some algorithms (ways to compute these functions) could be missing (see [10, 27] for examples related to primitive recursive algorithms). This paper’s purpose is to prove that common imperative languages are not only Turing-complete but also algorithmically complete, by using the axiomatic definition of the Gurevich’s Thesis and a fair bisimulation between the Abstract State Machines of Gurevich (defined in [16]) and a version of Jones’ While programs. No special knowledge is assumed, because all relevant material will be explained from scratch. Show more

Keywords: Algorithm, ASM, Completeness, Computability, Imperative, Simulation

DOI: 10.3233/FI-2019-1824

Citation: Fundamenta Informaticae, vol. 168, no. 1, pp. 51-77, 2019

Authors: Urban, Roman | Anisimowicz, Hubert

Article Type: Research Article

Abstract: In 2010 Durda, Caron, and Buchanan published a paper in INFOR: Information systems and Operational Research , entitled: An application of operational research to computational linguistics: Word ambiguity. In this article the authors developed “a new measure of word ambiguity (e.g., homonymy and polysemy) for use in psycholinguistic research”. In our work we propose some modification of their algorithm.

Keywords: Word ambiguity, homonymy, polysemy, clustering algorithms, Gomory-Hu algorithm, genetic algorithms

DOI: 10.3233/FI-2019-1825

Citation: Fundamenta Informaticae, vol. 168, no. 1, pp. 79-88, 2019