GOVPH

 

Henry N. Adorna

Sex: Male

Education:

Doctor of Philosophy in Mathematics, University of the Philippines Diliman, 2002

Master of Science in Mathematics, University of the Philippines Diliman

Bachelor of Science in Mathematics, FEATI University

Field of Specialization

Biocomputing

Bioinformatics

Data mining

Directed graphs

Graph theory

Traffic information systems

Bibliographic systems

Researches:

 

Article title: Snapse: A Visual Tool for Spiking Neural P Systems

Authors: Aleksei Dominic C. Fernandez, Reyster M. Fresco, Francis George C. Cabarle, Ren Tristan A. de la Cruz, et al.

Publication title: Processes 9(1): 72, 2021

 

Abstract:

Spiking neural P (SN P) systems are models of computation inspired by spiking neurons and part of the third generation of neuron models. SN P systems are equivalent to Turing machines and are able to solve computationally hard problems using a space-time trade-off. Research in SN P systems theory is especially active, more so in recent years as more efforts are directed towards their real-world applications. Usually, SN P systems are represented visually as a directed graph and simulated through mainly text-based simulations or tables. Thus, there is a need for tools that can simulate and create SN P Systems in a visual and easy-to-use manner. Snapse is such a tool which aims to hasten the speed and ease at which researchers may create and experiment with SN P systems. Furthermore, visual tools such as Snapse can help further bring SN P systems outside of theoretical computer science.

Article title: Homogeneous spiking neural P systems with structural plasticity

Authors: Ren Tristan A. de la Cruz, Francis George C. Cabarle, Ivan Cedric H. Macababayao, Henry N. Adorna, et al.

Publication title: Journal of Membrane Computing 3:10-21, 2021

 

Abstract:

Spiking neural P system (SNP system) is a model of computation inspired by the mechanism of spiking neurons. An SNP system is a directed graph of neurons that can communicate with each other using an object known as a spike (the object spike represents action potential or nerve impulse). Spiking neural P systems with structural plasticity (SNPSP system) is a variant of the SNP system model. It incorporates the concept of structural plasticity to the SNP system model. SNPSP systems have the ability to add and delete connections between neurons. In SNPSP systems, the behavior of a neuron can be “programmed” by giving it a set of rules. Different set of rules will result in different behaviors. In this work, we show that it is possible to construct a universal SNPSP system where all the neurons in the system use the same set of rules. Such systems are called homogeneous SNPSP systems.

Full text available upon request to the author

Article title: A return to stochasticity and probability in spiking neural P systems

Authors: Prometheus Peter L. Lazo, Francis George C. Cabarle, Henry N. Adorna, Jan Michael C. Yap

Publication title: Journal of Membrane Computing 2021

 

Abstract:

This work continues the investigations of introducing probabilities to spiking neural P systems, SN P systems in short—membrane computing models inspired from biological spiking neurons. A particular interest for SN P systems in this work is the nondeterministic selection of applicable firing rules. Rules represent the possible reactions of a neuron to the number of electrical impulses, or spikes, present. Intuitively, having nondeterministic selection can be interpreted as having a random choice with equal probabilities for all options. This seems unnatural in some biological sense, since some reactions are more active than others in general as emphasized in Obtułowicz and Păun, BioSystems 70(2):107–121, 2003. Results found that the stochastic process introduced to the nondeterministic selection of firing rules also applies to application of rules in general whether the rule is for firing or forgetting and whether a single rule is applicable or multiple. This work proposes SN P systems with stochastic application of rules, ⋆SN P systems in short. SN P systems are variants which introduce a stochastic process a priori to the application of rules in SN P systems.

Full text available upon request to the author

Article title: A polynomial time algorithm for the 2-Poset Cover Problem

Authors: Ivy Ordanel, Proceso Fernandez Jr, Henry Adorna

Publication title: Information Processing Letters 169: 106106, 2021

 

Abstract:

Given a set ϒ of linear orders, we say that a poset H a< b=(V,<) is a halfspace of ϒ if its set of linear extensions L (H a< b)⊂ ϒ and a< L b for every L∈ L (H a< b) and b< L a for every L∈ ϒ∖ L (H a< b). In this paper, we devise an efficient algorithm to expand the halfspace and determine a maximal poset P in ϒ that supercovers it, that is, L (H a< b)⊆ L (P)⊆ ϒ. Moreover, the said algorithm paves the way for the improvement of the existing exponential running time solution in literature for the 2-Poset Cover Problem to a polynomial running time solution.

Full text available upon request to the author

Article title: Approximation and Computational Complexity of Some Hammock Variations of the Poset Cover Problem

Authors: Ivy D. Ordanel, Proceso L. Fernandez Jr, Richelle Ann B. Juayong, Henry N. Adorna

