Arrow Research search

Author name cluster

Mikolaj Bojanczyk

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

10 papers
2 author rows

Possible papers

10

MFCS Conference 2020 Conference Paper

Some Remarks on Deciding Equivalence for Graph-To-Graph Transducers

  • Mikolaj Bojanczyk
  • Janusz Schmude

We study the following decision problem: given two mso transductions that input and output graphs of bounded treewidth, decide if they are equivalent, i. e. isomorphic inputs give isomorphic outputs. We do not know how to decide it, but we propose an approach that uses automata manipulating elements of a ring extended with division. The approach works for a variant of the problem, where isomorphism on output graphs is replaced by a relaxation of isomorphism.

Details

Highlights Conference 2018 Conference Abstract

Regular and First Order List Functions

  • Mikolaj Bojanczyk

ABSTRACT. We define two classes of functions, called regular (respectively, first-order) list functions, which manipulate objects such as lists, lists of lists, pairs of lists, lists of pairs of lists, etc. The definition is in the style of regular expressions: the functions are constructed by starting with some basic functions (e. g. projections from pairs, or head and tail operations on lists) and putting them together using four combinators (most importantly, composition of functions). Our main results are that first-order list functions are exactly the same as first-order transductions, under a suitable encoding of the inputs; and the regular list functions are exactly the same as MSO-transductions. A paper at LICS 2018, joint with Laure Daviaud and Krishna Shankara Narayanan https: //arxiv. org/abs/1803. 06168

Details

Highlights Conference 2017 Conference Abstract

A Proof of Courcelle’s Conjecture on Recognisable Graph Classes

  • Mikolaj Bojanczyk

Courcelle’s conjecture says that for classes of bounded treewidth, definability in MSO is the same as recognisability. More precisely, consider the following notions: (D) a class of graphs is called MSO definable if it can be defined in monadic second-order logic (with counting quantifiers). (R) a class of graphs is called recognisable if for each k there is a tree automaton which recognises width k tree decompositions of graphs satisfying the property. Many natural graph classes are easily seen to satisfy (D), e. g. graphs with Hamiltonian (or Euler) paths, or 3-colourable graphs. Courcelle’s Theorem says that (D) implies (R). Courcelle’s Conjecture says that (R) implies (D) for classes of bounded tree width. In the talk, I will discuss a proof of this conjecture. Slides https: //www. mimuw. edu. pl/~bojan/slides/graph-reco/ (Joint work with Michał Pilipczuk)

PDF Details

Highlights Conference 2016 Conference Abstract

A Proof of Courcelle’s Conjecture on Recognisable Graph Classes

  • Mikolaj Bojanczyk

Courcelle’s conjecture says that for classes of bounded treewidth, definability in MSO is the same as recognisability. More precisely, consider the following notions: (D) a class of graphs is called MSO definable if it can be defined in monadic second-order logic (with counting quantifiers). (R) a class of graphs is called recognisable if for each k there is a tree automaton which recognises width k tree decompositions of graphs satisfying the property. Many natural graph classes are easily seen to satisfy (D), e. g. graphs with Hamiltonian (or Euler) paths, or 3-colourable graphs. Courcelle’s Theorem says that (D) implies (R). Courcelle’s Conjecture says that (R) implies (D) for classes of bounded tree width. In the talk, I will discuss a proof of this conjecture. Slides https: //www. mimuw. edu. pl/~bojan/slides/graph-reco/ (Joint work with Michał Pilipczuk)

PDF Details

MFCS Conference 2016 Invited Paper

Decidable Extensions of MSO

  • Mikolaj Bojanczyk

This is an overview of the invited talk delivered at the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS-2016).

Details

CSL Conference 2009 Invited Paper

Algebra for Tree Languages

  • Mikolaj Bojanczyk

Abstract There are at least as many interesting classes of regular tree languages as there are of regular word languages. However, much less is known about the former ones. In particular, very few effective characterizations of tree language classes are known. Since for words most known characterizations are obtained using algebra, it seems to be a good idea to look for an algebra for tree languages. I will talk about one such attempt, which is called forest algebra. (Other frameworks in the literature include pre-clones of Ésik and Weil or tree algebra of Wilke. Another approach is to forget about algebra and study the structure of a tree automaton.)

Details

CSL Conference 2007 Conference Paper

Forest Expressions

  • Mikolaj Bojanczyk

Abstract We define regular expressions for unranked trees (actually, ordered sequences of unranked trees, called forests). These are compared to existing regular expressions for trees. On the negative side, our expressions have complementation, and do not define all regular languages. On the positive side, our expressions do not use variables, and have a syntax very similar to that of regular expressions for word languages. We examine the expressive power of these expressions, especially from a logical point of view. The class of languages defined corresponds to a form of chain logic [5, 6]. Furthermore, the star-free expressions coincide with first-order logic. Finally, we show that a concatenation hierarchy inside the expressions corresponds to the quantifier prefix hierarchy for first-order logic, generalizing a result of Thomas.

Details

MFCS Conference 2007 Conference Paper

Shuffle Expressions and Words with Nested Data

  • Henrik Björklund
  • Mikolaj Bojanczyk

Abstract In this paper, we develop a theory that studies words with nested data values with the help of shuffle expressions. We study two cases, which we call “ordered” and “unordered”. In the unordered case, we show that emptiness (of the two related problems) is decidable. In the ordered case, we prove undecidability. As a proof vehicle for the latter, we introduce the notion of higher-order multicounter automata.

Details

STOC Conference 2005 Conference Paper

Tree-walking automata do not recognize all regular languages

  • Mikolaj Bojanczyk
  • Thomas Colcombet

Tree-walking automata are a natural sequential model for recognizing tree languages. Every tree language recognized by a tree-walking automaton is regular. In this paper, we present a tree language which is regular but not recognized by any (nondeterministic) tree-walking automaton. This settles a conjecture of Engelfriet, Hoogeboom and Van Best. Moreover, the separating tree language is definable already in first-order logic over a signature containing the left-son, right-son and ancestor relations.

Details

CSL Conference 2004 Conference Paper

A Bounding Quantifier

  • Mikolaj Bojanczyk

Abstract The logic MSOL+ \(\mathbb{B}\) is defined, by extending monadic second-order logic on the infinite binary tree with a new bounding quantifier \(\mathbb{B}\). In this logic, a formula \(\mathbb{B}\) X. φ ( X ) states that there is a finite bound on the size of sets satisfying φ ( X ). Satisfiability is proved decidable for two fragments of MSOL+ \(\mathbb{B}\): formulas of the form \(\neg\mathbb{B}\) X. φ ( X ), with φ a \(\mathbb{B}\) -free formula; and formulas built from \(\mathbb{B}\) -free formulas by nesting \(\mathbb{B}\), ∃, ∨ and ∧.

Details
v2026.09.13