Now showing items 31-50 of 100

• #### Finitely Presented Algebras and the Polynomial Time Hiercharchy ﻿

(Cornell University, 1977-03)
Let $S_{n}(V_{n})=\{less than \Gamma, Q_{1}v_{1}\cdots Q_{k}v_{k} s \equiv j greater than | \Gamma$ is a finite presentation of $\cal A, Q_{1} \cdots Q_{k}$ is a string of quantifiers with $n$ alterations, the outermost ...
• #### First Order Predicate Logic Without Negation is NP-Complete ﻿

(Cornell University, 1977-04)
Techniques developed in the study of the complexity of finitely presented algebras are used to show that the problem of deciding validity of positive sentences in the language of first order predicate logic with equality ...
• #### Functional Decomposition of Polynomials ﻿

(Cornell University, 1987-07)
ABSTRACT NOT AVAILABLE
• #### Halting and Equivalence of Program Schemes in Models of Arbitrary Theories ﻿

(2010-05-19)
In this note we consider the following decision problems. Let S be a fixed first-order signature. (i) Given a first-order theory or ground theory T over S of Turing degree A, a program scheme p over S, and input values ...
• #### Halting and Equivalence of Schemes over Recursive Theories ﻿

(Cornell University, 2002-10-28)
Let S be a fixed first-order signature. In this note we consider the following decision problems. (i) Given a recursive ground theory T over S, a program scheme p over S, and input values specified by ground terms ...
• #### Indefinite Summation and the Kronecker Delta ﻿

(2007-10-18)
Indefinite summation, together with a generalized version of the Kronecker delta, provide a calculus for reasoning about various polynomial functions that arise in combinatorics, such as the Tutte, chromatic, flow, and ...
• #### Infinitary Axiomatization of the Equational Theory of Context-Free Languages ﻿

(2013-07-01)
We give a natural complete infinitary axiomatization of the equational theory of the context-free languages, answering a question of Leiss (1992).
• #### Intuitionistic Linear Logic and Partial Correctness ﻿

(Cornell University, 2001-01-02)
We formulate a Gentzen-style sequent calculus for partial correctness that subsumes propositional Hoare Logic. The system is a noncommutative Intuitionistic Linear Logic. We prove soundness and completeness over relational ...
• #### KAT + B! ﻿

(2014-01-08)
It is known that certain program transformations require a small amount of mutable state, a feature not explicitly provided by Kleene algebra with tests (KAT). In this paper we show how to axiomatically extend KAT with ...
• #### KAT-ML: An Interactive Theorem Prover for Kleene Algebra with Tests ﻿

(Cornell University, 2003-08-21)
KAT-ML is an interactive theorem prover for Kleene algebra with tests (KAT). The system is designed to reflect the natural style of reasoning with KAT that one finds in the literature. We describe the main features of ...
• #### Kleene Algebra and Bytecode Verification ﻿

(Cornell University, 2004-12-20)
Most standard approaches to the static analysis of programs, such as the popular worklist method, are first-order methods that inductively annotate program points with abstract values. In a recent paper we introduced a ...
• #### Kleene Algebra with Equations ﻿

(2014-02-27)
We identify sufficient conditions for the construction of free language models for systems of Kleene algebra with additional equations. The construction applies to a broad class of extensions of KA and provides a uniform ...
• #### Kleene algebra with tests and commutativity conditions ﻿

(Cornell University, 1996-01)
We give an equational proof, using Kleene algebra with tests and commutativity conditions, of the following classical result: every while program can be simulated by a while program with at most one while loop. The proof ...
• #### Kleene Algebra with Tests and Program Schematology ﻿

(Cornell University, 2001-07-10)
The theory of flowchart schemes has a rich history going back to Ianov (1960); see Manna (1974) for an elementary exposition. A central question in the theory of program schemes is scheme equivalence. Manna presents ...
• #### Kleene Algebra with Tests and the Static Analysis of Programs ﻿

(Cornell University, 2003-11-17)
We propose a general framework for the static analysis of programs based on Kleene algebra with tests (KAT). We show how KAT can be used to statically verify compliance with safety policies specified by security automata. ...
• #### Kleene Algebra with Tests: Completeness and Decidability ﻿

(Cornell University, 1996-04)
Kleene algebras with tests provide a rigorous framework for equational specification and verification. They have been used successfully in basic safety analysis, source-to-source program transformation, and concurrency ...
• #### Kolmogorov Extension, Martingale Convergence, and Compositionality of Processes ﻿

(2015-12-30)
We show that the Kolmogorov extension theorem and the Doob martingale convergence theorem are two aspects of a common generalization, namely a colimit-like construction in a category of Radon spaces and reversible Markov ...
• #### Language-Based Security ﻿

(Cornell University, 1999-06)
Security of mobile code is a major issue in today's global computing environment. When you download a program from an untrusted source, how can you be sure it will not do something undesirable? In this paper I will discuss ...
• #### Left-Handed Completeness ﻿

(2011-08-23)
We give a new, significantly shorter proof of the completeness of the left-handed star rule of Kleene algebra. The proof reveals the rich interaction of algebra and coalgebra in the theory.
• #### Lexicographic Flow ﻿

(2009-06-25)
The lexicographic flow problem is a flow problem in which the edges are assigned priorities, and we wish to find a flow that is lexicographically maximum with respect to the priority assignment. The problem is reducible ...