Fundamenta Informaticae - Volume 150, issue 2

Authors: Bozapalidis, Symeon | Rahonis, George

Article Type: Research Article

Abstract: We consider stochastic systems of equations of tree series, i.e., systems of equations whose right-hand sides are stochastic tree polynomials. We obtain their least solutions in arbitrary substochastic algebras, using both the [IO] - and OI -substitution mode. In the term algebra, we show that the consistency problem of the least [IO] - and OI -solutions is decidable, by reducing it to the consistency problem of stochastic context-free grammars. We prove a Kleene type theorem for the components of the least OI -solutions. The folklore Mezei-Wright result stating the coincidence of the components of least OI -solutions and behaviors of …tree automata fails in the stochastic setup. As an application of our theory, we prove a Kleene theorem for the class of series generated by stochastic context-free grammars. Show more

Keywords: Stochastic algebras, systems of stochastic trees series, stochastic context-free grammars

DOI: 10.3233/FI-2017-1463

Citation: Fundamenta Informaticae, vol. 150, no. 2, pp. 143-177, 2017

Authors: Gu, Ke | Jia, Weijia | Zhang, Jianming

Article Type: Research Article

Abstract: Multi-proxy signature is a variant of proxy signature, which allows that a delegator (original signer) may delegate his signing rights to many proxy signers. Comparing with proxy signatures, multi-proxy signatures can effectively prevent that some of proxy signers abuse signing rights. Also, with the rapid development of identity-based cryptography, identity-based multi-proxy signature (IBMPS) schemes have been proposed. Comparing with proxy signature based on public key cryptography, IBMPS can simplify key management and be used for more applications. Presently, many identity-based multi-proxy signature schemes have been proposed, but most of them are constructed in the random oracle model. Also, the existing …security model for identity-based multi-proxy signature is not enough complete according to the Boldyreva et al.’s work. In this paper, we present a framework for IBMPS on n + 1 users (n is the number of proxy signers participating in signing), and show a detailed security model for IBMPS. Under our framework, we present an identity-based multi-proxy signature scheme in the standard model. Comparing with other identity-based multi-proxy signature schemes, the proposed scheme has more complete security. Show more

Keywords: multi-proxy signature, identity-based cryptography, identity-based multi-proxy signature, security model

DOI: 10.3233/FI-2017-1464

Citation: Fundamenta Informaticae, vol. 150, no. 2, pp. 179-210, 2017

Authors: Juneam, Nopadon | Kantabutra, Sanpawat

Article Type: Research Article

Abstract: The process of merging two arbitrary partitions of a given finite set 𝒰 of n elements is known as coarsest refinement . In the COARSEST REFINEMENT PROBLEM we are given two arbitrary partitions 𝒳, 𝒴 of the set 𝒰 such that 𝒳 = {𝒳1 , 𝒳2 , ..., 𝒳x } and 𝒴 = {𝒴1 , 𝒴2 , ..., 𝒴y }, and determine a new partition 𝒵 = {𝒵1 , 𝒵2 , ..., 𝒵z } such that each is a common non-empty subset of some 𝒳a ∈ 𝒳 and some 𝒴b …∈ 𝒴 and |𝒵| is as small as possible. This article describes a resource-efficient parallel algorithm to solve this problem. More specifically, we show that a coarsest refinement can be computed in O (t (n ) + log n ) parallel time using max { n log n , p ( n ) } processors, where t (n ) denotes the running time of a parallel stable sorting algorithm that uses p (n ) processors on an EREW PRAM. This result depends on t (n ) and p (n ). We give a table that shows the best known time and processor complexities for a parallel stable sorting algorithm. If the parallel stable sorting algorithms by Ajtai et al., Cole, and Leighton are used, the coarsest refinement can be computed in O (log n ) parallel time using n processors on an EREW PRAM. On the other hand, if the parallel stable sorting algorithm by Bahig et al. is used, the coarsest refinement can be computed in O ( log n log ( n log n ) ) parallel time using n log n processors on an EREW PRAM. In addition, we show that on, a RAM machine, our parallel algorithm runs as asymptotically efficient as the fastest known sequential algorithm. Show more

Keywords: PRAM algorithms, parallel computation, coarsest refinement, partition refinement

DOI: 10.3233/FI-2017-1465

Citation: Fundamenta Informaticae, vol. 150, no. 2, pp. 211-220, 2017

Authors: Przybyszewski, Andrzej W. | Polkowski, Lech T.

Article Type: Research Article

Abstract: There are two very different approaches to understand functioning of the brain. First, there is a huge progress in the research of the neurological and neurophysiological properties of different brain substructures, circuits, networks, single cells, synapses and their molecular properties. It contributes to the progress of research in the fields of basic medical sciences and the dramatic increase in average life expectancy. On the another side that does not directly follows neurological developments, it is our introspection related to individual ways of thinking in order to solve different problems that also involve human creativity (cognitive theory of mind). We use …many diverse ways of thinking, and they depend on different circumstances. Especially interesting are influences of intuition, feelings and emotions on our creativity, which is in a large part are also related to the social interactions (affective empathy). In this work, we formalise emotional scales and transfer of emotions between individuals (social emotional thinking). We also demonstrate a continuity of the emotion transfer mappings, and an importance of the interactions between emotional faces. It is not only human specific to show and to react to face emotions, but strong and wide human social interactions are based on the precise emotional social thinking. By measuring critical values of face deformations that may influence mutual emotions, we can test precision and tolerance of human visual and emotional systems. By introduction indiscernibility relations between individual reading of face parts deformation, we have used rough set theory to probe social emotional thinking. As one of us have demonstrated that the visual system has properties that follows rough set theory (cognitive theory of mind), this work extends this concept to the social emotional interactions (cognitive and affective theory of mind). As in modern world IT - information technology - has became driving factor in the process of globalisation by creating effective channels of information exchange; hence it becomes extremely important to analyse emotional meaning (cognitive empathy) for this vast information flow. By using as described here, rough set theory to determine, which parts of information have significant emotional influence, our model may give grounds to increase the collective well-being. Show more

Keywords: amygdala, insula, similarities, driver and modulatory logical rules, cognitive empathy, affective empathy

DOI: 10.3233/FI-2017-1466

Citation: Fundamenta Informaticae, vol. 150, no. 2, pp. 221-230, 2017

Authors: Yu, Yang | Wu, Tingfang | Xu, Jinbang | Wang, Yanfeng | He, Juanjuan

Article Type: Research Article

Abstract: Spiking neural (SN, for short) P systems are a class of computation models inspired from the way in which neurons communicate by exchanging spikes. SN P systems with homogenous neurons and synapses are a new variant of SN P systems, where the spiking and forgetting rules are placed on synapses instead of in neurons and each synapse has the same set of spiking and forgetting rules. Recent studies illustrated that this variant of SN P systems is Turing universal as both number generating and accepting devices. In this note, we prove that SN P systems with homogenous neurons and synapses …without the feature of delay are also Turing universal. This result gives a positive answer to an open problem formulated in [K. Jiang, et al. Neurocomputing 171(2016) 1548-1555] “whether SN P systems with homogenous neurons and synapses are Turing universal when the feature of delay is not used”. Show more

Keywords: Bio-inspired computing, Membrane computing, Spiking neural P system, Small universal system, Turing completeness

DOI: 10.3233/FI-2017-1467

Citation: Fundamenta Informaticae, vol. 150, no. 2, pp. 231-240, 2017