Theory and Practice of Computation

The following sections are included:

• Preface
• PROGRAM CO-CHAIRS
• PROGRAM COMMITTEES
• GENERAL CO-CHAIRS
• ORGANIZING COMMITTEES
• Contents

The Poset Cover Problem is the problem where the input is a set of linear orders and the goal is to find a minimum set of posets that generates exactly all the given linear orders. The computational complexity of the decision version of the problem is already known; it is NP-Complete. However, the approximation complexity or approximability of the problem is not yet known.

In this paper, we show the approximability of two simple variations of the problem where the poset being considered are Hammock posets having hammocks of size 2. The first is Hammock(2, 2, 2)-Poset Cover Problem where the solution is a set of Hammock posets with 3 hammocks of size 2. This problem has been shown to be NP-Complete and in this paper we show that it is 2.7-approximable. The second variation which is more general than the first one considers Hammock posets with any number of hammocks of size 2 and we show that it is $H(n)-\frac{196}{300}-\text{approximable}$.

The Minimum Synteny problem is a well-known NP-hard problem that aims to identify the minimum syntenic distance between two genomes. In this paper, we focus on solving a variant of the problem, called the Minimum Translocation Synteny problem, where we consider the minimum number of translocations to transform one genome to another. We propose a polynomial-time algorithm that computes for the translocation syntenic distances between two genomes with square instances. The MinTranSyn algorithm presents a solution to the translocation syntenic distance problem by using a prioritization method in selecting an index to be isolated and vertices to be translocated. The MinTranSyn algorithm is devised for genomes with square instances having square-connected components. With this, the algorithm presented by Belenzo8 was improved with respect to the number of translocations. We showed the quality of the algorithm is bounded above by the total number of chromosomes in a genome for synteny graphs that are 2-regular, wheel, and acyclic.

Grover’s quantum search algorithm is a template for doing quantum search in unstructured search spaces. The details of the oracle in Grover’s algorithm is abstracted for the purpose of analyzing the bound on the number of queries the algorithm must make in order to find the target element of the search space. In order for Grover’s quantum search algorithm to be usable in a specific unstructured search problem, one must provide details on the inner workings of the oracle.

Specifically, we present a high-level and basic design of the oracle using the quantum computing model specific to the exact string matching problem. We describe our design using the quantum circuit model of computing and show that the gate complexity of the circuit is linear with respect to the product of the length of the pattern and the size of the alphabet. We have suggested a quantum memory structure for storage and retrieval of the input text. The quantum circuit we presented requires scratch qubits linear to the product of the length of the pattern and the size of the alphabet to reduce the size of the scratch register without exponential increase in the count of elementary gates required for the computation.

Structural motifs are short segments of a protein 3D structure that may appear to be conserved in a group of functionally related set of proteins. Finding such structures are essential in the field of proteomics for drug discovery. In this paper, we present a tool for finding structural motifs from a given a set of peptides. The computational model of the problem is NP-hard. We provide a tool which is an implementation of a polynomial-time approximation scheme (PTAS) for identifying conserved regions of the peptide. The tool is able to find compact structural motifs efficiently and with a customizable performance guarantee.

Functional reactive programming (FRP) is a programming paradigm for reactive systems based on declarative abstractions to express time-varying values. Previous works showed that FRP is beneficial to embedded systems. In this paper, we propose a new execution mechanism for an FRP language designed for resource constrained embedded systems. The mechanism is based on the Actor model, a concurrent computation model in which computation is achieved by actors communicating via asynchronous messages. We adopt actors for the run-time representation of time-varying values and event streams. With this representation, we can naturally integrate asynchronous execution mechanism in the runtime of the language.

