BZPEERReading, trust and collaboration for researchDiscover
Workspaces
Network
Opportunities
Account
Researcher profile
Dexter Kozen contributes to research discovery and scholarly infrastructure.
Trust snapshot
Actions
Identity and collaboration
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Claim this author entity first to unlock direct invitations.
Research graph
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
Algorithms for deriving Huffman codes and the recently developed algorithm for compiling PIFO trees to trees of fixed shape (Mohan et al. 2022) are similar, but work with different underlying algebraic operations. In this paper, we exploit the monadic structure of prefix codes to create a generalized Huffman algorithm that has these two applications as special cases.
Automata models for data languages (i.e. languages over infinite alphabets) often feature either global or local freshness operators. We show that Bollig et al.'s session automata, which focus on global freshness, are equivalent to regular nondeterministic nominal automata (RNNA), a natural nominal automaton model with explicit name binding that has appeared implicitly in the semantics of nominal Kleene algebra (NKA), an extension of Kleene algebra with name binding. The expected Kleene theorem for NKA is known to fail in one direction, i.e. there are nominal languages that can be accepted by an RNNA but are not definable in NKA; via session automata, we obtain a full Kleene theorem for RNNAs for an expression language that extends NKA with unscoped name binding. Based on the equivalence with RNNAs, we then slightly rephrase the known equivalence checking algorithm for session automata. Reinterpreting the data language semantics of name binding by unrestricted instead of clean alpha-equivalence, we obtain a local freshness semantics as a quotient of the global freshness semantics. Under local freshness semantics, RNNAs turn out to be equivalent to a natural subclass of Bojanczyk et al.'s nondeterministic orbit-finite automata. We establish decidability of inclusion under local freshness by modifying the RNNA-based algorithm; in summary, we obtain a formalism for local freshness in data languages that is reasonably expressive and has a decidable inclusion problem.
Stone-type dualities provide a powerful mathematical framework for studying properties of logical systems. They have recently been fruitfully explored in understanding minimisation of various types of automata. In Bezhanishvili et al. (2012), a dual equivalence between a category of coalgebras and a category of algebras was used to explain minimisation. The algebraic semantics is dual to a coalgebraic semantics in which logical equivalence coincides with trace equivalence. It follows that maximal quotients of coalgebras correspond to minimal subobjects of algebras. Examples include partially observable deterministic finite automata, linear weighted automata viewed as coalgebras over finite-dimensional vector spaces, and belief automata, which are coalgebras on compact Hausdorff spaces. In Bonchi et al. (2014), Brzozowski's double-reversal minimisation algorithm for deterministic finite automata was described categorically and its correctness explained via the duality between reachability and observability. This work includes generalisations of Brzozowski's algorithm to Moore and weighted automata over commutative semirings. In this paper we propose a general categorical framework within which such minimisation algorithms can be understood. The goal is to provide a unifying perspective based on duality. Our framework consists of a stack of three interconnected adjunctions: a base dual adjunction that can be lifted to a dual adjunction between coalgebras and algebras and also to a dual adjunction between automata. The approach provides an abstract understanding of reachability and observability. We illustrate the general framework on range of concrete examples, including deterministic Kripke frames, weighted automata, topological automata (belief automata), and alternating automata.