Publication title: INGENIARE-Revista Chilena de Ingeniería 28(1), 2020

 

Abstract:

Sequential data such as logs may contain a wealth of information that can be mined to discover knowledge about the objects in the data or about the system that generates the data. One interesting aspect of the objects in the data is their dependencies or ordering. The task of determining such is more commonly referred to as mining posets–a data mining task that is relevant in bioinformatics, process model mining, web mining, network management and intrusion detection, and preference-based service (Pei et al. 2006).

Full text available upon request to the author

Article title: Distributed computation of a k P systems with active membranes for SAT using clause completion

Authors: Kelvin Buño and Henry Adorna

Publication title: Journal of Membrane Computing 2: 108-120, 2020

 

Abstract:

In a work presented by Gazdag and Kolonits from 2013, it was shown that SAT can be solved in linear time in the number of variables using the clause completion method on a non-distributed P system with active membranes. A distributed P system with active membranes using the clause completion method solving SAT (denoted as k-𝛥(𝑛)Δ(n)) is presented in this work. k-𝛥(𝑛)Δ(n) is a weak uniform solution to SAT that runs in linear time with respect only to the number of variables, n, of the Boolean formula 𝜑φ. For the 2-component solution, 2-𝛥(𝑛)Δ(n), we show that the communication cost is constant. But, increasing the number of components in k-𝛥(𝑛)Δ(n), 𝑘≥3k≥3, would make the communication cost dependent on not just the number of components and the number of variables, but as well as the number of satisfying assignments to 𝜑φ. We report that an exponential amount of resources (in terms of alphabet size and rules) are necessary to construct k-𝛥(𝑛)Δ(n) solving SAT to obtain these reasonable communication costs.

Full text available upon request to the author

Article title: A survey of results on evolution–communication P systems with energy

Authors: Richelle Ann B. Juayong, Henry N. Adorna

Publication title: Journal of Membrane Computing 2(1): 59-69, 2020

 

Abstract:

We survey results related to the attempt to define communication complexity to P systems. Our P system model would be Evolution–Communication P systems with energy introduced in 2010. Some insights and research directions are suggested towards the end of the paper.

Full text available upon request to the author

Article title: Computing with SN P systems with I/O mode

Authors: Henry N. Adorna

Publication title: Journal of Membrane Computing 2(4): 230-245, 2020

 

Abstract:

P systems were introduced more than two decades ago by Gheorghe Pǎun. They are known as nondeterministic maximally parallel computing models. Most of their variants are proved to be capable of solving NP problems in polynomial time. This work focuses on using neural-like P systems to simulate uniform sequential computing models. In particular, we consider a so-called Spiking Neural P module (SN P module) computing finite-state functions. We define and characterize a so-called (SN) P automatic sequence by SN P modules.

Full text available upon request to the author

Article title: On Finding Two Posets that Cover Given Linear Orders

Authors: Ivy Ordanel, Proceso Fernandez and Henry Adorna

Publication title: Algorithms 12(10): 219, 2019

 

Abstract:

The Poset Cover Problem is an optimization problem where the goal is to determine a minimum set of posets that covers a given set of linear orders. This problem is relevant in the field of data mining, specifically in determining directed networks or models that explain the ordering of objects in a large sequential dataset. It is already known that the decision version of the problem is NP-Hard while its variation where the goal is to determine only a single poset that covers the input is in P. In this study, we investigate the variation, which we call the 2-Poset Cover Problem, where the goal is to determine two posets, if they exist, that cover the given linear orders. We derive properties on posets, which leads to an exact solution for the 2-Poset Cover Problem. Although the algorithm runs in exponential-time, it is still significantly faster than a brute-force solution. Moreover, we show that when the posets being considered are tree-posets, the running-time of the algorithm becomes polynomial, which proves that the more restricted variation, which we called the 2-Tree-Poset Cover Problem, is also in P.

Article title: Sequential spiking neural P systems with local scheduled synapses without delay

Authors: Alia Bibi, Fei Xu, Henry N, Adorna, Francis George C, Cabarle

Publication title: Complexity 2019

 

Abstract:

Spiking neural P systems with scheduled synapses are a class of distributed and parallel computational models motivated by the structural dynamism of biological synapses by incorporating ideas from nonstatic (i.e., dynamic) graphs and networks. In this work, we consider the family of spiking neural P systems with scheduled synapses working in the sequential mode: at each step the neuron(s) with the maximum/minimum number of spikes among the neurons that can spike will fire. The computational power of spiking neural P systems with scheduled synapses working in the sequential mode is investigated. Specifically, the universality (Turing equivalence) of such systems is obtained.

Full text available upon request to the author

Article title: Handling non-determinism in spiking neural P systems: Algorithms and simulations

