Search

Among many variations of pencil puzzles, Latin square Completion-Type puzzles (LSCP), such as Sudoku, Futoshiki and BlockSum, are quite popular for puzzle fans. Concerning these puzzles, the solvability has been investigated from the viewpoint of time complexity in the last decade; it has been shown that, in most of these puzzles, it is NP-complete to determine whether a given puzzle instance has a proper solution. In this paper, we investigate the approximability of LSCP. We formulate LSCP as the maximization problem that asks to fill as many cells as possible, under the Latin square condition and the inherent condition. We then propose simple generic approximation algorithms for LSCP and analyze their approximation ratios.

Equational theories that contain axioms expressing associativity and commutativity (AC) of certain operators are ubiquitous. Theorem proving methods in such theories rely on well-founded orders that are compatible with the AC axioms. In this paper we consider various definitions of AC-compatible Knuth-Bendix orders. The orders of Steinbach and of Korovin and Voronkov are revisited. The former is enhanced to a more powerful version, and we modify the latter to amend its lack of monotonicity on non-ground terms. We further present new complexity results. An extension reflecting the recent proposal of subterm coefficients in standard Knuth-Bendix orders is also given. The various orders are compared on problems in termination and completion., 31 pages, To appear in Theory and Practice of Logic Programming (TPLP) special issue for the 12th International Symposium on Functional and Logic Programming (FLOPS 2014)

This paper presents an agent-based simulator to investigating customer walking flows and purchasing behaviors in a super market. So far, such investigations have cost very much to examine in real situations. The simulator enables us to carry out "virtual experiments" through changing various parameters of retail businesses and store operations. For this purpose, first we observe an actual retail store and analyze sales data. Then we develop the simulation model: Agent-Based In-Store Simulator (ABISS). Intensive experiments have revealed that the flow of customers, which is related to the sales, depends on the design of a store and that the places of in-store advertisement and recommendation system vary their sales.

This paper, we focus on recommendation functions to extract the high potential sales items from the trend leaders' activities with the ID (Identification)-POS (Point-Of-Sales) data. Although the recommendation system is in common among the B2B or B2C businesses, the conventional recommendation engines provide the proper results; therefore, we need to improve the algorithms for the recommendation. We have defined the index of the trend leader with the criteria for the day and the sales number. Using with the results, we are able to make detailed decisions in the following three points: 1) to make appropriate recommendations to the other group member based on the transitions of the trend leaders' preferences; 2) to evaluate the effect of the recommendation with the trend leaders' preferences; and 3) to improve the retail management processes: prevention from the stock-out, sales promotion for early purchase effects and the increase of the numbers of sales.

An Attribute-Based Encryption (ABE) is an encryption scheme, where users with some attributes can decrypt ciphertexts associated with these attributes. However, the length of the ciphertext depends on the number of attributes in previous ABE schemes. In this paper, we propose a new Ciphertext-Policy Attribute-Based Encryption(CP-ABE) with constant ciphertext length. Moreover, the number of pairing computations is also constant., Proceedings of the 5th International Conference, ISPEC 2009 Xi’an, China, April 13-15, 2009.

Energy consumption is a fundamental barrier in taking full advantage of today and future semiconductor manufacturing technologies. This paper presents our recent research activities and results on estimating and reducing energy consumption in nanometer technology system LSIs. This includes techniques and tools for (i) estimating instantaneous energy consumption of embedded processors during an application execution, and (ii) reducing leakage energy in instruction cache memories by taking advantage of value-dependence of SRAM leakage due to within-die V th variation.

This paper presents an approach to assist engineers in modeling and capturing abnormal situations. In these days, safety becomes a social strict requirement in the process industry. An incident influences the competitiveness and/or sustainability. Therefore, PHA has been carried out through the lifecycle. However, incidents and/or disasters occur as ever, and many incident investigation reports point out incompleteness of PHA, and reputation of past experienced similar incidents. In this study, a generic exchangeable representation of incident information is proposed. Our approach is based on the knowledge representation of both the plant structure and the abnormal events. A computer implementation is presented to demonstrate the efficacy of the representation method. Finally, a case study is included to illustrate the application of the proposed approach.

