33178664
Dependency Pairs for Simply Typed Term Rewriting
Simply typed term rewriting proposed by Yamada (RTA, 2001) is a framework of higher-order term rewriting without bound variables. In this paper, the dependency pair method of first-order term rewriting introduced by Arts and Giesl (TCS, 2000) is extended in order to show termination of simply typed term rewriting systems. Basic concepts such as dependency pairs and estimated dependency graph in the simply typed term rewriting framework are clarified. The subterm criterion introduced by Hirokawa and Middeldorp (RTA, 2004) is successfully extended to the case where terms of function type are allowed. Finally, an experimental result for a collection of simply typed term rewriting systems is presented. Our method is compared with the direct application of the first-order dependency pair method to a first-order encoding of simply typed term rewriting systems.
45398397
Logicality of Conditional Rewrite Systems
A conditional term rewriting system is called logical if it has the same logical strength as the underlying conditional equational system. In this paper we summarize known logicality results and we present new sufficient conditions for logicality of the important class of oriented conditional term rewriting systems.
119674
Logicality of conditional rewrite systems
A conditional term rewriting system is called logical if it has the same logical strength as the underlying conditional equational system. In this paper we summarize known logicality results and we present new sufficient conditions for logicality of the important class of oriented conditional term rewriting systems.
40686834
Confluence and Termination of Simply Typed Term Rewriting Systems
We propose simply typed term rewriting systems (STTRSs), which extend first-order rewriting by allowing higher-order functions. We study a simple proof method for confluence which employs a characterization of the diamond property of a parallel reduction. By an application of the proof method, we obtain a new confluence result for orthogonal conditional STTRSs. We also discuss a semantic method for proving termination of STTRSs based on monotone interpretation.
36220595
The reachability and related decision problems for monadic and semi-constructor TRSs
This paper shows that reachability is undecidable for confluent monadic and semi-constructor TRSs, and that joinability and confluence are undecidable for monadic and semi-constructor TRSs. Here, a TRS is monadic if the height of the right-hand side of each rewrite rule is at most 1, and is semi-constructor if all defined symbols appearing in the right-hand side of each rewrite rule occur only in its ground subterms.
20213893
Inductive Theorems for Higher-Order Rewriting
Based on the simply typed term rewriting framework, inductive reasoning in higher-order rewriting is studied. The notion of higher-order inductive theorems is introduced to reflect higher-order feature of simply typed term rewriting. Then the inductionless induction methods in first-order term rewriting are incorporated to verify higher-order inductive theorems. In order to ensure that higher-order inductive theorems are closed under contexts, the notion of higher-order sufficient completeness is introduced. Finally, the decidability of higher-order sufficient completeness is discussed.
39965792
Optimal Population Size under Constant Computation Cost
Optimal setting of genetic algorithm parameters has been the subject of numerous studies; however, the optimality of a population size is still a controversial subject. This work addresses the issue of optimal population size under the constraint of a constant computation cost. Given a problem P to be solved, a GA (genetic algorithm) as a problem solver, and a computation cost C to spend, how should we schedule the problem solving? Under the constant C, there is a trade-off between a population size s. and the number r of GA runs. Focusing on this trade-off, the present paper claims there exists the optimal sopt for the given P and GA under the constant C; here, the optimality means maximum of the expected probability of obtaining acceptable solutions. To explain how the optimality comes about we propose the statistical model of GA runs, prove the existence of sopt and get more insight in a specific case. Then experiments were performed using a difficult job shop scheduling problem. The experiments showed the plausibility of the proposed model.
37171770
A Genetic Algorithm Applicable to Large-Scale Job-Shop Problems
5075607
Scheduling by Genetic Local Search with Multi-Step Crossover
In this paper, multi-step crossover (MSX) and a local search method are unied as a single operator called MSXF. MSX and MSXF utilize a neighborhood structure and a distance measure in the search space. In MSXF, a solution, initially set to be one of the parents, is stochastically replaced by a relatively good solution in the neighbor- hood, where the replacement is biased toward the other parent. After a certain number of iterations of this process, the best solution from those generated is selected as an ospring. Using job-shop scheduling problem benchmarks, MSXF was evaluated in a GA framework as a high-level crossover working on the critical path of a schedule. Experiments showed promising performance for the proposed method.
8720243
Clustering under the line graph transformation: application to reaction network
BackgroundMany real networks can be understood as two complementary networks with two kind of nodes. This is the case of metabolic networks where the first network has chemical compounds as nodes and the second one has nodes as reactions. In general, the second network may be related to the first one by a technique called line graph transformation (i.e., edges in an initial network are transformed into nodes). Recently, the main topological properties of the metabolic networks have been properly described by means of a hierarchical model. While the chemical compound network has been classified as hierarchical network, a detailed study of the chemical reaction network had not been carried out.ResultsWe have applied the line graph transformation to a hierarchical network and the degree-dependent clustering coefficient C(k) is calculated for the transformed network. C(k) indicates the probability that two nearest neighbours of a vertex of degree k are connected to each other. While C(k) follows the scaling law C(k) ~ k-1.1 for the initial hierarchical network, C(k) scales weakly as k0.08 for the transformed network. This theoretical prediction was compared with the experimental data of chemical reactions from the KEGG database finding a good agreement.ConclusionsThe weak scaling found for the transformed network indicates that the reaction network can be identified as a degree-independent clustering network. By using this result, the hierarchical classification of the reaction network is discussed.
37236112
Conventional Genetic Algorithm for Job Shop Problems