Authors: Jym Paul Carandang, Francis George C Cabarle, Henry Natividad Adorna, Nestine Hope S Hernandez, et al.

Publication title: Fundamenta Informaticae 164(2-3): 139-155, 2019

 

Abstract:

Spiking Neural P system is a computing model inspired on how the neurons in a living being are interconnected and exchange information. As a model in embrane computing, it is a non-deterministic and massively-parallel system. The latter makes GPU a good candidate for accelerating the simulation of these models. A matrix representation for systems with and without delay have been previously designed, and algorithms for simulating them with deterministic systems was also developed. So far, non-determinism has been problematic for the design of parallel simulators. In this work, an algorithm for simulating non-deterministic spiking neural P system with delays is presented. In order to study how the simulations get accelerated on a GPU, this algorithm was implemented in CUDA and used to simulate non-uniform and uniform solutions to the Subset Sum problem as a case study. The analysis is completed with a comparison of time and space resources in the GPU of such simulations.

Full text available upon request to the author

Article title: Generating context-free languages using spiking neural P systems with structural plasticity

Authors: Ren Tristan A. de la Cruz, Francis George Cabarle, Henry N. Adorna

Publication title: Journal of Membrane Computing 1(3): 161-177, 2019

 

Abstract:

Spiking neural P system (SNP system) is a model of computation inspired by networks of spiking neurons. An SNP system is a network of neurons that can send an object, known as a spike, to each other. Spiking neural P system with structural plasticity (SNPSP system) is a variant of the classical SNP system. SNPSP system that incorporates the ideas of synaptogenesis (creating new synapses) and synaptic pruning (deletion of existing synapses), collectively known as structural plasticity, as features of the model. This gives SNPSP systems the ability to change their own structure/topology. In this work, we use SNPSP systems to generate context-free languages. We create a procedure for constructing an SNPSP system given a context-free grammar in Greibach normal form (GNF). The resulting SNPSP system essentially simulates the way in which a context-free grammar in GNF is used to generate languages. We use modules known as arithmetic-memory modules, also created using SNPSP systems, to perform arithmetic operations which are needed for the simulation.

Full text available upon request to the author

Article title: Matrix representation and simulation algorithm of spiking neural P systems with structural plasticity

Authors:  Zechariah B. Jimenez, Francis George C. Cabarle, Ren Tristan A. de la Cruz, Kelvin C. Buño, et al.

Publication title: Journal of Membrane Computing 1(3): 145-160, 2019

 

Abstract:

In this paper, we create a matrix representation for spiking neural P systems with structural plasticity (SNPSP, for short), taking inspiration from existing algorithms and representations for related variants. Using our matrix representation, we provide a simulation algorithm for SNPSP systems. We prove that the algorithm correctly simulates an SNPSP system: our representation and algorithm are able to capture the syntax and semantics of SNPSP systems, e.g. plasticity rules, dynamism in the synapse set. Analyses of the time and space complexity of our algorithm show that its implementation can benefit using parallel computers. Our representation and simulation algorithm can be useful when implementing SNPSP systems and related variants with a dynamic topology, in software or hardware.

Full text available upon request to the author

Article title: Optimal Deterministic Algorithm for Hammock (2, 2)-Poset Cover Problem

Authors: I. Ordanel and H. Adorna

Publication title: Philippine Journal of Science 147(7): 733-748, 2018

 

Abstract:

Consider the ordering of different tasks in Figure 1. Suppose a teacher gives those tasks to students and the students need to finish all of them. From the graph, there are some tasks that are dependent on other tasks. For example, Tasks 2, 3, and 4 need to be accomplished first before proceeding on Task 5. There are also some tasks that do not have dependencies. For example, Task 6 is not dependent on Task 7, so it does not matter which one between them will be started first. With this ordering, one student can do all the tasks in the following order: Task 1→ Task 2→ Task 3→ Task 4→ Task 5→ Task 6→ Task 7→ Task 8. Another student can accomplish all the task as follows: Task 1→ Task 3→ Task 2→ Task 4→ Task 5→ Task 7→ Task 6→ Task 8. There are actually 12 possible ways on which a student can finish all the tasks. This is a typical scenario–an ordering is given and the flow of events must follow from them.

Article title: On Distributed Solution to SAT by Membrane Computing

Authors: Henry N. Adorna, Linqiang Pan, Bosheng Song

Publication title: International Journal of Computers Communication & Control 13(3): 303-320, 2018

 

Abstract:

Tissue P systems with evolutional communication rules and cell division (TPec, for short) are a class of bio-inspired parallel computational models, which can solve NP-complete problems in a feasible time. In this work, a variant of TPec, called -distributed tissue P systems with evolutional communication and cell division (, for short) is proposed. A uniform solution to the SAT problem by  under balanced fixed-partition is presented. The solution provides not only the precise satisfying truth assignments for all Boolean formulas, but also a precise amount of possible such satisfying truth assignments. It is shown that the communication resource for one-way and two-way uniform -P protocols are increased with respect to ; while a single communication is shown to be possible for bi-directional uniform -P protocols for any . We further show that if the number of clauses is at least equal to the square of the number of variables of the given boolean formula, then  for solving the SAT problem are more efficient than TPec as show in\cite {bosheng2017}; if the number of clauses is equal to the number of variables, then  for solving the SAT problem work no much faster than TPec.

Article title: On simulating cooperative transition P systems in evolution–communication P systems with energy

Authors: Richelle Ann B. Juayong, Henry N. Adorna

Publication title: Natural Computing 17(2): 333-343, 2018

 

Abstract:

In this paper, we investigate simulations of transition P systems (TP systems) in evolution–communication P systems with energy (ECPe systems). We only focus on TP systems where an object that triggers a cooperative rule also triggers a non-cooperative rule. In this way, the presence of a rule trigger always implies that a rule will be applied. In our constructed ECPe systems, a transition in the TP system is simulated by a k-step computation where k is a factor of the cardinality of the alphabet in the original system. Also, the maximum energy needed for communication rules depends on the number of copies of a trigger in a cooperative rule.

Full text available upon request to the author

Article title: A quick survey of tissue-like P systems

Authors: Bosheng Song, Yingxin Hu, Henry N. Adorna, Fei Xu

Publication title: Romanian Journal of Information Science and Technology 21(3): 310-321, 2018

 

Abstract:

Membrane computing is a branch of natural computing, which abstracts from the architecture and the functioning of living cells. The models investigated in membrane computing are distributed and parallel computing devices, which are generically called P systems. Three main families have been considered until now: cell-like P systems, tissuelike P systems and neural-like P systems. In this work, we first present the definitions of tissue-like P systems and several variants of these systems, then some results about Turing universality and computational efficiency are recalled. Finally, a computational complexity theory within the framework of tissue-like P systems is introduced, polynomial complexity classes associated with several variants of tissue-like P systems are defined and some relevant results are presented. Different borderlines between efficiency and non-efficiency on the basis of the length of communication rules are presented.

Full text available upon request to the author

Article title: Solving the N-Queens problem using dP systems with active membranes

Authors: Kelvin C. Buño, Francis George C. Cabarle, Marj Darrel Calabia, Henry N. Adorna

Publication title: Theoretical Computer Science 736: 1-14, 2018

Abstract:

The N-Queens problem consists of placing N queens on an N×N chessboard such that no two queens threaten each other (i.e. same row, column, or diagonal). P systems solutions to the N-Queens problem and related problems (e.g. SAT) are often in a nondistributed way, i.e. the complete input to the problem enters the system through a single input membrane and the problem is solved. dP systems involve using more than one P system to solve problems in a distributed way, i.e. the problem input is partitioned and each partition enters the system using distinct components (which are also P systems). In this work, we solve the N-Queens problem using dP systems where the components are P systems with active membranes. Our 2-component and 3-component solutions partition the elements of the input multiset based on the clauses they represent. Compared to the nondistributed solution, our 2-component and 3-component solutions reduce the computation time by a half and by a third, respectively. Besides the analysis of the computation time, we also analyze communication costs. ComN, indicating the number of computation steps where communication occurred, is constant for both solutions. ComR, the number of intercomponent communication rules used, and ComW, the number of objects communicated, are in terms of S, where S is the number of solutions to the problem instance.

Full text available upon request to the author

Article title: Sparse-matrix Representation of Spiking Neural P Systems for GPUs

Authors: Miguel A. Martınez-del-Amor, David Orellana-Martın, Francis G.C. Cabarle, Henry N. Adorna, et al.

Publication title: Proc. of 15th Brainstorming Week on Membrane Computing. Seville, Spain: Fénix Editora: 161-170, 2017

Abstract:

Current parallel simulation algorithms for Spiking Neural P (SNP) systems are based on a matrix representation. This helps to harness the inherent parallelism in algebraic operations, such as vector-matrix multiplication. Although it has been convenient for the first parallel simulators running on Graphics Processing Units (GPUs), such as CuSNP, there are some bottlenecks to cope with. For example, matrix representation of SNP systems with a low-connectivity-degree graph lead to sparse matrices, ie containing more zeros than actual values. Having to deal with sparse matrices downgrades the performance of the simulators because of wasting memory and time.

However, sparse matrices is a known problem on parallel computing with GPUs, and several solutions and algorithms are available in the literature. In this paper, we briefly analyse some of these ideas and apply them to represent some variants of SNP systems. We also conclude which variant better suit a sparse-matrix representation.