Consider a rooted directed acyclic graph G = (V, E) with root r, representing a collection V of web pages connected via a set E of hyperlinks. Each node v is associated with the probability that a user wants to access the node v. The access cost is defined as the expected number of steps required to reach a node from the root r. A bookmark is an additional shortcut from r to a node of G, which may reduce the access cost. The bookmark assignment problem is to find a set of bookmarks that achieves the greatest improvement in the access cost. For the problem, the paper presents a polynomial time approximation algorithm with factor (1 − 1/e), and shows that there exists no polynomial time approximation algorithm with a better constant factor than (1 − 1/e) unless ${cal NP}subseteq {cal DTIME}(N^{O(loglog N)})$ , where N is the size of the inputs.

As one simple type of statistical inference problems we consider Most Likely Solution problem, a task of finding a most likely solution (MLS in short) for a given problem instance under some given probability model. Although many MLS problems are NP-hard, we propose, for these problems, to study their average-case complexity under their assumed probabality models. We show three examples of MLS problems, and explain that "message passing algorithms" (e.g., belief propagation) work reasonably well for these problems. Some of the technical results of this paper are from the author's recent joint work with his colleagues [WST, WY06, OW06] .

Seki is a situation of coexistence in the game of Go, where neither player can profitably capture the opponent's stones. This paper presents a new method for deciding whether an enclosed area is or can become a seki. The method combines local search with global-level static analysis. Local search is used to identify possible seki, and reasoning on the global level is applied to determine which stones are safe with territory, which coexist in a seki and which are dead. Experimental results show that a safety-of-territory solver enhanced by this method can successfully recognize a large variety of local and global scale test positions related to seki. In contrast, the well-known program GNU Go can only solve easier problems from a test collection.

To practically solve NP-hard combinatorial optimizationproblems, local search algorithms and their parallel implementations on PVM or MPI have been frequently discussed. Since a huge number of neighbors may be examined to discover a locally optimal neighbor in each of local search calls, many of parallelization schemes, excluding so-called the multi-start parallel scheme, try to extract parallelism from a local search by distributing the examinations of neighbors to processors. However, in straightforward implementations, when the next local search starts, all the processors will be assigned to the neighbors of the latest solution, and the results of all (but one) examinations in the previous local search are thus discarded in vain, despite that they would contain useful information on further search. This paper explores the possibility of extracting information even from unsuccessful neighbor examinations in a systematic way to boost parallel local search algorithms. Our key concept is neighborhood composition. We demonstrate how this idea improves parallel implementations on PVM, by taking as examples well-known local search algorithms for the Traveling Salesman Problem.

Developing automatable methods for proving termination of term rewrite systems that resist traditional techniques based on simplification orders has become an active research area in the past few years. The dependency pair method of Arts and Giesl is one of the most popular such methods. However, there are several obstacles that hamper its automation. In this paper we present new ideas to overcome these obstacles. We provide ample numerical data supporting our ideas., Proceedings of the 19th International Conference on Automated Deduction, Miami Beach, FL, USA, July 28 – August 2, 2003.

In this paper, we introduce the Datarol-II processor, that can efficiently execute a fine-grain multi-thread program, called Datarol. In order to achieve the efficient multi-thread execution by reducing context switching overhead, we introduce an implicit register load/store mechanism in the execution pipeline. A two-level hierarchical memory system is also introduced in order to reduce memory access latency. The simulation results show that the Datarol-II processor can tolerate remote memory access latencies and execute a fine-grain multi-thread program efficiently.

In case of abnormal situation of chemical process plant, it is required to judge the plant condition correctly and carry out the unerring response. Many operation support systems were proposed to help the plant operator with such judgment and operation decision making, but most of them could not indicate the rationale for operation, because they used only information on the result of plant design. Therefore, plant operator could not get the theoretical information for operation decision making from it. This paper proposes the safety operation support system which helps the operation decision making based on the risk management information (RMI). The RMI is useful one for the theoretical operation decision making, because it is considered and updated through the plant life cycle (PLC) and includes the information on the design rationale (DR) of the safety countermeasure, the intents of corresponding operation, etc. PVC batch process is used for verifying the effectiveness of proposed method.