BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Mikołaj Bojańczyk

Mikołaj Bojańczyk appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Formal Languages and Automata TheoryLogic in Computer ScienceComputational ComplexityData Structures and AlgorithmsDiscrete Mathematicsmath.LO

Catalog footprint

What is connected

13works
6topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

13 published item(s)

preprint2022arXiv

Monadic Monadic Second Order Logic

One of the main reasons for the correspondence of regular languages and monadic second-order logic is that the class of regular languages is closed under images of surjective letter-to-letter homomorphisms. This closure property holds for structures such as finite words, finite trees, infinite words, infinite trees, elements of the free group, etc. Such structures can be modelled using monads. In this paper, we study which structures (understood via monads in the category of sets) are such that the class of regular languages (i.e. languages recognized by finite algebras) are closed under direct images of surjective letter-to-letter homomorphisms. We provide diverse sufficient conditions for a monad to satisfy this property. We also present numerous examples of monads, including positive examples that do not satisfy our sufficient conditions, and counterexamples where the closure property fails.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Languages recognised by finite semigroups, and their generalisations to objects such as trees and graphs, with an emphasis on definability in monadic second-order logic

These are lecture notes on the algebraic approach to regular languages. The classical algebraic approach is for finite words; it uses semigroups instead of automata. However, the algebraic approach can be extended to structures beyond words, e.g.~infinite words, or trees or graphs. The purpose of this book is to describe the algebraic approach in a way that covers these extensions.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Single use register automata for data words

Our starting point are register automata for data words, in the style of Kaminski and Francez. We study the effects of the single-use restriction, which says that a register is emptied immediately after being used. We show that under the single-use restriction, the theory of automata for data words becomes much more robust. The main results are: (a) five different machine models are equivalent as language acceptors, including one-way and two-way single-use register automata; (b) one can recover some of the algebraic theory of languages over finite alphabets, including a version of the Krohn-Rhodes Theorem; (c) there is also a robust theory of transducers, with four equivalent models, including two-way single use transducers and a variant of streaming string transducers for data words. These results are in contrast with automata for data words without the single-use restriction, where essentially all models are pairwise non-equivalent.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Definability equals recognizability for graphs of bounded treewidth

We prove a conjecture of Courcelle, which states that a graph property is definable in MSO with modular counting predicates on graphs of constant treewidth if, and only if it is recognizable in the following sense: constant-width tree decompositions of graphs satisfying the property can be recognized by tree automata. While the forward implication is a classic fact known as Courcelle's theorem, the converse direction remained open

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Transducers with origin information

Call a string-to-string transducer regular if it can be realised by one of the following equivalent models: mso transductions, two-way deterministic automata with output, and streaming transducers with registers. This paper proposes to treat origin information as part of the semantics of a regular string-to-string transducer. With such semantics, the model admits a machine-independent characterisation, Angluin-style learning in polynomial time, as well as effective characterisations of natural subclasses such as one-way transducers or first-order definable transducers.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Minimization of semilinear automata

We investigate finite deterministic automata in sets with non-homogeneous atoms: integers with successor. As there are uncount- ably many deterministic finite automata in this setting, we restrict our attention to automata with semilinear transition function. The main re- sults is a minimization procedure for semilinear automata. The proof is subtle and refers to decidability of existential Presburger arithmetic with divisibility predicates. Interestingly, the minimization is not obtained by the standard partition refinement procedure, and we demonstrate that this procedure does not necessarily terminate for semilinear automata.

0 citations0 reviewsNo code linkedOpen access