This paper analyzes a blockchain network forming a directed acyclic graph (DAG), called a DAG-type blockchain, from the viewpoint of graph algorithm theory. To use a DAG-type blockchain, NP-hard graph optimization problems on the DAG are required to be solved. Although various problems for undirected and directed graphs can be efficiently solved by using the notions of graph parameters, these currently known parameters are meaningless for DAGs, which implies that it is hopeless to design efficient algorithms based on the parameters for such problems. In this work, we propose a novel graph parameter for directed graphs called a DAG-pathwidth, which represents the closeness to a directed path. This is an extension of the pathwidth, a well-known graph parameter for undirected graphs. We analyze the features of the DAG-pathwidth and prove that computing the DAG-pathwidth of a DAG (directed graph in general) is NP-complete. Finally, we propose an efficient algorithm for a variant of the maximum k-independent set problem for the DAG-type blockchain when the DAG-pathwidth of the input graph is small.

Register automaton (RA), register context-free grammar (RCFG) and register tree automaton (RTA) are computational models with registers which deal with data values. This paper shows pumping lemmas for the classes of languages expressed by RA, RCFG and RTA. Among them, the first lemma was already proved in terms of nominal automata, which is an abstraction of RA. We define RTA in a deterministic and bottom-up manner. For these languages, the notion of ‘pumped word’ must be relaxed in such a way that a pumped subword is not always the same as the original subword, but is any word equivalent to the original subword in terms of data type defined in this paper. By using the lemmas, we give examples of languages that do not belong to the above-mentioned classes of languages.

Register automaton (RA) is an extension of finite automaton by adding registers storing data values. RA has good properties such as the decidability of the membership and emptiness problems. Linear temporal logic with the freeze quantifier (LTL^↓) proposed by Demri and Lazić is a counterpart of RA. However, the expressive power of LTL^↓ is too high to be applied to automatic verification. In this paper, we propose a subclass of modal µ-calculus with the freeze quantifier, which has the same expressive power as RA. Since a conjunction ψ₁ ∧ ψ₂ in a general LTL^↓ formula cannot be simulated by RA, the proposed subclass prohibits at least one of ψ₁ and ψ₂ from containing the freeze quantifier or a temporal operator other than X (next). Since the obtained subclass of LTL^↓ does not have the ability to represent a cycle in RA, we adopt µ-calculus over the subclass of LTL^↓, which allows recursive definition of temporal formulas. We provide equivalent translations from the proposed subclass of µ-calculus to RA and vice versa and prove their correctness.

Recently, we introduced a new automata model, so-called colored finite automata (CFAs) whose accepting states are multi-colored (i.e., not conventional black-and-white acceptance) in order to classify their input strings into two or more languages, and solved the specific complexity problems concerning color-unmixedness of nondeterministic CFA. That is, so-called UV, UP, and UE problems are shown to be NLOG-complete, P, and NP-complete, respectively. In this paper, we apply the concept of colored accepting mechanism to pushdown automata and show that the corresponding versions of the above-mentioned complexity problems are all undecidable. We also investigate the case of unambiguous pushdown automata and show that one of the problems turns out to be permanent true (the others remain undecidable).

Multiple context-free grammar (MCFG) is an extension of context-free grammar (CFG), which generates tuples of words. The expressive power of MCFG is between CFG and context-sensitive grammar while MCFG inherits good properties of CFG. In this paper, we introduce weighted multiple context-free grammar (WMCFG) as a quantitative extension of MCFG. Then we investigate properties of WMCFG such as polynomial-time computability of basic problems, its closure property and expressive power.

Due to the limitations of cloud computing on latency, bandwidth and data confidentiality, edge computing has emerged as a novel location-aware paradigm to provide them with more processing capacity to improve the computing performance and quality of service (QoS) in several typical domains of human activity in smart society, such as social networks, medical diagnosis, telecommunications, recommendation systems, internal threat detection, transports, Internet of Things (IoT), etc. These application domains often handle a vast collection of entities with various relationships, which can be naturally represented by the graph data structure. Graph processing is a powerful tool to model and optimize complex problems in which the graph-based data is involved. In view of the relatively insufficient resource provisioning of the portable terminals, in this paper, for the first time to our knowledge, we propose an interactive and reductive graph processing library (GPL) for edge computing in smart society at low overhead. Experimental evaluation is conducted to indicate that the proposed GPL is more user-friendly and highly competitive compared with other established systems, such as igraph, NetworKit and NetworkX, based on different graph datasets over a variety of popular algorithms.

Calculation is a solitaire card game with a standard 52-card deck. Initially, cards A, 2, 3, and 4 of any suit are laid out as four foundations. The remaining 48 cards are piled up as the stock, and there are four empty tableau piles. The purpose of the game is to move all cards of the stock to foundations. The foundation starting with A is to be built up in sequence from an ace to a king. The other foundations are similarly built up, but by twos, threes, and fours from 2, 3, and 4 until a king is reached. Here, a card of rank i may be used as a card of rank i + 13j for j ∈ {0, 1, 2, 3}. During the game, the player moves (i) the top card of the stock either onto a foundation or to the top of a tableau pile, or (ii) the top card of a tableau pile onto a foundation. We prove that the generalized version of Calculation Solitaire is NP-complete.

