Datalog is a well-known database query language based on the logicprogramming paradigm. A general datalog program consists of a number of rules and facts. Programs containing a unique rule and possibly some facts are...
详细信息
ISBN:
(纸本)3540664920
Datalog is a well-known database query language based on the logicprogramming paradigm. A general datalog program consists of a number of rules and facts. Programs containing a unique rule and possibly some facts are called single rule programs (sirups). We study boththe combined and the program complexity of sirups, ie., the complexity of evaluating sirups over variable and fixed databases, respectively. Moreover, we study the descriptive complexity of sirups, i.e., their expressive power. In ail cases it turns out that even very restricted classes of sirups have the same complexity and essentially the same expressive power as general datalog programs. We show that the evaluation of single clause programs is EXPTIME complete (combined complexity), and, if restricted to linear recursive rules, PSPACE complete. Moreover, sirups with one recursive rule and one additional fact capture PTIME on ordered structures, if a certain data representation is assumed and certain predefined relations are provided. Our results are obtained by a uniform product construction which maps a datalog program into a single rule by essentially maintaining its semantics. We also prove that the datalog clause implication problem, i.e., deciding whether a datalog clause implies another one, is EXPTIME complete.
the programmable logic controllers (PLC) programming is designed to the possibilities of a medium user of this equipment. In ALS 4.0 programming language a hierarchy of classes is set in three big trees which include ...
详细信息
the programmable logic controllers (PLC) programming is designed to the possibilities of a medium user of this equipment. In ALS 4.0 programming language a hierarchy of classes is set in three big trees which include the areas of application of this equipment. Its data and functions are encapsulated withthree degrees of visibility. the dynamic pass of types in execution time is allowed. Persistence is guaranteed outside the creation place and separated from ancestors using the macronets library. the whole normalized syntax of the structured languages of the IEC-61131-3 is almost kept.
the logicprogramming language λProlog is based on the intuitionistic theory of higher-order hereditary Harrop formulas, a logicthat significantly extends the theory of Horn clauses. A systematic ex73;ploitation ...
详细信息
We study the problem of deciding satisfiability of first order logic queries over views, our aim being to delimit the boundary between the decidable and the undecidable fragments of this language. Views currently occu...
详细信息
ISBN:
(纸本)3540654526
We study the problem of deciding satisfiability of first order logic queries over views, our aim being to delimit the boundary between the decidable and the undecidable fragments of this language. Views currently occupy a central place in database research, due to their role in applications such as information integration and data warehousing. Our principal result is the identification of an important decidable class of queries over unary conjunctive views. this extends the decidability of the classical class of first order sentences over unary relations (the Lowenheim class). We then demonstrate how extending this class leads to undecidability. In addition to new areas, our work also has relevance to extensions of results for related problems such as query containment, trigger termination, implication of dependencies and reasoning in description logics.
CHAT offers an Eilternative to SLG-WAM for implementing the suspension eind resumption of consumers that tabling needs;unlike SLG-WAM, it does not use freeze registers nor a complicated trail to preserve their executi...
详细信息
ISBN:
(纸本)3540664920
CHAT offers an Eilternative to SLG-WAM for implementing the suspension eind resumption of consumers that tabling needs;unlike SLG-WAM, it does not use freeze registers nor a complicated trail to preserve their execution environments. CHAT Eilso limits the amount of copying of CAT, which was previously put forwMd as another alternative to SLG-WAM. Although experimented results show that in preictice CHAT is competitive with - if not better than - SLG-WAM, there remains the annoying fact that on contrived programs the original CHAT can be made axbitraxily worse than SLG-WAM, i.e. the origincd CHAT has an intrinsically higher complexity. In this paper we show how to overcome this problem, in particular, we deal withthe two sources of higher complexity of CHAT: the repeated traversal of the choice point stack, Eind the lack of sufficient sharing of the trail. this is eichieved without fundamentally changing the underlying principle of CHAT by a technique that manipulates a Prolog choice point so that it assumes temporarily a different functionality smd in a way that is treinsparent to the underlying WAM. there is more potential use of this technique besides lowering the worst case complexity of CHAT: it leads to considering scheduling strategies that were not feasible before either in CHAT or in SLG-WAM. We aJso discuss extensively issues related to the implementation of the trail in a tabled logicprogramming system.
We define a class of modal logics LF by uniformly extend73;ing a class of modal logics L. Each logic L is characterised by a class of first-order definable frames, but the corresponding logic LF is some73;times ...
详细信息
We reduce the provability problem of any formula of the Lambek calculus to some context-free parsing problem. this reduction, which is based on non-commutative proof-net theory, allows us to de73;rive an automatic ...
详细信息
the subject of groundness analysis for (constraint) logic programs has been widely studied, and interesting domains have been proposed. Pos has been recognized as the most suitable domain for capturing the kind of dep...
详细信息
ISBN:
(纸本)3540654623
the subject of groundness analysis for (constraint) logic programs has been widely studied, and interesting domains have been proposed. Pos has been recognized as the most suitable domain for capturing the kind of dependencies arising in groundness analysis, and Reduced Ordered Binary Decision Diagrams (ROBDDs) are generally accepted to be the most efficient representation for Pos. Unfortunately, the size of an ROBDDs is, in the worst case, exponential in the number of variables it depends upon. Earlier work [2] has shown that a hybrid representation that separates the definite information from the dependency information is considerably more efficient than keeping the two together. the aim of the present paper is to push this idea further, also separating out certain dependency information, in particular all pairs of variables that are always either both ground or neither ground. We find that this new hybrid representation is a significant improvement over previous work.
Production plants have been complicated by the diversification of products. In order to control complicated production plants, the distributed process control is one of powerful approach. In the development of a distr...
详细信息
Production plants have been complicated by the diversification of products. In order to control complicated production plants, the distributed process control is one of powerful approach. In the development of a distributed process control system, it is difficult to develop its software because distributed controllers complicatedly interact with each other. For that reason, the function block model, that is the specification language for distributed process control logic, is being standardized in IEC61499-1. In this paper, a distributed process control programming tool for function block description is proposed. It is possible to describe control programs hierarchically by using function blocks. the GUI of this tool supplies multi-windows which can simultaneously display function blocks on different hierarchical levels. In this tool, inputted programs can also be verified by a simulation. this tool is applied to the control program description of an automatic carrier system. It has been confirmed that the control program is completely described and simulated by using this tool.
A systematic procedure is presented for generating Boolean logic equations that represent the desired control action to be carried out by a discrete logic controller. A key component of the controller design is the sp...
详细信息
A systematic procedure is presented for generating Boolean logic equations that represent the desired control action to be carried out by a discrete logic controller. A key component of the controller design is the specification of set and reset operations that define the next value of each state variable in the Boolean logic equations for the controller. the logic equations can be implemented on a PLC or PC in order to realize the desired control action. Two examples are given to illustrate the procedure.
暂无评论