11 citations · 36 across the 25 of their papers we have counts for
16 papers · 1 filter
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…
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…
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…
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…
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…
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…
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…
Varieties of Data Languages
Henning Urbat, Stefan Milius
We establish an Eilenberg-type correspondence for data languages, i.e. languages over an infinite alphabet. More precisely, we prove that there is a bijective correspondence betwee…
Schützenberger Products in a Category
Liang-Ting Chen, Henning Urbat
The Schützenberger product of monoids is a key tool for the algebraic treatment of language concatenation. In this paper we generalize the Schützenberger product to the level of mo…
Eilenberg Theorems for Free
Henning Urbat, Jiří Adámek, Liang-Ting Chen +1
Eilenberg-type correspondences, relating varieties of languages (e.g. of finite words, infinite words, or trees) to pseudovarieties of finite algebras, form the backbone of algebra…
Profinite Monads, Profinite Equations, and Reiterman's Theorem
Liang-Ting Chen, Jiri Adamek, 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…
A Fibrational Approach to Automata Theory
Liang-Ting Chen, Henning Urbat
For predual categories C and D we establish isomorphisms between opfibrations representing local varieties of languages in C, local pseudovarieties of D-monoids, and finitely gener…
Varieties of Languages in a Category
Jiri Adamek, Stefan Milius, Robert Myers +1
Eilenberg's variety theorem, a centerpiece of algebraic automata theory, establishes a bijective correspondence between varieties of languages and pseudovarieties of monoids. In th…
Generalized Eilenberg Theorem I: Local Varieties of Languages
Jiri Adamek, Stefan Milius, Robert Myers +1
We investigate the duality between algebraic and coalgebraic recognition of languages to derive a generalization of the local version of Eilenberg's theorem. This theorem states th…