One of the long-standing research problems on logic programming is to treat the cut predicate in a logical, high-level way. We argue that this problem can be solved by adopting linear logic and choice-disjunctive goal formulas of the form G₀ ⊕ G₁ where G₀, G₁ are goals. These goals have the following intended semantics: choose the true disjunct G_i and execute G_i where i (= 0 or 1), while discarding the unchosen disjunct. Note that only one goal can remain alive during execution. These goals thus allow us to specify mutually exclusive tasks in a high-level way. Note that there is another use of cut which is for breaking out of failure-driven loops and efficient heap management. Unfortunately, it is not possible to replace cut of this kind with use of choice-disjunctive goals.

Stereo depth estimation has become an attractive topic in the computer vision field. Although various algorithms strive to optimize the speed and the precision of estimation, the energy cost of a system is also an essential metric for an embedded system. Among these various algorithms, Semi-Global Matching (SGM) has been a popular choice for some real-world applications because of its accuracy-and-speed balance. However, its power consumption makes it difficult to be applied to an embedded system. Thus, we propose a robust stereo matching system, RT-libSGM, working on the Xilinx Field-Programmable Gate Array (FPGA) platforms. The dedicated design of each module optimizes the speed of the entire system while ensuring the flexibility of the system structure. Through an evaluation on a Zynq FPGA board called M-KUBOS, RT-libSGM achieves state-of-the-art performance with lower power consumption. Compared with the benchmark design (libSGM) working on the Tegra X2 GPU, RT-libSGM runs more than 2× faster at a much lower energy cost.

Using third-party intellectual properties (3PIP) has been a norm in IC design development process to meet the time-to-market demand and at the same time minimizing the cost. But this flow introduces a threat, such as hardware trojan, which may compromise the security and trustworthiness of underlying hardware, like disclosing confidential information, impeding normal execution and even permanent damage to the system. In years, different detections methods are explored, from just identifying if the circuit is infected with hardware trojan using conventional methods to applying machine learning where it identifies which nets are most likely are hardware trojans. But the performance is not satisfactory in terms of maximizing the detection rate and minimizing the false positive rate. In this paper, a new hardware trojan detection approach is proposed where gate-level netlist is segmented into regions first before analyzing which nets might be hardware trojans. The segmentation process depends on the nets' connectivity, more specifically by looking on each fanout points. Then, further analysis takes place by means of computing the structural similarity of each segmented region and differentiate hardware trojan nets from normal nets. Experimental results show 100% detection of hardware trojan nets inserted on each benchmark circuits and an overall average of 1.38% of false positive rates which resulted to a higher accuracy with an average of 99.31%.

Ordinal regression is used to classify instances by considering ordinal relation between labels. Existing methods tend to decrease the accuracy when they adhere to the preservation of the ordinal relation. Therefore, we propose a distributional knowledge-based network (DK-net) that considers ordinal relation while maintaining high accuracy. DK-net focuses on image datasets. However, in industrial applications, one can find not only image data but also tabular data. In this study, we propose DK-neural oblivious decision ensemble (NODE), an improved version of DK-net for tabular data. DK-NODE uses NODE for feature extraction. In addition, we propose a method for adjusting the parameter that controls the degree of compliance with the ordinal relation. We experimented with three datasets: WineQuality, Abalone, and Eucalyptus dataset. The experiments showed that the proposed method achieved high accuracy and small MAE on three datasets. Notably, the proposed method had the smallest average MAE on all datasets.

The equilibrium optimizer (EO) is a novel physics-based meta-heuristic optimization algorithm that is inspired by estimating dynamics and equilibrium states in controlled volume mass balance models. As a stochastic optimization algorithm, EO inevitably produces duplicated solutions, which is wasteful of valuable evaluation opportunities. In addition, an excessive number of duplicated solutions can increase the risk of the algorithm getting trapped in local optima. In this paper, an improved EO algorithm with a bis-population-based non-revisiting (BNR) mechanism is proposed, namely BEO. It aims to eliminate duplicate solutions generated by the population during iterations, thus avoiding wasted evaluation opportunities. Furthermore, when a revisited solution is detected, the BNR mechanism activates its unique archive population learning mechanism to assist the algorithm in generating a high-quality solution using the excellent genes in the historical information, which not only improves the algorithm's population diversity but also helps the algorithm get out of the local optimum dilemma. Experimental findings with the IEEE CEC2017 benchmark demonstrate that the proposed BEO algorithm outperforms other seven representative meta-heuristic optimization techniques, including the original EO algorithm.

