Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 6 of 6
Full-Text Articles in Physical Sciences and Mathematics
Semantics Vs. Syntax Vs. Computations Machine Models For Type-2 Polynomial-Time Bounded Functionals (Preliminary Draft), James S. Royer
Semantics Vs. Syntax Vs. Computations Machine Models For Type-2 Polynomial-Time Bounded Functionals (Preliminary Draft), James S. Royer
Electrical Engineering and Computer Science - Technical Reports
This paper investigates analogs of the Kreisel-Lacombe-Shoenfield Theorem in the context of the type-2 basic feasible functionals, a.k.a. the Mehlhorn-Cook class of type-2 polynomial-time functionals. We develop a direct, polynomial-time analog of effective operation, where the time bound on computations is modeled after Kapron and Cook's scheme for their basic polynomial-time functionals. We show that (i) if P = NP, these polynomial-time effective operations are strictly more powerful on R (the class of recursive functions) than the basic feasible functions, and (ii) there is an oracle relative to which these polynomial-time effective operations and the basic feasible functionals have the …
Parametricity And Local Variables, Peter W. O'Hearn, R. D. Tennent
Parametricity And Local Variables, Peter W. O'Hearn, R. D. Tennent
Electrical Engineering and Computer Science - Technical Reports
We propose that the phenomenon of local state may be understood in terms of Strachey's concept of parametric (i.e., uniform) polymorphism. The intuitive basis for our proposal is the following analogy: a non-local procedure is independent of locally-declared variables in the same way that a parametrically polymorphic function is independent of types to which it is instantiated. A connection between parametricity and representational abstraction was first suggested by J. C. Reynolds. Reynolds used logical relations to formalize this connection in languages with type variables and user-defined types. We use relational parametricity to construct a model for an Algol-like language in …
A Declarative Foundation Of Λprolog With Equality, Mino Bai
A Declarative Foundation Of Λprolog With Equality, Mino Bai
Electrical Engineering and Computer Science - Technical Reports
We build general model-theoretic semantics for higher-order logic programming languages. Usual semantics for first-order logic is two-level: i.e., at a lower level we define a domain of individuals, and then, we define satisfaction of formulas with respect to this domain. In a higher-order logic which includes the propositional type in its primitive set of types, the definition of satisfaction of formulas is mutually recursive with the process of evaluation of terms. As result of this in higher-order logic it is extremely difficult to define an effective semantics. For example to define T p operator for logic program P, we need …
Fitting Semantics For Conditional Term Rewriting, Chilukuri K. Mohan
Fitting Semantics For Conditional Term Rewriting, Chilukuri K. Mohan
Electrical Engineering and Computer Science - Technical Reports
This paper investigates the semantics of conditional term rewriting systems with negation which do not satisfy useful properties like termination. It is shown that the approach used by Fitting [5] for Prolog-style logic programs is applicable in this context. A monotone operator is developed, whose fixpoints describe the semantics of conditional rewriting. Several examples illustrate this semantics for non-terminating rewrite systems which could not be easily handled by previous approaches.
A Lexical Extension Of Montague Semantics, William C. Purdy
A Lexical Extension Of Montague Semantics, William C. Purdy
Electrical Engineering and Computer Science - Technical Reports
This paper presents a model theory of lexical semantics that is compatible with theories in the Montagovian tradition. Lexical expressions are modeled as subsets or “subspaces” in a “semantic spaces”. A unique representation is defined for subspaces of the semantic space. This unique representation is called the "normal form" of the lexical denotation. A Boolean algebra of normal forms is developed, in which lexical entailment is Boolean inclusion. The presentation in the body of the paper is informal, making use of examples to illustrate the theory and to indicate the range of applicability. Formal definitions and proofs in support of …
A Lexical Extension Of Montague Semantics, William C. Purdy
A Lexical Extension Of Montague Semantics, William C. Purdy
Electrical Engineering and Computer Science - Technical Reports
Montague's linguistic theory provides a completely formalized account of language in general and natural language in particular. It would appear to be especially applicable to the problem of natural language understanding by computer systems. However the theory does not deal with meaning at the lexical level. As a result, deduction in a system based on Montague semantics is severely restricted. This paper considers lexical extension of Montague semantics as a way to remove this restriction. Representation of lexical semantics by a logic program or semantic net is complex. An alternative representation, called a semantic space, is described. This alternative lacks …