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

KAT + B!
Grathwohl, Niels Bjørn Bugge; Kozen, Dexter; Mamouras, Konstantinos (20140108)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 ... 
KATML: An Interactive Theorem Prover for Kleene Algebra with Tests
AboulHosn, Kamal; Kozen, Dexter (Cornell University, 20030821)KATML 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
Kot, Lucja; Kozen, Dexter (Cornell University, 20041220)Most standard approaches to the static analysis of programs, such as the popular worklist method, are firstorder methods that inductively annotate program points with abstract values. In a recent paper we introduced a ... 
Kleene Algebra with Equations
Kozen, Dexter; Mamouras, Konstantinos (20140227)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
Kozen, Dexter (Cornell University, 199601)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
Angus, Allegra; Kozen, Dexter (Cornell University, 20010710)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
Kozen, Dexter (Cornell University, 20031117)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
Kozen, Dexter; Smith, Frederick (Cornell University, 199604)Kleene algebras with tests provide a rigorous framework for equational specification and verification. They have been used successfully in basic safety analysis, sourcetosource program transformation, and concurrency ... 
Kolmogorov Extension, Martingale Convergence, and Compositionality of Processes
Kozen, Dexter (20151230)We show that the Kolmogorov extension theorem and the Doob martingale convergence theorem are two aspects of a common generalization, namely a colimitlike construction in a category of Radon spaces and reversible Markov ... 
LanguageBased Security
Kozen, Dexter (Cornell University, 199906)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 ... 
LeftHanded Completeness
Kozen, Dexter; Silva, Alexandra (20110823)We give a new, significantly shorter proof of the completeness of the lefthanded star rule of Kleene algebra. The proof reveals the rich interaction of algebra and coalgebra in the theory. 
Lexicographic Flow
Kozen, Dexter (20090625)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 ... 
Logical Aspects of Set Constraints
Kozen, Dexter (Cornell University, 199405)Set constraints are inclusion relations between sets of ground terms over a ranked alphabet. They have been used extensively in program analysis and type inference. Here we present an equational axiomatization of the ... 

Malicious Code Detection for Open Firmware
Adelstein, Frank; Stillerman, Matt; Kozen, Dexter (Cornell University, 20020927)Malicious boot firmware is a largely unrecognized but significant security risk to our global information infrastructure. Since boot firmware executes before the operating system is loaded, it can easily circumvent any ... 
A Metrized Duality Theorem for Markov Processes
Kozen, Dexter; Mardare, Radu; Panangaden, Prakash (20140521)We extend our previous duality theorem for Markov processes by equipping the processes with a pseudometric and the algebras with a notion of metric diameter. We are able to show that the isomorphisms of our previous duality ... 
MyhillNerode Relations on Automatic Systems and the Completeness ofKleene Algebra
Kozen, Dexter (Cornell University, 20001130)It is well known that finite square matrices over a Kleene algebra again form a Kleene algebra. This is also true for infinite matrices under suitable restrictions. One can use this fact to solve certain infinite systems ... 
Natural Transformations as Rewrite Rules and Monad Composition
Kozen, Dexter (Cornell University, 20040702)Eklund et al. (2002) present a graphical technique aimed at simplifying the verification of various categorytheoretic constructions, notably the composition of monads. In this note we take a different approach involving ... 
NC Algorithms for Comparability Graphs, Interval Graphs, and Unique Perfect Matchings
Kozen, Dexter; Vazirani, Umesh V.; Vazirani, Vijay V. (Cornell University, 198612)Laszlo Lovasz recently posed the following problem: "Is there an NC algorithm for testing if a given graph has a unique perfect matching?" We present such an algorithm for bipartite graphs. We also give NC algorithms ... 
NetKAT: Semantic Foundations for Networks
Anderson, Carolyn Jane; Foster, Nate; Guha, Arjun; Jeannin, JeanBaptiste; Kozen, Dexter; Schlesinger, Cole; Walker, David (20131011)Recent years have seen growing interest in highlevel languages for programming networks. But the design of these languages has been largely ad hoc, driven more by the needs of applications and the capabilities of network ...