In many situations, abnormal sounds, called adventitious sounds, are included with the lung sounds of a subject suffering from pulmonary diseases. Thus, a method to automatically detect abnormal sounds in auscultation was proposed. The acoustic features of normal lung sounds for control subjects and abnormal lung sounds for patients are expressed using hidden markov models (HMMs) to distinguish between normal and abnormal lung sounds. Furthermore, abnormal sounds were detected in a noisy environment, including heart sounds, using a heart-sound model. However, the F1-score obtained in detecting abnormal respiration was low (0.8493). Moreover, the duration and acoustic properties of segments of respiratory, heart, and adventitious sounds varied. In our previous method, the appropriate HMMs for the heart and adventitious sound segments were constructed. Although the properties of the types of adventitious sounds varied, an appropriate topology for each type was not considered. In this study, appropriate HMMs for the segments of each type of adventitious sound and other segments were constructed. The F1-score was increased (0.8726) by selecting a suitable topology for each segment. The results demonstrate the effectiveness of the proposed method.

3D reconstruction methods using neural networks are popular and have been studied extensively. However, the resulting models typically lack detail, reducing the quality of the 3D reconstruction. This is because the network is not designed to capture the fine details of the object. Therefore, in this paper, we propose two networks designed to capture both the coarse and fine details of the object to improve the reconstruction of the detailed parts of the object. To accomplish this, we design two networks. The first network uses a multi-scale architecture with skip connections to associate and merge features from other levels. For the second network, we design a multi-branch deep generative network that separately learns the local features, generic features, and the intermediate features through three different tailored components. In both network architectures, the principle entails allowing the network to learn features at different levels that can reconstruct the fine parts and the overall shape of the reconstructed 3D model. We show that both of our methods outperformed state-of-the-art approaches.

In this paper we propose an extension of the Attention Branch Network (ABN) by using instance segmentation for generating sharper attention maps for action recognition. Methods for visual explanation such as Grad-CAM usually generate blurry maps which are not intuitive for humans to understand, particularly in recognizing actions of people in videos. Our proposed method, Object-ABN, tackles this issue by introducing a new mask loss that makes the generated attention maps close to the instance segmentation result. Further the Prototype Conformity (PC) loss and multiple attention maps are introduced to enhance the sharpness of the maps and improve the performance of classification. Experimental results with UCF101 and SSv2 shows that the generated maps by the proposed method are much clearer qualitatively and quantitatively than those of the original ABN.

Object detection is one of the most important aspects of computer vision, and the use of CNNs for object detection has yielded substantial results in a variety of fields. However, due to the fixed sampling in standard convolution layers, it restricts receptive fields to fixed locations and limits CNNs in geometric transformations. This leads to poor performance of CNNs for slender object detection. In order to achieve better slender object detection accuracy and efficiency, this proposed detector DFAM-DETR not only can adjust the sampling points adaptively, but also enhance the ability to focus on slender object features and extract essential information from global to local on the image through an attention mechanism. This study uses slender objects images from MS-COCO dataset. The experimental results show that DFAM-DETR achieves excellent detection performance on slender objects compared to CNN and transformer-based detectors.

Many optimisation algorithms improve the algorithm from the perspective of population structure. However, most improvement methods simply add hierarchical structure to the original population structure, which fails to fundamentally change its structure. In this paper, we propose an umbrellalike hierarchical artificial bee colony algorithm (UHABC). For the first time, a historical information layer is added to the artificial bee colony algorithm (ABC), and this information layer is allowed to interact with other layers to generate information. To verify the effectiveness of the proposed algorithm, we compare it with the original artificial bee colony algorithm and five representative meta-heuristic algorithms on the IEEE CEC2017. The experimental results and statistical analysis show that the umbrellalike mechanism effectively improves the performance of ABC.

Soil moisture sensor calibration based on the Multivariate Adaptive Regression Splines (MARSplines) model is studied in this paper. Different from the generic polynomial fitting methods, the MARSplines model is a non-parametric model, and it is able to model the complex relationship between the actual and measured soil moisture. Rao-1 algorithm is employed to tune the hyper-parameters of the calibration model and thus the performance of the proposed method is further improved. Data collected from four commercial soil moisture sensors is utilized to verify the effectiveness of the proposed method. To assess the calibration performance, the proposed model is compared with the model without using the temperature information. The numeric studies prove that it is promising to apply the proposed model for real applications.

In this article, a GUI system is proposed to support clinical cardiology examinations. The proposed system estimates “pulmonary artery wedge pressure” based on patients' chest radiographs using an explainable regression-based convolutional neural network. The GUI system was validated by performing an effectiveness survey with 23 cardiology physicians with medical licenses. The results indicated that many physicians considered the GUI system to be effective.

We characterized prion disease by comparing brain functional connectivity network (BFCN), which were constructed by 16-ch scalp-recorded electroencephalograms (EEGs). The connectivity between each pair of nodes (electrodes) were computed by synchronization likelihood (SL). The BFCN was applied to graph theory to discriminate prion disease patients from healthy elderlies and dementia groups.