Shinobu NAGAYAMA Tsutomu SASAO Jon T. BUTLER
This paper proposes a decomposition method for symmetric multiple-valued functions. It decomposes a given symmetric multiple-valued function into three parts. By using suitable decision diagrams for the three parts, we can represent symmetric multiple-valued functions compactly. By deriving theorems on sizes of the decision diagrams, this paper shows that space complexity of the proposed representation is low. This paper also presents algorithms to construct the decision diagrams for symmetric multiple-valued functions with low time complexity. Experimental results show that the proposed method represents randomly generated symmetric multiple-valued functions more compactly than the conventional representation method using standard multiple-valued decision diagrams. Symmetric multiple-valued functions are a basic class of functions, and thus, their compact representation benefits many applications where they appear.
Nihad A. A. ELHAG Liang LIU Ping WEI Hongshu LIAO Lin GAO
The concept of dual function radar-communication (DFRC) provides solution to the problem of spectrum scarcity. This paper examines a multiple-input multiple-output (MIMO) DFRC system with the assistance of a reconfigurable intelligent surface (RIS). The system is capable of sensing multiple spatial directions while serving multiple users via orthogonal frequency division multiplexing (OFDM). The objective of this study is to design the radiated waveforms and receive filters utilized by both the radar and users. The mutual information (MI) is used as an objective function, on average transmit power, for multiple targets while adhering to constraints on power leakage in specific directions and maintaining each user’s error rate. To address this problem, we propose an optimal solution based on a computational genetic algorithm (GA) using bisection method. The performance of the solution is demonstrated by numerical examples and it is shown that, our proposed algorithm can achieve optimum MI and the use of RIS with the MIMO DFRC system improving the system performance.
Modern high-level programming languages have a wide variety of grammar and can implement the required functionality in different ways. The authors believe that a large amount of code that implements the same functionality in different ways exists even in open source software where the source code is publicly available, and that by collecting such code, a useful data set can be constructed for various studies in software engineering. In this study, we construct a dataset of pairs of Java methods that have the same functionality but different structures from approximately 314 million lines of source code. To construct this dataset, the authors used an automated test generation technique, EvoSuite. Test cases generated by automated test generation techniques have the property that the test cases always succeed. In constructing the dataset, using this property, test cases generated from two methods were executed against each other to automatically determine whether the behavior of the two methods is the same to some extent. Pairs of methods for which all test cases succeeded in cross-running test cases are manually investigated to be functionally equivalent. This paper also reports the results of an accuracy evaluation of code clone detection tools using the constructed dataset. The purpose of this evaluation is assessing how accurately code clone detection tools could find the functionally equivalent methods, not assessing the accuracy of detecting ordinary clones. The constructed dataset is available at github (https://github.com/YoshikiHigo/FEMPDataset).
Chisho TAKEOKA Toshimasa YAMAZAKI Yoshiyuki KUROIWA Kimihiro FUJINO Toshiaki HIRAI Hidehiro MIZUSAWA
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.
Various types of indices for estimating functional connectivity have been developed over the years that have introduced effective approaches to discovering complex neural networks in the brain. Two significant examples are the phase lag index (PLI) and transfer entropy (TE). Both indices have specific benefits; PLI, defined using instantaneous phase dynamics, achieves high spatiotemporal resolution, whereas transfer entropy (TE), defined using information flow, reveals directed network characteristics. However, the relationship between these indices remains unclear. In this study, we hypothesize that there exists a complementary relationship between PLI and TE to discover new aspects of functional connectivity that cannot be detected using either PLI or TE. To validate this hypothesis, we evaluated the synchronization in a coupled Rössler model using PLI and TE. Consequently, we proved the existence of non-linear relationships between PLI and TE. Both indexes exhibit a specific trend that demonstrates a linear relationship in the region of small TE values. However, above a specific TE value, PLI converges to a constant irrespective of the TE value. In addition to this relational difference in synchronization, there is another characteristic difference between these indices. Moreover, by virtue of its finer temporal resolution, PLI can capture the temporal variability of the degree of synchronization, which is called dynamical functional connectivity. TE lacks this temporal characteristic because it requires a longer evaluation period in this estimation process. Therefore, combining the advantages of both indices might contribute to revealing complex spatiotemporal functional connectivity in brain activity.
Fukashi MORISHITA Wataru SAITO Norihito KATO Yoichi IIZUKA Masao ITO
This paper proposes novel test techniques for high accuracy measurement of ADCs and a ramp generator on a CMOS image sensor (CIS) chip. The test circuit for the ADCs has a dual path and has an ability of multi-functional fine pattern generator that can define any input for each column to evaluate CIS specific characteristics electrically. The test circuit for the ramp generator can realize an on-chip current cell test and reject the current cell failure within 1LSB accuracy. We fabricated the test sensor using 55nm CIS process and measured the IP characteristics. Measured results show INL of 14.6LSB, crosstalk of 14.9LSB and column interference noise of 5.4LSB. These measured results agree with the designed values. By using this technique, we confirmed the accurate ADC measurement can be realized without being affected by the ambiguity of the optical input.
Wenhao FAN Dong LIU Fan WU Bihua TANG Yuan'an LIU
Android operating system occupies a high share in the mobile terminal market. It promotes the rapid development of Android applications (apps). However, the emergence of Android malware greatly endangers the security of Android smartphone users. Existing research works have proposed a lot of methods for Android malware detection, but they did not make the utilization of apps' functional category information so that the strong similarity between benign apps in the same functional category is ignored. In this paper, we propose an Android malware detection scheme based on the functional classification. The benign apps in the same functional category are more similar to each other, so we can use less features to detect malware and improve the detection accuracy in the same functional category. The aim of our scheme is to provide an automatic application functional classification method with high accuracy. We design an Android application functional classification method inspired by the hyperlink induced topic search (HITS) algorithm. Using the results of automatic classification, we further design a malware detection method based on app similarity in the same functional category. We use benign apps from the Google Play Store and use malware apps from the Drebin malware set to evaluate our scheme. The experimental results show that our method can effectively improve the accuracy of malware detection.
Kaiyu WANG Sichen TAO Rong-Long WANG Yuki TODO Shangce GAO
In 2019, a new selection method, named fitness-distance balance (FDB), was proposed. FDB has been proved to have a significant effect on improving the search capability for evolutionary algorithms. But it still suffers from poor flexibility when encountering various optimization problems. To address this issue, we propose a functional weights-enhanced FDB (FW). These functional weights change the original weights in FDB from fixed values to randomly generated ones by a distribution function, thereby enabling the algorithm to select more suitable individuals during the search. As a case study, FW is incorporated into the spherical search algorithm. Experimental results based on various IEEE CEC2017 benchmark functions demonstrate the effectiveness of FW.
Nuttapong ATTRAPADUNG Goichiro HANAOKA Takato HIRANO Yutaka KAWAI Yoshihiro KOSEKI Jacob C. N. SCHULDT
In this paper, we put forward the notion of a token-based multi-input functional encryption (token-based MIFE) scheme - a notion intended to give encryptors a mechanism to control the decryption of encrypted messages, by extending the encryption and decryption algorithms to additionally use tokens. The basic idea is that a decryptor must hold an appropriate decryption token in addition to his secrete key, to be able to decrypt. This type of scheme can address security concerns potentially arising in applications of functional encryption aimed at addressing the problem of privacy preserving data analysis. We firstly formalize token-based MIFE, and then provide two basic schemes; both are based on an ordinary MIFE scheme, but the first additionally makes use of a public key encryption scheme, whereas the second makes use of a pseudorandom function (PRF). Lastly, we extend the latter construction to allow decryption tokens to be restricted to specified set of encryptions, even if all encryptions have been done using the same encryption token. This is achieved by using a constrained PRF.
Yasunori ISHIHARA Takashi HAYATA Toru FUJIWARA
This paper discusses a static analysis problem, called absolute consistency problem, for relational schema mappings. A given schema mapping is said to be absolutely consistent if every source instance has a corresponding target instance. Absolute consistency is an important property because it guarantees that data exchange never fails for any source instance. Originally, for XML schema mappings, the absolute consistency problem was defined and its complexity was investigated by Amano et al. However, as far as the authors know, there are no known results for relational schema mappings. In this paper, we focus on relational schema mappings such that both the source and the target schemas have functional dependencies, under the assumption that mapping rules are defined by constant-free tuple-generating dependencies. In this setting, we show that the absolute consistency problem is in coNP. We also show that it is solvable in polynomial time if the tuple-generating dependencies are full and the size of the left-hand side of each functional dependency is bounded by some constant. Finally, we show that the absolute consistency problem is coNP-hard even if the source schema has no functional dependency and the target schema has only one; or each of the source and the target schemas has only one functional dependency such that the size of the left-hand side of the functional dependency is at most two.
Computation methods using custom circuits are frequently employed to improve the throughput and power efficiency of computing systems. Hardware development, however, can incur significant development costs because designs at the register-transfer level (RTL) with a hardware description language (HDL) are time-consuming. This paper proposes a hardware and software co-design environment, named Mulvery, which is designed for non-professional hardware designer We focus on the similarities between functional reactive programming (FRP) and dataflow in computation. This study provides an idea to design hardware with a dynamic typing language, such as Ruby, using FRP and provides the proof-of-concept of the method. Mulvery, which is a hardware and software co-design tool based on our method, reduces development costs. Mulvery exhibited high performance compared with software processing techniques not equipped with hardware knowledge. According to the experiment, the method allows us to design hardware without degradation of performance. The sample application applied a Laplacian filter to an image with a size of 128×128 and processed a convolution operation within one clock.
Junichi TOMIDA Masayuki ABE Tatsuaki OKAMOTO
Inner product functional encryption (IPFE) is a subclass of functional encryption (FE), whose function class is limited to inner product. We construct an efficient private-key IPFE scheme with full-hiding security, where confidentiality is assured for not only encrypted data but also functions associated with secret keys. Recently, Datta et al. presented such a scheme in PKC 2016 and this is the only scheme that achieves full-hiding security. Our scheme has an advantage over their scheme for the two aspects. More efficient: keys and ciphertexts of our scheme are almost half the size of those of their scheme. Weaker assumption: our scheme is secure under the k-linear (k-Lin) assumption, while their scheme is secure under a stronger assumption, namely, the symmetric external Diffie-Hellman (SXDH) assumption. It is well-known that the k-Lin assumption is equivalent to the SXDH assumption when k=1 and becomes weak as k increases.
Hiroto TANAKA Shinsuke MATSUMOTO Shinji KUSUMOTO
Over the past recent decades, numerous programming languages have expanded to embrace multi-paradigms such as the fusion of object-oriented and functional programming. For example, Java, one of the most famous object-oriented programming languages, introduced a number of functional idioms in 2014. This evolution enables developers to achieve various benefits from both paradigms. However, we do not know how Java developers use functional idioms actually. Additionally, the extent to which, while there are several criticisms against the idioms, the developers actually accept and/or use the idioms currently remains unclear. In this paper, we investigate the actual use status of three functional idioms (Lambda Expression, Stream, and Optional) in Java projects by mining 100 projects containing approximately 130,000 revisions. From the mining results, we determined that Lambda Expression is utilized in 16% of all the examined projects, whereas Stream and Optional are only utilized in 2% to 3% of those projects. It appears that most Java developers avoid using functional idioms just because of keeping compatibility Java versions, while a number of developers accept these idioms for reasons of readability and runtime performance improvements. Besides, when they adopt the idioms, Lambda Expression frequently consists of a single statement, and Stream is used to operate the elements of a collection. On the other hand, some developers implement Optional using deprecated methods. We can say that good usage of the idioms should be widely known among developers.
Takahiro NAKAYAMA Masanori HASHIMOTO
VLSIs that perform signal processing near infrared sensors cooled to ultra-low temperature are demanded. Delay test of those chips must be executed at ultra-low temperature while functional test could be performed at room temperature as long as hold timing errors do not occur. In this letter, we focus on the hold timing violation and evaluate the feasibility of functional test of ultra-low temperature circuits at room temperature. Experimental evaluation with a case study shows that the functional test at room temperature is possible.
Siyu CHEN Ning WANG Mengmeng ZHANG
We propose to discover approximate primary functional dependency (aPFD) for web tables, which focus on the determination relationship between primary attributes and non-primary attributes and are more helpful for entity column detection and topic discovery on web tables. Based on association rules and information theory, we propose metrics Conf and InfoGain to evaluate PFDs. By quantifying PFDs' strength and designing pruning strategies to eliminate false positives, our method could select minimal non-trivial approximate PFD effectively and are scalable to large tables. The comprehensive experimental results on real web datasets show that our method significantly outperforms previous work in both effectiveness and efficiency.
Yuma MATSUMOTO Takayuki OMORI Hiroya ITOGA Atsushi OHNISHI
In order to verify the correctness of functional requirements, we have been developing a verification method of the correctness of functional requirements specification using the Requirements Frame model. In this paper, we propose a verification method of non-functional requirements specification in terms of time-response requirements written with a natural language. We established a verification method by extending the Requirements Frame model. We have also developed a prototype system based on the method using Java. The extended Requirements Frame model and the verification method will be illustrated with examples.
Functional encryption is a new paradigm of public-key encryption that allows a user to compute f(x) on encrypted data CT(x) with a private key SKf to finely control the revealed information. Multi-input functional encryption is an important extension of (single-input) functional encryption that allows the computation f(x1,...,xn) on multiple ciphertexts CT(x1),...,CT(xn) with a private key SKf. Although multi-input functional encryption has many interesting applications like running SQL queries on encrypted database and computation on encrypted stream, current candidates are not yet practical since many of them are built on indistinguishability obfuscation. To solve this unsatisfactory situation, we show that practical two-input functional encryption schemes for inner products can be built based on bilinear maps. In this paper, we first propose a two-input functional encryption scheme for inner products in composite-order bilinear groups and prove its selective IND-security under simple assumptions. Next, we propose a two-client functional encryption scheme for inner products where each ciphertext can be associated with a time period and prove its selective IND-security. Furthermore, we show that our two-input functional encryption schemes in composite-order bilinear groups can be converted into schemes in prime-order asymmetric bilinear groups by using the asymmetric property of asymmetric bilinear groups.
We have previously introduced the static dependency pair method that proves termination by analyzing the static recursive structure of various extensions of term rewriting systems for handling higher-order functions. The key is to succeed with the formalization of recursive structures based on the notion of strong computability, which is introduced for the termination of typed λ-calculi. To bring the static dependency pair method close to existing functional programs, we also extend the method to term rewriting models in which functional abstractions with patterns are permitted. Since the static dependency pair method is not sound in general, we formulate a class; namely, accessibility, in which the method works well. The static dependency pair method is a very natural reasoning; therefore, our extension differs only slightly from previous results. On the other hand, a soundness proof is dramatically difficult.
Shota ISHIMURA Byung-Gon KIM Kazuki TANAKA Shinobu NANBA Kosuke NISHIMURA Hoon KIM Yun C. CHUNG Masatoshi SUZUKI
The intermediate frequency-over-fiber (IFoF) technology has attracted attention as an alternative transmission scheme to the functional split for the next-generation mobile fronthaul links due to its high spectral efficiency and perfect centralized control ability. In this paper, we discuss and clarify network architectures suited for IFoF, based on its advantages over the functional split. One of the major problems for IFoF transmission is dispersion-induced RF power fading, which limits capacity and transmission distance. We introduce our previous work, in which high-capacity and long-distance IFoF transmission was demonstrated by utilizing a parallel intensity/phase modulators (IM/PM) transmitter which can effectively avoid the fading. The IFoF technology with the proposed scheme is well suited for the long-distance mobile fronthaul links for the 5th generation (5G) mobile system and beyond.
Nurul AIN BINTI ADNAN Shigeru YAMASHITA Alan MISHCHENKO
This paper presents a technique to reduce the quantum cost by making temporary changes to the functionality of a given Boolean function. This technique is one of the very few known methods based on manipulating Exclusive-or Sum-Of-Products (ESOP) expressions to reduce the quantum cost of the corresponding circuit. The idea involves adding Mixed Polarity Multiple-Control Toffoli (MPMCT) gates to temporarily change the functionality of the given function, so that the modified function has a smaller quantum cost. To compensate for the temporary change, additional gates are inserted into the circuit. The proposed method finds a small ESOP expression for the given function, and then finds a good pair of product terms in the ESOP expression so that the quantum cost can be reduced by applying the transformation. The proposed approach is likely to produce a better quantum cost reduction than the existing methods, and indeed experimental results confirm this expectation.