Finding gene clusters in genomes is an essential process in establishing relationships among organisms. Gene clusters may express functional dependencies among genes and may give insight into expression of specific traits and perhaps even of diseases. The problem of finding gene clusters among several genomes is referred to as Gene Cluster Discovery and several models have already been formulated for its definition. One formulation of this problem is the Approximate Gene Cluster Discovery Problem (AGCDP), which is modeled as a combinatorial optimization problem in some works. In this study we show the formulation of an instance of AGCDP into the Minimum Weighted t-partite Clique Problem (MWtCP), which is the problem of finding a t-clique with minimum weight given a complete edge-weighted t-partite graph. This study also presents an algorithm that runs on O(n²) in the metric case of inputs which is related to another algorithm for MWtCP presented in another study. However, this version allows more edges to be considered in approximating the t-clique with minimum weight. We show that this algorithm has a 2-approximation performance guarantee for the metric case and 1 approximation performance guarantee for the ultrametric case.

A restart strategy with time delay is proposed to a multi-agent consensus algorithm for an approximated distributed minimax optimization. The restart strategy controls a step length of a subgradient method and resets a local clock under certain criteria in the algorithm. A synchronization protocol with time delay is introduced in the algorithm to execute the restart strategy simultaneously. A numerical example illustrates that the proposed algorithm works well particularly in high approximation ratios.

In programming languages, first-class object is an entity which can be passed to a function as an actual parameter and returned from the function as a return value. You can classify and compare the programming languages from the point of view of first-class object. A continuation means a rest of computation at some point in a program, which corresponds to a call stack in a programming language processor. An environment is a mapping of variable names to bound values. In the framework of the lambda calculus, the first-class continuation was studied by Felleisen and the first-class environment has been studied by us.

In this paper, we propose a call-by-value lambda calculus with first-class continuations and environment. Its operational semantics is formalized as a small-step semantics using evaluation contexts. Then, we show the soundness property of the operational semantics with respect to the call-by-value lambda calculus with first-class continuations and records.

Many fatal accidents involving safety-critical reactive systems occur in unexpected situations that were not considered during the development of the specification. However, realizability verification of reactive system typically involves complex and intricate analyses. To avoid this difficulty, Schewe et al. (2007) introduced the notion of bounded realizability that requires the existence of a model of size k that satisfies the given specification. Further to our works on bounded realizability checking that we have reported previously, we have put forward ideas on how this method might be improved in this paper. Specifically, we discuss bounded nonemptiness checking for Universal Co-Büchi Tree automata (UCT), based on simulation relations or state equivalences of UCT. Our method constructs a universal co-Büchi tree automata (UCT) that accepts models of a system (environment) that satisfy (do not satisfy) the specifications in all cases. Then, we check bounded nonemptiness for the automaton. We reduce bounded nonemptiness checking to a SAT problem, and solved the problem using a fast SAT solver. Through experiments, we demonstrated that our method can check problems at a lower cost in many cases. Based on simulation relations or state equivalences of UCT, we have shown the proposed approach has improved the SAT-based bounded nonemptiness checking process for UCT more efficient than those presented in our previous work, in terms of checking bounded realizability.

For the past few years, there is a significant increase in the number of mobile health (mHealth) applications specifically for diabetes. These applications are mostly for self - management. However, most of these applications have the same features but it lack the part of educating patients and the involvement of medical professionals in the development process of an application. Diabetes Bridge aims to propose solutions to these problems.

Diabetes Bridge is a mobile health application intended to better facilitate care coordination for people with diabetes. This application was developed with the coordination of a healthcare professional. Some features of the application includes preparing for the consultation with listing down important questions, knowing what to do before going to laboratory tests, and educating patients with the common questions that diabetic people asked to their doctors.

The usability of Diabetes Bridge was evaluated by people with diabetes and a health practitioner using Mobile Application Rating Scale (MARS) as an evaluation tool to assess the mobile health application in four categories. A total of thirty (30) people participated in the testing. The participants perceived the application to be useful and that it was well - made for people with diabetes. The application’s simplicity and ease of use receive a good feedback from the testers. Improvements can be made in the visuals of the application to make it more appealing for all age groups and not only for the older people. It is very useful in preparation with the patient’s consultation, laboratory requests and results and educating the patient about his diseases. Diabetes Bridge is positively received by diabetic people as a good mobile health application.

