JavaScript is disabled for your browser. Some features of this site may not work without it.
Browsing by Author "Kozen, Dexter"
Now showing items 6786 of 100

On Parallelism in Turing Machines
Kozen, Dexter (Cornell University, 197606)A model of parallel computation based on a generalization of nondeterminism in Turing machines is introduced. Complexity classes //T(n)TIME, //L(n)SPACE, //LOGSPACE, //PTIME, etc. are defined for these machines in a ... 
On RegularityPreserving Functions
Kozen, Dexter (Cornell University, 199511)We give a characterization of regularitypreserving functions. 
On Teaching LeftHanded Children to Write
Kozen, Dexter (Cornell University, 198706)It is argued that the handwriting method commonly taught to lefthanded children is incorrect and harmful. The disadvantages of this method are noted, and a new method alleviating these disadvantages is proposed. 
On the Coalgebraic Theory of Kleene Algebra with Tests
Kozen, Dexter (20080314)We develop a coalgebraic theory of Kleene algebra with tests (KAT) along the lines of Rutten (1998) for Kleene algebra (KA) and Chen and Pucella (2003) for a limited version of KAT, resolving two open problems of Chen and ... 
On the Completeness of Propositional Hoare Logic
Kozen, Dexter; Tiuryn, Jerzy (Cornell University, 199909)We investigate the completeness of Hoare Logic on the propositional level. In particular, the expressiveness requirements of Cook's proof are characterized propositionally. We give a completeness result for Propositional ... 
On the Complexity of Reasoning in Kleene Algebra
Kozen, Dexter (Cornell University, 199703)We study the complexity of reasoning in Kleene algebra and *continuous Kleene algebra in the presence of extra equational assumptions $E$; that is, the complexity of deciding the validity of universal Horn formulas $E\imp ... 
On the Complexity of the Horn Theory of REL
Hardin, Chris; Kozen, Dexter (Cornell University, 20030508)We show that the universal Horn theory of relational Kleene algebras is Pi11complete. 
On the Elimination of Hypotheses in Kleene Algebra with Tests
Hardin, Chris; Kozen, Dexter (Cornell University, 20021021)The validity problem for certain universal Horn formulas of Kleene algebra with tests (KAT) can be efficiently reduced to the equational theory. This reduction is known as elimination of hypotheses. Hypotheses are used ... 
On the Representation of Kleene Algebras with Tests
Kozen, Dexter (Cornell University, 20031006)We investigate conditions under which a given Kleene algebra with tests is isomorphic to an algebra of binary relations. Two simple separation properties are identified that, along with starcontinuity, are sufficient ... 
On Two Letters versus Three
Kozen, Dexter (Cornell University, 20020204)If A is a contextfree language over a twoletter alphabet, then the set of all words obtained by sorting words in A and the set of all permutations of words in A are contextfree. This is false over alphabets of three ... 
Optimal Coin Flipping
Kozen, Dexter (20090602)This paper studies the problem of simulating a coin of arbitrary real bias q with a coin of arbitrary real bias p with minimum loss of entropy. We establish a lower bound that is strictly greater than the informationtheoretic ... 
Parallel Resultant Computation
Ierardi, Doug J.; Kozen, Dexter (Cornell University, 199001)A resultant is a purely algebraic criterion for determining when a finite collection of polynomials have a common zero. It has been shown to be a useful tool in the design of efficient parallel and sequential algorithms ... 
Parikh's Theorem in Commutative Kleene Algebra
Hopkins, Mark; Kozen, Dexter (Cornell University, 199901)Parikh's Theorem says that the commutative image of every context free language is the commutative image of some regular set. Pilling has shown that this theorem is essentially a statement about least solutions of ... 
Polynomial Decomposition Algorithms
Kozen, Dexter; Landau, Susan (Cornell University, 198608)In a recent paper [BZ], Barton and Zippel examine the question of when a polynomial $f(x)$ over a field of characteristic 0 has a nontrivial decomposition $f(x)=g(h(x))$. They give two exponentialtime algorithms, both ... 
Practical Coinduction
Kozen, Dexter; Silva, Alexandra (20121111)Induction is a wellestablished proof principle that is taught in most undergraduate programs in mathematics and computer science. In computer science, it is used primarily to reason about inductivelydefined datatypes ... 
Probabilistic NetKAT
Foster, Nate; Kozen, Dexter; Mamouras, Konstantinos; Reitblatt, Mark; Silva, Alexandra (201507)This paper develops a new language for programming softwaredefined networks based on a probabilistic semantics. We extend the NetKAT language with new primitives for expressing probabilistic behaviors and enrich the ... 
Publication/Citation: A ProofTheoretic Approach to Mathematical Knowledge Management
Kozen, Dexter; Ramanarayanan, Ganesh (Cornell University, 20050316)There are many reallife examples of formal systems that support constructions or proofs, but that do not provide direct support for remembering them so that they can be recalled and reused in the future. In this paper ... 
Rabin Measures and Their Applications to Fairness and Automata Theory
Klarlund, Nils; Kozen, Dexter (Cornell University, 199104)Rabin conditions are general class of properties of infinite sequences that emcompass most known automatatheoretic acceptance conditions and notions of fairness. In this paper we show how to determine whether a program ... 
Rational Spaces and Set Constraints
Kozen, Dexter (Cornell University, 199501)Set constraints are inclusions between expressions denoting sets of ground terms. They have been used extensively in program analysis and type inference. In this paper we investigate the topological structure of the spaces ... 
Realization of Coinductive Types
Kozen, Dexter (20110301)We give an explicit combinatorial construction of final coalgebras for a modest generalization of polynomial functors on Set. Type signatures are modeled as directed multigraphs instead of endofunctors. The final coalgebra ...