1,721,145 research outputs found
Natural Transformations as Rewrite Rules and Monad Composition
No full textEklund et al. (2002) present a graphical technique aimed at simplifying the
verification of various category-theoretic constructions, notably the
composition of monads. In this note we take a different approach involving
string rewriting. We show that a given tuple is a monad if and
only if is a terminal object in a certain category of strings and rewrite
rules, and that this fact can be established by proving confluence of the
rewrite system. We illustrate the technique on the monad composition problem.
We also give a characterization of adjunctions in terms of rewrite categories
Travelling with Dexter Kozen
No full textAside from our shared interest in particular areas of Theoretical Computer Science, the experience I share with Dexter Kozen originates from the fact that we both belong to the not too large group of Theoreticiancs who during the late 1970-ies and early 1980-ies frequently crossed the Iron Curtain in order to interact with our colleagues from the Socialist part of Europe. This results into many appearances of Dexter in my collection of pictures from that period; a collection I like to share with the readers of this volume
On Free -Continuous and Regular Ordered Algebras
No full textWe study varieties of certain ordered -algebras with restricted
completeness and continuity properties. We give a general characterization of
their free algebras in terms of submonads of the monad of -coterms.
Varieties of this form are called \emph{quasi-regular}. For example, we show
that if is a set of inequalities between finite -terms, and if
and denote the varieties of all
-continuous ordered -algebras and regular ordered
-algebras satisfying , respectively, then the free
-algebra on generators is the
subalgebra of the corresponding free -algebra
determined by those elements of denoted by the regular
-coterms. This is a special case of a more general construction that
applies to any quasi-regular family. Examples include the *-continuous Kleene
algebras, context-free languages, -continuous semirings and
-continuous idempotent semirings, OI-macro languages, and iteration
theories
Kleene Algebra with Products and Iteration Theories
Full text linkWe develop a typed equational system that subsumes both iteration theories and typed Kleene algebra in a common framework. Our approach is based on cartesian categories endowed with commutative strong monads to handle nondeterminism
McNetKAT - Scalable Verification of Probabilistic Networks (PLDI'19)
No full text<p>This is the artifact associated with the following paper:</p>
<blockquote>
<p>Steffen Smolka, Praveen Kumar, David M Kahn, Nate Foster, Justin<br>
Hsu, Dexter Kozen, and Alexandra Silva. 2019. Scalable Verification<br>
of Probabilistic Networks. In PLDI ’19.<br>
<a href="https://doi.org/10.1145/3314221.3314639">https://doi.org/10.1145/3314221.3314639</a>.</p>
</blockquote>
<p>You can obtain the full paper here <a href="https://arxiv.org/abs/1904.08096">here</a>.</p>
<p>Please refer to artifact-page/index.html for instruction on how to install McNetKAT and reproduce the experiments from the paper.</p>
A Conversation with Dexter Kozen
No full textKozen discusses his experiences at Cornell – his research and teaching experience, textbooks, participation in sports & music, etc.Dexter Kozen got his PhD from CS at Cornell in 1977. After he spent time doing research at IBM, we drew him
back to the faculty in 1985.
Dexter has made lasting, fundamental contributions to diverse areas such as algorithms, complexity, logics, semantics
of programming languages, and computer security. The CS Department’s environment, which encourages
collaboration of people in different areas, both experimental and theoretical, has had a synergistic effect on both
his and others’ research.
One computer scientist said that: a winning combination of brilliance, depth, and elegance captures the essence
of Kozen’s work over the years. And it shows in the influence Dexter has had. He received the LICS Test-of-Time
Award for one of his papers, the EATCS Award from the European Association for Theoretical Computer Science,
the W. Wallace McDowell Award from the IEEE Computer Society, and two prizes from the Polish Ministry of
Education. He also has several teaching awards from Cornell. Further, he has written textbooks on the theory of
computation, automata theory, dynamic logic, and algorithms.
With interviewer Bob Constable, Dexter discusses his research and teaching experience, textbooks, participation
in sports and music, and more.
Running Time: 45 min. http://hdl.handle.net/1813/412061_jqw8x4r
The Ackermann Award 2018
Full text linkThe Ackermann Award is the EACSL Outstanding Dissertation Award for Logic in Computer Science. It is presented during the annual conference of the EACSL (CSL'xx). This contribution reports on the 2018 edition of the award
- …