Full text available upon request to the author

Article title: CuSNP: Spiking neural P systems simulators in CUDA

Authors: Jym Paul Carandang, John Matthew B. Villaflores, Francis George C. Cabarle, Henry N. Adorna, et al.

Publication title: Romanian Journal of Information Science and Technology (ROMJIST) 20 (1): 57-70, 2017

Abstract:

Spiking neural P systems (in short, SN P systems) are models of computation inspired by biological neurons. CuSNP is a project involving sequential (CPU) and parallel (GPU) simulators for SN P systems. In this work, we report the following results: a P-Lingua le parser is included, for ease of use when performing simulations; extension of the matrix representation of SN P systems to include delay; comparison and analysis of our simulators by simulating two types (bitonic and generalized) of parallel sorting networks; extension of supported types of regular expressions in SN P systems. Our GPU simulator is better suited for generalized sorting as compared to bitonic sorting networks, and the GPU simulators run up to 50 faster than our CPU simulator. Finally, we discuss our experiments and provide directions for further work.

Article title: Spiking neural P systems with scheduled synapses

Authors: Francis George C. Cabarle, Henry N. Adorna, Min Jiang, Xiangxiang Zeng

Publication title: IEEE Transactions on Nanobioscience 16(8): 792-801, 2017

Abstract:

Spiking neural P systems (SN P systems) are models of computation inspired by biological spiking neurons. SN P systems have neurons as spike processors, which are placed on the nodes of a directed and static graph (the edges in the graph are the synapses). In this paper, we introduce a variant called SN P systems with scheduled synapses (SSN P systems). SSN P systems are inspired and motivated by the structural dynamism of biological synapses, while incorporating ideas from nonstatic (i.e., dynamic) graphs and networks. In particular, synapses in SSN P systems are available only at specific durations according to their schedules. The SSN P systems model is a response to the problem of introducing durations to synapses of SN P systems. Since SN P systems are in essence static graphs, it is natural to consider them for dynamic graphs also. We introduce local and global schedule types, also taking inspiration from the above-mentioned sources. We prove that SSN P systems are computationally universal as number generators and acceptors for both schedule types, under a normal form (i.e., a simplifying set of restrictions). The introduction of synapse schedules for either schedule type proves useful in programming the system, despite restrictions in the normal form.

Full text available upon request to the author

Article title: Robustness diagram with loop and time controls for system modelling and scenario extraction with energy system applications

Authors: Jasmine Malinao, Florian Judex, Tim Selke, Gerhard Zucker, et al.

Publication title: Energy Procedia 88: 537-543, 2016

Abstract:

In this research, we introduce an extension of Robustness Diagrams for modelling complex systems such as energy systems. We provide a construction scheme of this extension for the inclusion of looped and time-dependent substructures for an effective modelling framework. The latter set of substructures is introduced in this work as “reset-bound subsystems”. We introduce a scenario extraction algorithm to obtain behavioral profiles from the models. Lastly, we apply our scheme to create a model of a real-world energy system and use the proposed algorithm to extract a scenario describing one process done by the system being modelled.

Article title: Notes on spiking neural P systems and finite automata

Authors: Francis George C. Cabarle, Henry N. Adorna, Mario J. Pérez-Jiménez

Publication title: Natural Computing 15(4): 533-539, 2016

Abstract:

Spiking neural P systems (in short, SN P systems) are membrane computing models inspired by the pulse coding of information in biological neurons. SN P systems with standard rules have neurons that emit at most one spike (the pulse) each step, and have either an input or output neuron connected to the environment. A variant known as SN P modules generalize SN P systems by using extended rules (more than one spike can be emitted each step) and a set of input and output neurons. In this work we continue relating SN P modules and finite automata. In particular, we amend and improve previous constructions for the simulatons of deterministic finite automata and state transducers. Our improvements reduce the number of neurons from three down to one, so our results are optimal. We also simulate finite automata with output, and we use these simulations to generate automatic sequences.

Full text available upon request to the author

Article title: Sequential spiking neural P systems with structural plasticity based on max/min spike number

Authors: Francis George C. Cabarle, Henry N. Adorna, Mario J. Pérez-Jiménez

Publication title: Neural Computing and Applications 27(5): 1337-1347, 2016

Abstract:

Spiking neural P systems (in short, SNP systems) are parallel, distributed, and nondeterministic computing devices inspired by biological spiking neurons. Recently, a class of SNP systems known as SNP systems with structural plasticity (in short, SNPSP systems) was introduced. SNPSP systems represent a class of SNP systems that have dynamism applied to the synapses, i.e. neurons can use plasticity rules to create or remove synapses. In this work, we impose the restriction of sequentiality on SNPSP systems, using four modes: max, min, max-pseudo-, and min-pseudo-sequentiality. We also impose a normal form for SNPSP systems as number acceptors and generators. Conditions for (non)universality are then provided. Specifically, acceptors are universal in all modes, while generators need a nondeterminism source in two modes, which in this work is provided by the plasticity rules.