This paper presents an analysis of Filipino and Japanese students’ facial expressions and hand gestures while solving a series of computer programming exercises. Frequently occurring Facial Action Coding System (FACS) muscle movements such as the widening of the eye (AU-5) and sucking of the lip (AU-28), as well as the occurrence of hand gestures, are identified and discussed in relation to the reported affective states of engagement and confusion. We show that it is possible to build models for predicting engagement and confusion using facial expressions and typing information. We believe that this study can help in the development of affectively aware computer systems for learning programming that can work with different cultures.

Numerous studies on emotion recognition have discovered that facial cues are reliable to distinguish one emotional expression from another. This is useful in highly-controlled environments where the face can easily be tracked. However, this is not true in real-world scenarios, thus, alternative modalities need to be investigated. Bodily expression and human activity can provide additional information to recognize an emotional expression, which will hopefully help create more robust models. Previous works on body movement used acted emotional expressions. To overcome this limitation, this work collected body movement data as human subjects played a game. Subjects are free to move within their assigned space as data was recorded. SVM and Random Forest models predicted valence, arousal and intensity using body posture, movement and activity. Models that reached a validation score of 70% and train-test accuracy of 60% have been analyzed. The best performing model reached a train-test accuracy of 80.2%.

The researchers attempt to create a Case Management System that could better represent and better assist workflow environments currently in use by most multi-tiered Organizations. The Office of the Vice President for Legal Affairs in the University of the Philippines, one such office, will be used as the pilot office. The Case Management System will be based on the needs of the said office and the comments, ideas and suggestions of their employees, as well as incorporating modern studies on functional Information Systems into the design.

With the traditional similarity-based approaches to recommender systems, it is unlikely to discover truly novel things. Users no longer find the outputs interesting or surprising since the outputs are locked into clusters of similarities on single domain. To make recommendations more attractive to the users, the system must provide a serendipitous recommendation list which is new, exciting and unexpectable. Serendipitous recommendation increases the chance of discovering music that is truly novel and unexpectedly useful leading to better performance and higher efficiency. In this paper, we propose a bisociative based approach to automatically generate a serendipitous recommendation list for particular users. The unexpected interesting links crossing different context domains are found by applying bisociative knowledge discovery concept and inducting the rules for generating the serendipitous list using probabilistic logic framework. For the music recommendation on subset of Amazon product dataset including users’ music and movie preferences, we are able to achieve a recommendation list with 60% accuracy. The list includes recommendations which are not found in the single-domain based systems.

WappenLite is a platform to provide Web-based programming environments mainly for JVM-based programming languages. Since the deprecation of Java applets, we must redesign some aspects of WappenLite. This paper reports the structure and the features of renewed WappenLite and explains its usage along with its future plans.

Cognitive abilities are brain-based skills needed to carry out any task. These are measured using cognitive tests generally designed to be administered by an expert, which consequently makes experience less engaging. Gamification, or the application of game elements in a non-game context improves the experience and the engagement of the user while doing mundane tasks. RoboKuma is a serious game platform that incorporates gamified cognitive tests to measure a person’s cognitive abilities to improve the engagement and overall experience when taking the tests. This study evaluates the effectiveness of the system for use in measuring a person’s cognitive ability. Upon the deployment of the system, the collected data from select participants were observed and analyzed to assess the system’s replay value and effectiveness as a clinical tool. Based on the analysis performed, it can be concluded that the system is an effective tool in measuring a person’s cognitive abilities.

Practical education about information security is needed for system developers and administrators in Web service suppliers. We propose a hacking contest CTF as attack and defense style with a website for a multiple online game. The contest organizer prepares a game server site as a contest environment which contains several vulnerability. The contest participants are divided into an attacker team as game players and a defender team as game Website operators. While the attackers access the game site with normal actions, they find vulnerabilities and try cheating actions. While the defenders monitor server logs, they detect illegal events and prevent them for maintenance. An action of each side is calculated as a point and makes each score for victory or defeat by the contest rule. The contest organizer reviews the progress situation with all participants. In this paper, we introduce several functions of the system and discuss the result of an official practice in Security Camp 2016 in Japan.

The following section is included:

• Author Index