11 citations · 36 across the 25 of their papers we have counts for
34 papers
A Unified Treatment of Substitution for Presheaves, Nominal Sets, Renaming Sets, and so on
Fabian Lenke, Stefan Milius, Henning Urbat
Presheaves and nominal sets provide alternative abstract models of sets of syntactic objects with free and bound variables, such as lambda-terms. One distinguishing feature of the…
Codensity Monads via Density and Duality
Fabian Lenke, Nico Wittrock, Stefan Milius +1
Codensity monads provide a universal method to generate complex monads from simple functors. Recently, a wide range of important monads in logic, denotational semantics, and probab…
Bialgebraic Reasoning on Stateful Languages
Sergey Goncharov, Stefan Milius, Lutz Schröder +2
Reasoning about program equivalence in imperative languages is notoriously challenging, as the presence of states (in the form of variable stores) fundamentally increases the obser…
Learning Automata with Name Allocation
Florian Frank, Stefan Milius, Jurriaan Rot +1
Automata over infinite alphabets have emerged as a convenient computational model for processing structures involving data, such as nonces in cryptographic protocols or data values…
Abstract Operational Methods for Call-by-Push-Value
Sergey Goncharov, Stelios Tsampas, Henning Urbat
Levy's call-by-push-value is a comprehensive programming paradigm that combines elements from functional and imperative programming, supports computational effects and subsumes bot…
Algebraic Language Theory with Effects
Fabian Lenke, Stefan Milius, Henning Urbat +1
Regular languages -- the languages accepted by deterministic finite automata -- are known to be precisely the languages recognized by finite monoids. This characterization is the o…
Alternating Nominal Automata with Name Allocation
Florian Frank, Daniel Hausmann, Stefan Milius +2
Formal languages over infinite alphabets serve as abstractions of structures and processes carrying data. Automata models over infinite alphabets, such as classical register automa…
Higher-order bialgebraic semantics
Sergey Goncharov, Stefan Milius, Lutz Schröder +2
Compositionality proofs in higher-order languages are notoriously involved, and general semantic frameworks guaranteeing compositionality are hard to come by. In particular, Turi a…
Bialgebraic Reasoning on Higher-Order Program Equivalence
Sergey Goncharov, Stefan Milius, Stelios Tsampas +1
Logical relations constitute a key method for reasoning about contextual equivalence of programs in higher-order languages. They are usually developed on a per-case basis, with a n…
Logical Predicates in Higher-Order Mathematical Operational Semantics
Sergey Goncharov, Alessio Santamaria, Lutz Schröder +2
We present a systematic approach to logical predicates based on universal coalgebra and higher-order abstract GSOS, thus making a first step towards a unifying theory of logical re…
Algebraic Reasoning over Relational Structures
Jan Jurka, Stefan Milius, Henning Urbat
Many important computational structures involve an intricate interplay between algebraic features (given by operations on the underlying set) and relational features (taking accoun…
Extended Stone Duality via Monoidal Adjunctions
Fabian Lenke, Henning Urbat, Stefan Milius
Extensions of Stone-type dualities have a long history in algebraic logic and have also been instrumental in proving results in algebraic language theory. We show how to extend abs…
Nominal Topology for Data Languages
Fabian Birkmann, Stefan Milius, Henning Urbat
We propose a novel topological perspective on data languages recognizable by orbit-finite nominal monoids. For this purpose, we introduce pro-orbit-finite nominal topological space…
Positive Data Languages
Florian Frank, Stefan Milius, Henning Urbat
Positive data languages are languages over an infinite alphabet closed under possibly non-injective renamings of data values. Informally, they model properties of data words expres…
Weak Similarity in Higher-Order Mathematical Operational Semantics
Henning Urbat, Stelios Tsampas, Sergey Goncharov +2
Higher-order abstract GSOS is a recent extension of Turi and Plotkin's framework of Mathematical Operational Semantics to higher-order languages. The fundamental well-behavedness p…
Towards a Higher-Order Mathematical Operational Semantics
Sergey Goncharov, Stefan Milius, Lutz Schröder +2
Compositionality proofs in higher-order languages are notoriously involved, and general semantic frameworks guaranteeing compositionality are hard to come by. In particular, Turi a…
Coalgebraic Semantics for Nominal Automata
Florian Frank, Stefan Milius, Henning Urbat
This paper provides a coalgebraic approach to the language semantics of two types of non-deterministic automata over nominal sets: non-deterministic orbit-finite automata (NOFAs) a…
Stateful Structural Operational Semantics
Sergey Goncharov, Stefan Milius, Lutz Schröder +2
Compositionality of denotational semantics is an important concern in programming semantics. Mathematical operational semantics in the sense of Turi and Plotkin guarantees composit…
Nominal Büchi Automata with Name Allocation
Henning Urbat, Daniel Hausmann, Stefan Milius +1
Infinite words over infinite alphabets serve as models of the temporal development of the allocation and (re-)use of resources over linear time. We approach omega-languages over in…
Nondeterministic Syntactic Complexity
Robert Myers, Stefan Milius, Henning Urbat
We introduce a new measure on regular languages: their nondeterministic syntactic complexity. It is the least degree of any extension of the `canonical boolean representation' of t…
Reiterman's Theorem on Finite Algebras for a Monad
Jiri Adamek, Liang-Ting Chen, Stefan Milius +1
Profinite equations are an indispensable tool for the algebraic classification of formal languages. Reiterman's theorem states that they precisely specify pseudovarieties, i.e.~cla…
On Language Varieties Without Boolean Operations
Fabian Birkmann, Stefan Milius, Henning Urbat
Eilenberg's variety theorem marked a milestone in the algebraic theory of regular languages by establishing a formal correspondence between properties of regular languages and prop…
On the Behaviour of Coalgebras with Side Effects and Algebras with Effectful Iteration
Stefan Milius, Jiří Adámek, Henning Urbat
For every finitary monad on sets and every endofunctor on the category of -algebras we introduce the concept of an ffg-Elgot algebra for , that is, an algebra admitti…
Automata Learning: An Algebraic Approach
Henning Urbat, Lutz Schröder
We propose a generic categorical framework for learning unknown formal languages of various types (e.g. finite or infinite words, weighted and nominal languages). Our approach is p…