Since the seminal work of J. A. Robinson on resolution, many lifting lemmas for simplifying proofs of completeness of resolution have been proposed in the literature. In the logic programming framework, they may also help to detect some infinite derivations while proving goals under the SLD-resolution. In this paper, we first generalize a version of the lifting lemma, by extending the relation "is more general than" so that it takes into account only some arguments of the atoms. The other arguments, which we call neutral arguments, are disregarded. Then we propose two syntactic conditions of increasing power for identifying neutral arguments from mere inspection of the text of a logic program.
VAF-check (for Variant Atoms loop check for logic programs with Functions) was proposed by Shen @cite_14 . It is based on the notion of . VAF-check says that an SLD-derivation may be infinite if it generates an atomic subgoal @math that is an expanded variant of some of its ancestor @math , @math is a variant of @math except for some arguments @math such that: @math grows from @math to @math into a function containing @math , , @math grows from @math to @math into a function containing @math . VAF-check is as reliable as and more efficient than EVA-check @cite_14 .
@cite_14
1981314990 1975546131 2069456883 2276638936
Two complete loop checking mechanisms have been presented in the literature for logic programs with functions: OS-check and EVA-check. OS-check is computationally efficient but quite unreliable in that it often misidentifies infinite loops, whereas EVA-check is reliable for a majority of cases but quite expensive. In this paper, we develop a series of new complete loop checking mechanisms, called VAF-checks. The key technique we introduce is the notion of expanded variants, which captures a key structural characteristic of in finite loops. We show that our approach is superior to both OS-check and EVA-check in that it is as efficient as OS-check and as reliable as EVA-check. Copyright 2001 Elsevier Science B.V. The Equality check and the Subsumption check are weakly sound, but are not complete even for function-free logic programs. Although the OverSize (OS) check is complete for positive logic programs, it is too general in the sense that it prunes SLD-derivations merely based on the depth-bound of repeated predicate symbols and the size of atoms, regardless of the inner structure of the atoms, so it may make wrong conclusions even for some simple programs. In this paper, we explore complete loop checking mechanisms for positive logic programs. We develop an extended Variant of Atoms (VA) check that has the following features: (1) it generalizes the concept of “variant” from “the same up to variable renaming” to “the same up to variable renaming except possibly with some arguments whose size recursively increases”, (2) it makes use of the depth-bound of repeated variants of atoms instead of depth-bound of repeated predicate symbols, (3) it combines the Equality Subsumption check with the VA check, (4) it is complete w. r. t. the leftmost selection rule for positive logic programs, and (5) it is more sound than both the OS check and all the existing versions of the VA check. This paper presents an easy to design Physically Unclonable Function (PUF). The proposed PUF implementation is a loop composed of @math identical and controllable delay chains which are serially assembled in a loop to create a single ring oscillator. The frequency discrepancies resulting from the oscillator driven by complementary combinations of the delay chains allows to characterize one device. The presented PUF, nicknamed the Loop PUF (LPUF), returns a frequency comparison of loops made of @math delay chains ( @math ). The comparisons are done sequentially on the same structure. Unlike others PUFs based on delays, there is no specific routing constraints. Hence the LPUF is particularly flexible and easy to design. The basic use of the Loop PUF is to generate intrinsic device keys for cryptographic algorithms. It can also be used to generate challenge response pairs for simple authentication. Experiments have been carried out on CYCLONE II FPGAs to assess the performance of the LPUF, such as randomness, uniqueness and steadiness. They clearly show both the easiness of design and the quality level of the LPUF. The measurement time steadiness, as well as resistance against side-channel and modeling attacks are discussed. Logic programming (LP) is a programming language based on first-order Horn clause logic that uses SLD-resolution as a semi-decision procedure. Finite SLD-computations are inductively sound and complete with respect to least Herbrand models of logic programs. Dually, the corecursive approach to SLD-resolution views infinite SLD-computations as successively approximating infinite terms contained in programs' greatest complete Herbrand models. State-of-the-art algorithms implementing corecursion in LP are based on loop detection. However, such algorithms support inference of logical entailment only for rational terms, and they do not account for the important property of productivity in infinite SLD-computations. Loop detection thus lags behind coinductive methods in interactive theorem proving (ITP) and term-rewriting systems (TRS). Structural resolution is a newly proposed alternative to SLD-resolution that makes it possible to define and semi-decide a notion of productivity appropriate to LP. In this paper, we prove soundness of structural resolution relative to Herbrand model semantics for productive inductive, coinductive, and mixed inductive-coinductive logic programs. We introduce two algorithms that support coinductive proof search for infinite productive terms. One algorithm combines the method of loop detection with productive structural resolution, thus guaranteeing productivity of coinductive proofs for infinite rational terms. The other allows to make lazy sound observations of fragments of infinite irrational productive terms. This puts coinductive methods in LP on par with productivity-based observational approaches to coinduction in ITP and TRS.