Structures using constructors are of ordinary use in functional programming to represent data structures of unbound size. Lack of associativity of constructors, however, hinders program analyses or efficient execution...Structures using constructors are of ordinary use in functional programming to represent data structures of unbound size. Lack of associativity of constructors, however, hinders program analyses or efficient executions. This paper describes ideas of abstraction toward constructors, and similarly abstraction from constructing functions, which we call functional constructors. We demonstrate our ideas making program analyses easier and enable transformation to efficient execution.展开更多
This paper investigates the semantics of conditional term rewriting systemswith negation (denoted by EI-CTRS), called constructor-based EI-model se-mantics. The introduction of '≠' in EI-CTRS make EI-CTRS mor...This paper investigates the semantics of conditional term rewriting systemswith negation (denoted by EI-CTRS), called constructor-based EI-model se-mantics. The introduction of '≠' in EI-CTRS make EI-CTRS more difficult tostudy. This is in part because of a failure of EI-CTRS to guarantee that thereexist least Herbrand models in classical logical point of views. The key idea ofEI-model is to explain that 't ≠ s' means that the two concepts representedby t and s respectively actually belong to distinguished basic concepts repre-sented by two constructor-ground terms. We define the concept of EI-model,and show that there exist least Herbrand ELmodels for EI-satisfiable EI-CTRS.From algebraic and logic point of view, we show that there are very strong rea-sons for regarding the least Herbrand EI-models as the intended semantics ofEI-CTRS. According to fixpoint theory, we develop a method to construct leastHerbrand EI-models in a bottom-up manner. Moreover, we discuss soundnessand completeness of EI-rewrite for EI-model semantics.展开更多
Further research about nonterminating rewritings is introduced. First, the previousdefinition of head boundedness is modified to exclude nonfair reduction sequences.A sufficient condition is then given to determine he...Further research about nonterminating rewritings is introduced. First, the previousdefinition of head boundedness is modified to exclude nonfair reduction sequences.A sufficient condition is then given to determine head boundedness of term rewritingsystems. The condition is then developed to a method to determine head boundednessof constructor systems.展开更多
基金Supported by Research Fellowships of Japan Society for the Promotion of Science for Young Scientists(11-0 6 2 82 )
文摘Structures using constructors are of ordinary use in functional programming to represent data structures of unbound size. Lack of associativity of constructors, however, hinders program analyses or efficient executions. This paper describes ideas of abstraction toward constructors, and similarly abstraction from constructing functions, which we call functional constructors. We demonstrate our ideas making program analyses easier and enable transformation to efficient execution.
文摘This paper investigates the semantics of conditional term rewriting systemswith negation (denoted by EI-CTRS), called constructor-based EI-model se-mantics. The introduction of '≠' in EI-CTRS make EI-CTRS more difficult tostudy. This is in part because of a failure of EI-CTRS to guarantee that thereexist least Herbrand models in classical logical point of views. The key idea ofEI-model is to explain that 't ≠ s' means that the two concepts representedby t and s respectively actually belong to distinguished basic concepts repre-sented by two constructor-ground terms. We define the concept of EI-model,and show that there exist least Herbrand ELmodels for EI-satisfiable EI-CTRS.From algebraic and logic point of view, we show that there are very strong rea-sons for regarding the least Herbrand EI-models as the intended semantics ofEI-CTRS. According to fixpoint theory, we develop a method to construct leastHerbrand EI-models in a bottom-up manner. Moreover, we discuss soundnessand completeness of EI-rewrite for EI-model semantics.
文摘Further research about nonterminating rewritings is introduced. First, the previousdefinition of head boundedness is modified to exclude nonfair reduction sequences.A sufficient condition is then given to determine head boundedness of term rewritingsystems. The condition is then developed to a method to determine head boundednessof constructor systems.
