Obtaining shorter regular expressions from finite-state automata

We consider the use of state elimination to construct shorter regular expressions from finite-state automata (FAs). Although state elimination is an intuitive method for computing regular expressions from FAs, the resulting regular expressions are often very long and complicated. We examine the minimization of FAs to obtain shorter expressions first. Then, we introduce vertical chopping based on bridge states and horizontal chopping based on the structural properties of given FAs. We prove that we should not eliminate bridge states until we eliminate all non-bridge states to obtain shorter regular expressions. In addition, we suggest heuristics for state elimination that leads to shorter regular expressions based on vertical chopping and horizontal chopping.     

Pseudo-inversion: closure properties and decidability

We consider a pseudo-inversion operation inspired by biological events, such as DNA sequence transformations, where only parts of a string are reversed. We define the pseudo-inversion of a string \(w = uxv\) to be the set of all strings \(v^Rxu^R\), where \(uv \ne \lambda \) and consider the operation from a formal language theoretic viewpoint. We show that regular languages are closed under the pseudo-inversion operation whereas context-free languages are not. Furthermore, we study the iterated pseudo-inversion operation and show that the iterated pseudo-inversion of a context-free language is recognized by a nondeterministic reversal-bounded multicounter machine. Finally, we introduce the notion of pseudo-inversion-freeness and examine closure properties and decidability problems for regular and context-free languages. We demonstrate that pseudo-inversion-freeness is decidable in polynomial time for regular languages and undecidable for context-free languages.     

State complexity of basic operations on suffix-free regular languages

We investigate the state complexity of basic operations for suffix-free regular languages. The state complexity of an operation for regular languages is the number of states that are necessary and sufficient in the worst-case for the minimal deterministic finite-state automaton that accepts the language obtained from the operation. We establish the precise state complexity of catenation, Kleene star, reversal and the Boolean operations for suffix-free regular languages.     

A Speculative Parallel DFA Membership Test for Multicore,SIMD and Cloud Computing Environments

We present techniques to parallelize membership tests for Deterministic Finite Automata (DFAs). Our method searches arbitrary regular expressions by matching multiple bytes in parallel using speculation. We partition the input string into chunks, match chunks in parallel, and combine the matching results. Our parallel matching algorithm exploits structural DFA properties to minimize the speculative overhead. Unlike previous approaches, our speculation is failure-free, i.e., (1) sequential semantics are maintained, and (2) speed-downs are avoided altogether. On architectures with a SIMD gather-operation for indexed memory loads, our matching operation is fully vectorized. The proposed load-balancing scheme uses an off-line profiling step to determine the matching capacity of each participating processor. Based on matching capacities, DFA matches are load-balanced on inhomogeneous parallel architectures such as cloud computing environments. We evaluated our speculative DFA membership test for a representative set of benchmarks from the Perl-compatible Regular Expression (PCRE) library and the PROSITE protein database. Evaluation was conducted on a 4 CPU (40 cores) shared-memory node of the Intel Academic Program Manycore Testing Lab (Intel MTL), on the Intel AVX2 SDE simulator for 8-way fully vectorized SIMD execution, and on a 20-node (288 cores) cluster on the Amazon EC2 computing cloud. Obtained speedups are on the order of $\mathcal O \left( 1+\frac{|P|-1}{|Q|\cdot \gamma }\right) $ , where $|P|$ denotes the number of processors or SIMD units, $|Q|$ denotes the number of DFA states, and $0<\gamma \le 1$ represents a statically computed DFA property. For all observed cases, we found that $0.02<\gamma <0.47$ . Actual speedups range from 2.3 $\times $ to 38.8 $\times $ for up to 512 DFA states for PCRE, and between 1.3 $\times $ and 19.9 $\times $ for up to 1,288 DFA states for PROSITE on a 40-core MTL node. Speedups on the EC2 computing cloud range from 5.0 $\times $ to 65.8 $\times $ for PCRE, and from 5.0 $\times $ to 138.5 $\times $ for PROSITE. Speedups of our C-based DFA matcher over the Perl-based ScanProsite scan tool range from 559.3 $\times $ to 15079.7 $\times $ on a 40-core MTL node. We show the scalability of our approach for input-sizes of up to 10 GB.     

A movie recommendation algorithm based on genre correlations

Since the late 20th century, the number of Internet users has increased dramatically, as has the number of Web searches performed on a daily basis and the amount of information available. A huge amount of new information is transferred to the Web on a daily basis. However, not all data are reliable and valuable, which implies that it may become more and more difficult to obtain satisfactory results from Web searches. We often iterate searches several times to find what we are looking for. To solve this problem, researchers have suggested the use of recommendation systems. Instead of searching for the same information several times, a recommendation system proposes relevant information. In the Web 2.0 era, recommendation systems often rely on collaborative filtering by users. In general, a collaborative filtering approach based on user information such as gender, location, or preference is effective. However, the traditional approach can fail due to the cold-start problem or the sparsity problem, because initial user information is required for this approach to be effective. Recently, several attempts have been made to tackle these collaborative filtering problems. One such attempt used category correlations of contents. For instance, a movie has genre information provided by movie experts and directors. This category information is more reliable than user ratings. Moreover, newly created content always has category information, allowing avoidance of the cold-start problem. In this study, we consider a movie recommendation system and improve the previous algorithms based on genre correlations to correct its shortcomings. We also test the modified algorithm and analyze the results with respect to two characteristics of genre correlations.     

Representative reviewers for Internet social media

Our many various relationships with persons from home, work and school give rise to our social networks. In a social network, people receive, provide, and pass a great deal of information. In this process, we often observe that certain individuals have especially strong influences on others. We call these highly influential people opinion leaders. Since the late 20th century, the number of Internet users has increased rapidly, and a huge number of people now interact with each other in online social networks. In this way, the Web community has become similar to real-world society. Internet users receive information not only from the mass media, but also from opinion leaders. For example, online articles posted by influential bloggers are often used as marketing tools or political advertisements, due to their huge influence on other users. Therefore, it is important and useful to identify the influential users in an online society. We thus propose a simple yet reliable algorithm that identifies opinion leaders in a cyber social network. In this paper, we first describe our algorithm for identifying influential users in an online society. We then demonstrate the validity of the selection of representative reviewers using the Yahoo! music and GroupLens movie databases and performing 10-fold cross-validation and z-tests.