Full text available upon request to the author

Article title: Relating computations in non-cooperative transition P systems and evolution-communication P systems with energy

Authors: Richelle Ann B. Juayong and Henry N Adorna

Publication title: Fundamenta Informaticae 136(3): 209-217, 2015

Abstract:

This paper explores the relation of computations in Evolution-Communication P systems with energy (ECPe systems) and non-cooperative Transition P systems without dissolution (TP systems). We have shown that for every non-cooperative TP system, we can construct an ECPe system that,(i) generates the same language, and (ii) each halting computation that takes τ steps in the TP system can be simulated in at most 3τ+ 1 steps in its corresponding ECPe system.

Full text available upon request to the author

Article title: Spiking neural P systems with structural plasticity

Authors: Francis George C. Cabarle, Henry N. Adorna, Mario J. Pérez-Jiménez, Tao Song

Publication title: Neural Computing and Applications 26(8): 1905-1917, 2015

Abstract:

Spiking neural P (SNP) systems are a class of parallel, distributed, and nondeterministic computing models inspired by the spiking of biological neurons. In this work, the biological feature known as structural plasticity is introduced in the framework of SNP systems. Structural plasticity refers to synapse creation and deletion, thus changing the synapse graph. The “programming” therefore of a brain-like model, the SNP system with structural plasticity (SNPSP system), is based on how neurons connect to each other. SNPSP systems are also a partial answer to an open question on SNP systems with dynamism only for synapses. For both the accepting and generative modes, we prove that SNPSP systems are universal. Modifying SNPSP systems semantics, we introduce the spike saving mode and prove that universality is maintained. In saving mode, however, a deadlock state can arise, and we prove that reaching such a state is undecidable. Lastly, we provide one technique in order to use structural plasticity to solve a hard problem: a constant time, nondeterministic, and semi-uniform solution to the NP-complete problem Subset Sum.

Article title: Reoptimization of Motif Finding Problem

Authors: Jhoirene B. Clemente, Jeffrey A. Aborot, Henry N. Adorna

Publication title: Proceedings of the International MultiConference of Engineers and Computer Scientists 1, 2014

Abstract:

One of the approaches in solving NP-hard problems is through reoptimization. In this technique, we solve a locally modified instance of a problem by making use of known solution to its original instance instead of obtaining a solution from scratch. In this paper, we present a reoptimization of motif finding problem. Since the problem is showed to be self-reducible, we can use a self-reduction method to solve the reoptimization variant of the problem. Using the method, we have improved the approximation ratio of the algorithm solving the reoptimized version as compared to the non-reoptimized counterpart. Moreover, we showed that if a certain problem is self-reducible, any problem that obtains a polynomial-time reduction to it is also self-reducible.

Article title: A GPU simulation for evolution-communication P systems with energy having no antiport rules

Authors: Zylynn F. Bangalan, Krizia Ann N. Soriano, Richelle Ann B. Juayong, Francis George C. Cabarle, et al.

Publication title: Proceedings of the Eleventh Brainstorming Week on Membrane Computing: 25-50, 2013

Abstract:

Evolution-Communication P system with energy (ECPe systems) is a cell- like variant P system which establishes a dependence between evolution and communi- cation through special objects, called `energy,' produced during evolution and utilized during communication. This paper presents our initial progress and e orts on the im- plementation and simulation of ECPe systems using Graphics Processing Units (GPUs). Our implementation uses matrix representation and operations presented in a previous work. Speci cally, an implementation of computations on ECPe systems without antiport rules is discussed.

Full text available upon request to the author

Article title: The Reduction-Buildup Algorithm (RBA) for Efficient Support Set Construction

Authors: Jasmine A. Malinao, Richelle Ann B. Juayong, Unaiza M. Garnica, Henry N. Adorna

Publication title: Philippine Information Technology Journal 3(1): 43-47, 2012

Abstract:

The Reduction-Buildup Algorithm (RBA) is introduced in this study to be able to generate a minimal support set for a given conflict-free binary 2− tagged data set S of n dimen-sions. A support set φ, where| φ|≤ n, is a set of dimensions obtained from S which forms another conflict-free data set. Finding this set has been proven to be NP-complete in. Unlike previous literatures that have transformed the orig-inal data set into another form prior to deriving a minimal support set, RBA shows that such a set can still be achieved in a comparable running time and utilizing lesser computa-tion space even in the absence of this transformation.

Full text available upon request to the author

Article title: Strong Spanned Patterns Generation Using Subsequence Cover Problem Reduction and the Term-Product Operation

Authors: Jasmine A. Malinao, Richelle Ann B. Juayong, Nestine Hope S. Fernandez, Henry N. Adorna

Publication title: Philippine Journal of Science 141(2): 127-139, 2012

Abstract:

The Strong Spanned Patterns-Trie Construction (SSP-TC) algorithm is introduced to efficiently generate a set of strong spanned patterns of a given conflict-free binary k-tagged data set obtained by the use of the Approximate Crisp Theory Set Formation (ACTSF) methodology that we proposed in our previous work. In our previous work, we have shown that such a set with this characteristic can be obtained using the SSP-trie data structure in O (mn2). In this paper, we present and prove the correctness of the SSP-TC algorithm that generates this set through parallel computations in O (mn) implemented in this trie structure. We were also able to reduce the problem of generating a set of strong spanned patterns into a problem known as the Subsequence Cover Problem (SubCP). We obtain a solution to this reduct through the use of the SSP-TC algorithm and the SSP-Trie data structure whose input is from the components of the Term-Product Matrix introduced in this paper. To illustrate the classification performance of the generated set of patterns using the proposed concepts and methods, we use two data sets publicly-made-available in University of California Irvine (UCI) Machine Learning Repository and show that we achieve better rates of classification on the test sets of the two data sets compared with the results in literature.

Article title: A Quantitative Analysis-based Algorithm for Optimal Data Signature Construction of Traffic Data Sets

Authors: Jasmine A. Malinao, Richelle Ann B. Juayong, Rona May U. Tadlas, Jhoirene B. Clemente, et al.

Publication title: Information and Media Technologies 7(3): 949-955, 2012

Abstract:

In this paper, a new set of m-dimensional Power Spectrum-based data signatures is derived to obtain better Vector Fusion 2-dimensional visualizations of a time series and periodic n-dimensional traffic data set as compared with visualizations produced from using the entire set of n-dimensional Power Spectrum representations in literature, where m≪ n. We were able to ascertain that 4-dimensional data signatures provide empirically optimal representations with respect to the data set used. We have achieved≈ 97.6% reduction in terms of data representation of the original nD data set with the signatures. We propose an algorithm that determines how good the selected set of m-dimensional signatures represents the n-dimensional data set in 2 dimensions in quantitative terms. We use the Vector Fusion visualization algorithm in transforming each signature from m dimensions into 2 dimensions. An improved set of qualitative criterion is drawn to measure the goodness of the 2-dimensional data signature-based visual representation of the original n-dimensional data set. Finally, we provide empirical testing, discuss the results, and conclude the contributions of the proposed methods.

Article title: Traffic Density Modeling on NLEX Time Series Data Segment

Authors: Reynaldo G. Maravilla Jr, Elise Raina A. Tabanda, Jasmine A. Malinao, Henry N. Adorna

Publication title: Philippine Information Technology Journal 5(2): 14-18, 2012

Abstract:

Traffic density-based analysis provides a more effective representation of congestion than volume-based analysis. However, existing propositions on determining densities proved to be inefficient according to traffic engineering experts in the National Center of Transportation Studies (NCTS). In this study, we made use of a similar density model, this time considering the space of the road segment as an important factor. With the data set provided by NCTS, careful preprocessing yielded valid traffic flow characteristics that were used in modeling traffic flow behavior. Relationships between these characteristics are also observed through established traffic models. With those models, we deter-mined the traffic flow behavior of North Luzon Expressway Balintawak-North Bound segment.

Full text available upon request to the author

Article title: Data signatures for traffic data analysis

Authors: Jasmine A. Malinao, Richelle Ann B. Juayong, Francis James O. Corpuz, Jan Michael C. Yap, et al.

Publication title: Philippine Information Technology Journal 3(1): 12-17, 2012

Abstract:

With the advent of the Information Age, interpretation of huge amounts of data always poses big problem to data analysts. Methodologies had been created to try to mine useful and, possibly, novel information from data sources of massive sizes. We use the concept of Data Signatures to accomplish these difficult tasks. Data sets are processed by combinations of algorithms with a common aim of creating smaller and more compact representation or summarization of the latent characteristics of the data sets. We investigate the effectiveness of Power Spectrum signatures to analyze traffic volume data. We show that this method is successful in data repre-sentation, detection of common patterns, determination of outliers, and realization of unexpected and novel information from the data set through the help of domain experts from the National Center for Transportation Studies (NCTS).

Full text available upon request to the author

Article title: Characterizing classes of potential outliers through traffic data set data signature 2D nMDS projection

Authors: Erlo Robert F. Oquendo, Jhoirene B. Clemente, Jasmine A. Malinao, Henry N. Adorna

Publication title: Philippine Information Technology Journal 4(1): 37-42, 2012

Abstract:

This paper presents a formal method for characterizing the potential outliers from the data signature projection of traffic data set using Non-Metric Multidimensional Scaling (nMDS) visualization. Previous work had only relied on visual inspection and the subjective nature of this technique may derive false and invalid potential outliers. The identification of correct potential outliers had already been an open problem proposed in literature. This is due to the fact that they pinpoint areas and time frames where traffic incidents/accidents occur along the North Luzon Expressway (NLEX) in Luzon.

Full text available upon request to the author

Article title: On the simulations of evolution-communication P systems with energy without antiport rules for GPUs

Authors: Richelle Ann B. Juayong, Francis George C. Cabarle, Henry N. Adorna, Miguel Ángel Martínez del Amor

Publication title: Proceedings of the Tenth Brainstorming Week on Membrane Computing: 267-290, 2012

Abstract:

In this report, we present our initial proposal on simulating computations on a restricted variant of Evolution-Communication P system with energy (ECPe system) which will then be implemented in Graphics Processing Units (GPUs). This ECPe sys- tems variant prohibits the use of antiport rules for communication. Several possible levels of parallelizations for simulating ECPe systems computations on GPUs are emphasized. Our work is based on a localized matrix representation for the mentioned variant given in a previous literature. Our proposal employs a methodology for forward computing also discussed in the said literature.

Full text available upon request to the author

Article title: Improving GPU simulations of spiking neural P systems

Authors: Francis George C. Cabarle, Henry N. Adorna, Miguel Ángel Martínez del Amor, Mario de Jesús Pérez Jiménez

Publication title: Romanian Journal of Information Science and Technology 15 (1): 5-20, 2012

Abstract:

In this work we present further extensions and improvements of a Spiking Neural P system (for short, SNP systems) simulator on graphics processing units (for short, GPUs). Using previous results on representing SNP system computations using linear algebra, we analyze and implement a compu- tation simulation algorithm on the GPU. A two-level parallelism is introduced for the computation simulations. We also present a set of benchmark SNP sys- tems to stress test the simulation and show the increased performance obtained using GPUs over conventional CPUs. For a 16 neuron benchmark SNP system with 65536 nondeterministic rule selection choices, we report a 2.31 speedup of the GPU-based simulations over CPU-based simulations.

Full text available upon request to the author

Article title: Spiking neural P system without delay simulator implementation using GPGPUs

Authors: Francis Cabarle, Henry Adorna, MA Martínez-del-Amor

Publication title: Eleventh Philippine Computing Science Congress: 35-43, 2011

Abstract:

This paper presents a parallel simulator for a type of P system known as spiking neural P system (SNP system) using general purpose graphics processing units (GPGPUs). GPGPUs, unlike the more conventional and general purpose, multi-core CPUs, are used for parallelizable problems due to their architectural optimization for parallel computations.

Membrane computing or P systems on the other hand, are cell-inspired computational models which compute in a maximally parallel and non-deterministic manner. SNP systems, w/c compute via time separated spikes and whose inspiration was taken from the way neurons operate in living organisms, have been represented as matrices.

Article title: Simulating Spiking Neural P systems without delays using GPUs

Authors: Francis Cabarle, Henry Adorna, Miguel A Martinez-del-Amor

Publication title: International Journal of Natural Computing Research (IJNCR) 2(2): 19-31, 2011

Abstract:

In this paper, the authors discuss the simulation of a P system variant known as Spiking Neural P systems (SNP systems), using Graphics Processing Units (GPUs). GPUs are well suited for highly parallel computations because of their intentional and massively parallel architecture. General purpose GPU computing has seen the use of GPUs for computationally intensive applications, not just in graphics and video processing. P systems, including SNP systems, are maximally parallel computing models taking inspiration from the functioning and dynamics of a living cell. In particular, SNP systems take inspiration from a type of cell known as a neuron. The nature of SNP systems allowed for their representation as matrices, which is an elegant step toward their simulation on GPUs. In this paper, the simulation algorithms, design considerations, and implementation are presented. Finally, simulation results, observations, and analyses using a simple but non-trivial SNP system as an example are discussed, including recommendations for future work.

Article title: An Algorithm to Efficiently Generate an Approximation of a Theory Set

Authors: J. Malinao and H. Adorna

Publication title: Proceedings of 9th Philippine Computing Science Congress: 2-3, 2009

Abstract:

A theory set essentially consists of patterns that summarizes the observed inherent behavior of each cluster of observation in a data set. Furthermore, it is used in evaluating the cluster membership of new sets of data. Due to the large amount of computational resources needed to generate a theory set of a given data set, we propose an algorithm to approximate this set efficiently.

Full text available upon request to the author