Digital Library[ Search Result ]
Improving Counterexample-Guided Bidirectional Inductive Synthesis by an Incremental Approach
Yongho Yoon, Woosuk Lee, Kwangkeun Yi
http://doi.org/10.5626/JOK.2023.50.12.1091
One of the sources of inefficiency in counterexample-guided inductive synthesis algorithms is the fresh restart of inductive synthesis for each iteration. In this paper, we propose an incremental approach for the generalized counterexample-guided bidirectional inductive synthesis algorithm. The incremental algorithm reuses knowledge from the last iteration therefore reducing the search space, and making the remaining search faster. We applied our approach to the state-of-the-art bidirectional inductive synthesis algorithm, Simba, which is based on iterative forward-backward abstract interpretation. We implemented our approach and evaluated it on a set of benchmarks from the Simba paper. The experimental results showed that, on average, our approach reduces synthesis time to 74.2% of the original, without any loss in the quality.
A Survey of High-Level Programming Languages for Operating Swarm Robots
Woosuk Kang, EunJin Jeong, Taejoon Yoon, Seokhaeng Heo, Soonhoi Ha
http://doi.org/10.5626/JOK.2022.49.11.936
Robots used for unmanned tasks in various fields have been developing in the direction of operating multiple robots rather than using only a single robot. Since swarm robotics aims to outperform a single robot through cooperative control of multiple robots, it can efficiently perform tasks such as building local maps and searching for survivors. Although developing and operating such swarm robot systems requires a skilled developer, high-level programming languages and frameworks that can support non-experts to easily specify and operate swarm robots are being developed. In this paper, we selected and introduced 11 swarm robot specification languages tested by simulations or using real robots. We compared the difference between selected languages from the viewpoint of software and swarm robot operation. Finally, limitations of swarm robotics languages developed so far and future tasks are discussed.
Program Synthesis for JavaScript via Divide-and-Conquer and Abstraction Interpretation
Jungmin Jo, Hangyeol Cho, Woosuk Lee
http://doi.org/10.5626/JOK.2021.48.6.629
Program synthesis aims to automatically generate a program that satisfies the user intent expressed in the form of a high-level specification. Recent years have witnessed a surge in interest in applying this technology to a wide range of problems. Program synthesis can help improve software development productivity. In this paper, we present an algorithm for synthesizing Javascript programs from input-output examples. Our approach was based on a synergistic combination of the version space algebra-based approach, which can efficiently solve synthesis problems through divide-and-conquer, and abstract interpretation, which can be used to finitize infinite search spaces. We have implemented our approach and evaluated it in 140 problems of synthesizing string- and integer-manipulating programs. On average, the desirable programs were generated within nine seconds.
Performance Improvement of Neural Network-based Detection of ROP Attacks using Abstraction of Instruction Features
http://doi.org/10.5626/JOK.2021.48.5.493
Return-oriented programming (ROP) is a program attack technique that executes code snippets in memory following an attacker-intended order using return instructions. This paper proposes a method of detecting ROP attacks using neural networks. The method reduces the size of the data by using abstraction of instruction features relevant to ROP attacks rather than entire bits of instructions and activates the neural networks only for 12 instructions after a return instruction. Our experiments on a web server, browser, and the necessary libraries show speedups of 9.6 and 1,403.1 over DeepCheck and HeNet with an F1 score of 100.
Computational Analysis of Heuristics and Linear Programming Relaxations for Capacitated Facility Location
http://doi.org/10.5626/JOK.2021.48.4.377
In this paper, we experimentally evaluate new practical heuristics based on approximation algorithms for capacitated facility location (CFL) and the linear programming (LP) relaxations used by them. Although CFL has been extensively studied in the fields of computer science and operations research, an LP-based constant-factor approximation algorithm was only discovered recently. However, the existing analysis only gives a loose upper bound of 288 on the integrality gap of the LP relaxation. By measuring the approximation ratio and the integrality gap in a concrete dataset, this paper aims at measuring the practical performance of the heuristics and the relaxation, which would also provide evidence for further theoretical exploration. Due to the highly theoretical nature of the existing approximation algorithm, its naive implementation is practically inefficient. In this paper, we propose heuristics that improve the running time without affecting the numerical stability and experimentally optimize the algorithms’ parameters, thus obtaining an efficient implementation.
An Autonomous IoT Programming Paradigm Supporting Neuromorphic Models and Machine Learning Models
Sanglok Yoo, Keonmyung Lee, Youngsun Yun, Jiman Hong
http://doi.org/10.5626/JOK.2020.47.3.310
The demands and expectations of the IoT (Internet of Things) application services are increasing with the development of sensor technology and high-speed communication infrastructures. Even with many sensors operating and networked, transmission of all the sensor data to the server for processing is inefficient in terms of communication bandwidth and storage space. Meanwhile, with the recent development of artificial intelligence technology, the demand for intelligent processing of the IoT is increasing. This paper proposes a programming paradigm that can apply neuromorphic model-based models and machine learning models relative to IoT clients, and a programming paradigm that applies machine learning models and knowledge processing models relative to IoT servers. The proposed programming paradigm is expected to be valuable for the intelligent IoT as well as for autonomous IoT environments in that various AI modules can be applied relative to IoT clients and server programs.
Parser Generators Sharing LR Automaton Generators and Accepting General Purpose Programming Language-based Specifications
Jintaeck Lim, Gayoung Kim, Seunghyun Shin, Kwanghoon Choi, Iksoon Kim
http://doi.org/10.5626/JOK.2020.47.1.52
This paper proposes two ways to develop LR parsers easily. First, one can write a parser specification in a general programming language and derive the benefits of syntax error checking, code completion, and type-error checking over the specification from the language’s development environment. Second, to make it easy to develop a parser tool for a new programming language, the automata generation for the parser specifications is in a modular form. With the idea proposed in this study, we developed a tool for writing parsers in Python, Java, C++, and Haskell. We also demonstrated the two aforementioned advantages in an experiment.
Improving the Upper Bound of the Dynamic Time Warping for Sparse and Long Time Sequences
Janghyuk Seo, Woohwan Jung, Kyuseok Shim
http://doi.org/10.5626/JOK.2019.46.6.570
Dynamic Time Warping (DTW), a distance measure widely used in time series analysis, is associated with the shortcoming of long execution time with long time sequences. To alleviate the problem, several algorithms which use a compression technique called run-length encoding and compute approximate DTW distances were recently proposed. However, the computation of the upper bounds by such algorithms consists of adding unnecessary distance values. In this paper, we propose an approximation algorithm which improves the state of the art for computing approximate DTW distances while keeping the time complexity unchanged. Experimental results with both synthetic and real-life data confirm the effectiveness of our proposed algorithm.
An Educational Relay Programming System for Cooperative Programming Activities and Evaluations
http://doi.org/10.5626/JOK.2019.46.6.526
Recently, programming education has become important all around the world. Previously, programming education mostly involved individual ways of learning. However, the process of solving complex real-world problems through programming often requires grouping and cooperative programming. Therefore, a system is needed that enables cooperative programming and evaluation in programming education. Few educational systems exist for cooperative programming education. Meanwhile, a teacher must perform a process-oriented evaluation in order to maximize the educational effects of cooperative learning. But many teachers have felt burdened by this task. In this study, we designed and implemented a relay programming learning system to support cooperative programming learning. We developed factors to be considered in order to support the evaluation of an instructor and developed an automated evaluation algorithm. This allows learners to develop the ability to improve readability, reusability, and maintenance that are important in programming, and allows instructors to easily evaluate learners.
Performance Comparison between Haskell Eval Monad and Cloud Haskell
Yeoneo Kim, Hyungjun An, Sugwoo Byun, Gyun Woo
http://doi.org/10.5626/JOK.2017.44.8.791
Competition in the modern CPU market has shifted from speeding up the clock speed of a single core to increasing the number of cores. As such, there is a growing interest in parallel programming to maximize the use of resources of many core processors. In this paper, we propose parallel programming models in Haskell to find an advisable parallel programming model for many-core environments. Specifically, we used Eval monad and Cloud Haskell to develop two versions of parallel programs: plagiarism detection and K-means. Then, we evaluated the performance of the developed programs in 32-core and 120-core environments. The results of our experiment show that the Eval monad is highly efficient in an environment with a small number of cores. On the other hand, the Cloud Haskell runtime shows 37% improvement over Eval monad and the scalability shows a 134% improvement over Eval monad as the number of cores increases.
Search
Journal of KIISE
- ISSN : 2383-630X(Print)
- ISSN : 2383-6296(Electronic)
- KCI Accredited Journal
Editorial Office
- Tel. +82-2-588-9240
- Fax. +82-2-521-1352
- E-mail. chwoo@kiise.or.kr