Search Results

Documents authored by Bojańczyk, Mikołaj

Document
DOI: 10.4230/LIPIcs.LICS.2026.21
Automata for MSO over Infinite Trees with Quantification over Borel Sets of Branches

Authors: Mikołaj Bojańczyk, Antonio Casares, Sven Manthe, and Paweł Parys

Published in: LIPIcs, Volume 380, 41st Annual Symposium on Logic in Computer Science (LICS 2026)

Abstract
Rabin’s Tree Theorem says that the {mso} theory of the infinite binary tree 2^* is decidable. Shelah showed that MSO logic becomes undecidable if this tree is extended to 2^{≤ω}, i.e. by allowing quantification over sets of infinite branches. A longstanding open problem is whether the decidability can be recovered in 2^{≤ω} by restricting set quantification to Borel sets. We make some progress in this direction, by identifying a suitable automaton model, and showing that most of the automata-theoretic approach to Rabin’s Theorem can be extended to the new framework. The only missing part is a conjecture about finite-memory determinacy in certain games. This paper states and explores the conjecture. We prove it in some restricted cases, and give lower bounds on the memory required in those games.
Cite as

Mikołaj Bojańczyk, Antonio Casares, Sven Manthe, and Paweł Parys. Automata for MSO over Infinite Trees with Quantification over Borel Sets of Branches. In 41st Annual Symposium on Logic in Computer Science (LICS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 380, pp. 21:1-21:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bojanczyk_et_al:LIPIcs.LICS.2026.21,
  author =	{Boja\'{n}czyk, Miko{\l}aj and Casares, Antonio and Manthe, Sven and Parys, Pawe{\l}},
  title =	{{Automata for MSO over Infinite Trees with Quantification over Borel Sets of Branches}},
  booktitle =	{41st Annual Symposium on Logic in Computer Science (LICS 2026)},
  pages =	{21:1--21:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-434-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{380},
  editor =	{Faggian, Claudia and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.LICS.2026.21},
  URN =		{urn:nbn:de:0030-drops-268080},
  doi =		{10.4230/LIPIcs.LICS.2026.21},
  annote =	{Keywords: MSO logic, automata over infinite trees, games on graphs}
}
Document
DOI: 10.4230/LIPIcs.LICS.2026.22
Low Rank MSO

Authors: Mikołaj Bojańczyk, Michał Pilipczuk, Wojciech Przybyszewski, Marek Sokołowski, and Giannos Stamoulis

Published in: LIPIcs, Volume 380, 41st Annual Symposium on Logic in Computer Science (LICS 2026)

Abstract
We introduce a new logic for describing properties of graphs, which we call low rank MSO. This is the fragment of monadic second-order logic in which set quantification is restricted to vertex sets of bounded cutrank. We prove the following statements about the expressive power of low rank MSO. - Over any class of graphs that is weakly sparse, low rank MSO has the same expressive power as separator logic. This equivalence does not hold over all graphs. - Over any class of graphs that has bounded VC dimension, low rank MSO has the same expressive power as flip-connectivity logic. This equivalence does not hold over all graphs. - Over all graphs, low rank MSO has the same expressive power as flip-reachability logic. Here, separator logic is an extension of first-order logic by basic predicates for checking connectivity, which was proposed by Bojańczyk [ArXiv 2107.13953] and by Schirrmacher, Siebertz, and Vigny [ACM ToCL 2023]. Flip-connectivity logic and flip-reachability logic are analogues of separator logic suited for non-sparse graphs, which we propose in this work. In particular, the last statement above implies that every property of undirected graphs expressible in low rank MSO can be decided in polynomial time.
Cite as

Mikołaj Bojańczyk, Michał Pilipczuk, Wojciech Przybyszewski, Marek Sokołowski, and Giannos Stamoulis. Low Rank MSO. In 41st Annual Symposium on Logic in Computer Science (LICS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 380, pp. 22:1-22:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bojanczyk_et_al:LIPIcs.LICS.2026.22,
  author =	{Boja\'{n}czyk, Miko{\l}aj and Pilipczuk, Micha{\l} and Przybyszewski, Wojciech and Soko{\l}owski, Marek and Stamoulis, Giannos},
  title =	{{Low Rank MSO}},
  booktitle =	{41st Annual Symposium on Logic in Computer Science (LICS 2026)},
  pages =	{22:1--22:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-434-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{380},
  editor =	{Faggian, Claudia and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.LICS.2026.22},
  URN =		{urn:nbn:de:0030-drops-268091},
  doi =		{10.4230/LIPIcs.LICS.2026.22},
  annote =	{Keywords: First Order logic, Monadic Second Order logic, cutrank, flips}
}
Document
DOI: 10.4230/LIPIcs.LICS.2026.82
The Finite Length Property of the Rado Graph and Friends

Authors: Jingjie Yang, Mikołaj Bojańczyk, and Bartek Klin

Published in: LIPIcs, Volume 380, 41st Annual Symposium on Logic in Computer Science (LICS 2026)

Abstract
An infinite structure has the finite length property (over a given field) if, for each of its finite powers, chains of equivariant subspaces in the corresponding free vector space are bounded in length. Prior work showed that the countable pure set and the countable dense linear order without endpoints have this property. We generalise these results to (a) any structure approximated by finite substructures with few orbits, provided the field is of characteristic zero, and (b) any Fraïssé limit with free amalgamation in a finite vocabulary consisting of unary and binary relations, possibly expanded with a generic total order. As a special case, we deduce the finite length property of the Rado graph using both methods. We also describe some connections with function spaces, weighted register automata, and orbit-finite systems of linear equations.
Cite as

Jingjie Yang, Mikołaj Bojańczyk, and Bartek Klin. The Finite Length Property of the Rado Graph and Friends. In 41st Annual Symposium on Logic in Computer Science (LICS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 380, pp. 82:1-82:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{yang_et_al:LIPIcs.LICS.2026.82,
  author =	{Yang, Jingjie and Boja\'{n}czyk, Miko{\l}aj and Klin, Bartek},
  title =	{{The Finite Length Property of the Rado Graph and Friends}},
  booktitle =	{41st Annual Symposium on Logic in Computer Science (LICS 2026)},
  pages =	{82:1--82:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-434-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{380},
  editor =	{Faggian, Claudia and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.LICS.2026.82},
  URN =		{urn:nbn:de:0030-drops-268695},
  doi =		{10.4230/LIPIcs.LICS.2026.82},
  annote =	{Keywords: Rado graph, oligomorphic structure, orbit-finite set, orbit-finitely spanned vector space, equivariant subspace, finite length}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2026.170
Transducers on Compressed Strings

Authors: Mikołaj Bojańczyk and Markus Lohrey

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
We study string-to-string functions which are compatible with compression in the following sense: given a compressed representation of an input string, one can compute in polynomial time a compressed representation of the output string. As the compression formalism, we use straight-line programs (i.e. context-free grammars that produce only one string). As the functions, we use finite state transducers, with a focus on the regular and polyregular functions. We show that all regular functions are compatible with compression, but this is no longer true for the polyregular functions. We identify a subclass of the polyregular functions - the so-called rectangular polyregular functions - which is compatible with compression, and we characterise this subclass in terms of a functional programming language.
Cite as

Mikołaj Bojańczyk and Markus Lohrey. Transducers on Compressed Strings. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 170:1-170:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bojanczyk_et_al:LIPIcs.ICALP.2026.170,
  author =	{Boja\'{n}czyk, Miko{\l}aj and Lohrey, Markus},
  title =	{{Transducers on Compressed Strings}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{170:1--170:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.170},
  URN =		{urn:nbn:de:0030-drops-265580},
  doi =		{10.4230/LIPIcs.ICALP.2026.170},
  annote =	{Keywords: polyregular functions, grammar compression}
}
Document
DOI: 10.4230/DagRep.15.3.177
Categories for Automata and Language Theory (Dagstuhl Seminar 25141)

Authors: Achim Blumensath, Mikołaj Bojańczyk, Bartek Klin, and Daniela Petrişan

Published in: Dagstuhl Reports, Volume 15, Issue 3 (2025)

Abstract
Categorical methods have a long history in automata and language theory, but a coherent theory has started to emerge only in recent years. The abstract viewpoint of category theory can provide a unifying perspective on various forms of automata; it can make it easier to bootstrap a theory in a new setting; and it provides conceptual clarity regarding which aspects and properties are fundamental and which are only coincidental. Due to being in its early stages, the field is currently still divided into several different communities with little connections between them. One of the central aims of the Dagstuhl Seminar "Categories for Automata and Language Theory" (25141) was to enhance communication between automata theory and category theory communities. To this end, the seminar brought together researchers from both areas and included introductory tutorials designed to provide common ground and help participants better understand each other’s approach and terminology. The following key topics were explored during the seminar: - Categorical unification of language theory, either via the theory of monads, or via the category of MSO-transductions and their composition; - Coalgebraic methods and their applications to automata theory, to infinite trace semantics and connection to bisimulation-invariant fragments of logics; - Functorial automata and generic algorithms therein; - Fibrational and monoidal perspectives on language theory; - Higher-order automata and profinite lambda-calculus.
Cite as

Achim Blumensath, Mikołaj Bojańczyk, Bartek Klin, and Daniela Petrişan. Categories for Automata and Language Theory (Dagstuhl Seminar 25141). In Dagstuhl Reports, Volume 15, Issue 3, pp. 177-200, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{blumensath_et_al:DagRep.15.3.177,
  author =	{Blumensath, Achim and Boja\'{n}czyk, Miko{\l}aj and Klin, Bartek and Petri\c{s}an, Daniela},
  title =	{{Categories for Automata and Language Theory (Dagstuhl Seminar 25141)}},
  pages =	{177--200},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2025},
  volume =	{15},
  number =	{3},
  editor =	{Blumensath, Achim and Boja\'{n}czyk, Miko{\l}aj and Klin, Bartek and Petri\c{s}an, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.15.3.177},
  URN =		{urn:nbn:de:0030-drops-248949},
  doi =		{10.4230/DagRep.15.3.177},
  annote =	{Keywords: categorical automata theory, automata theory, category theory, monads}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2024.130
Function Spaces for Orbit-Finite Sets

Authors: Mikołaj Bojańczyk, Lê Thành Dũng (Tito) Nguyễn, and Rafał Stefański

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
Orbit-finite sets are a generalisation of finite sets, and as such support many operations allowed for finite sets, such as pairing, quotienting, or taking subsets. However, they do not support function spaces, i.e. if X and Y are orbit-finite sets, then the space of finitely supported functions from X to Y is not orbit-finite. We propose a solution to this problem inspired by linear logic.
Cite as

Mikołaj Bojańczyk, Lê Thành Dũng (Tito) Nguyễn, and Rafał Stefański. Function Spaces for Orbit-Finite Sets. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 130:1-130:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bojanczyk_et_al:LIPIcs.ICALP.2024.130,
  author =	{Boja\'{n}czyk, Miko{\l}aj and Nguy\~{ê}n, L\^{e} Th\`{a}nh D\~{u}ng (Tito) and Stefa\'{n}ski, Rafa{\l}},
  title =	{{Function Spaces for Orbit-Finite Sets}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{130:1--130:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.130},
  URN =		{urn:nbn:de:0030-drops-202730},
  doi =		{10.4230/LIPIcs.ICALP.2024.130},
  annote =	{Keywords: Orbit-finite sets, automata, linear types, game semantics}
}
Document
DOI: 10.4230/DagRep.13.5.96
Regular Transformations (Dagstuhl Seminar 23202)

Authors: Rajeev Alur, Mikołaj Bojańczyk, Emmanuel Filiot, Anca Muscholl, and Sarah Winter

Published in: Dagstuhl Reports, Volume 13, Issue 5 (2023)

Abstract
This report documents the program and the outcomes of the Dagstuhl Seminar 23202 "Regular Transformations". The goal of this seminar was to advance on a list of topics about transducers that have gathered much interest recently, and to explore new connections between the theory of regular transformations and its applications in linguistics.
Cite as

Rajeev Alur, Mikołaj Bojańczyk, Emmanuel Filiot, Anca Muscholl, and Sarah Winter. Regular Transformations (Dagstuhl Seminar 23202). In Dagstuhl Reports, Volume 13, Issue 5, pp. 96-113, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{alur_et_al:DagRep.13.5.96,
  author =	{Alur, Rajeev and Boja\'{n}czyk, Miko{\l}aj and Filiot, Emmanuel and Muscholl, Anca and Winter, Sarah},
  title =	{{Regular Transformations (Dagstuhl Seminar 23202)}},
  pages =	{96--113},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{13},
  number =	{5},
  editor =	{Alur, Rajeev and Boja\'{n}czyk, Miko{\l}aj and Filiot, Emmanuel and Muscholl, Anca and Winter, Sarah},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.5.96},
  URN =		{urn:nbn:de:0030-drops-193663},
  doi =		{10.4230/DagRep.13.5.96},
  annote =	{Keywords: transducers; (poly-)regular functions; linguistic transformations}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2023.117
Algebraic Recognition of Regular Functions

Authors: Mikołaj Bojańczyk and Lê Thành Dũng (Tito) Nguyễn

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
We consider regular string-to-string functions, i.e. functions that are recognized by copyless streaming string transducers, or any of their equivalent models, such as deterministic two-way automata. We give yet another characterization, which is very succinct: finiteness-preserving functors from the category of semigroups to itself, together with a certain output function that is a natural transformation.
Cite as

Mikołaj Bojańczyk and Lê Thành Dũng (Tito) Nguyễn. Algebraic Recognition of Regular Functions. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 117:1-117:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bojanczyk_et_al:LIPIcs.ICALP.2023.117,
  author =	{Boja\'{n}czyk, Miko{\l}aj and Nguy\~{ê}n, L\^{e} Th\`{a}nh D\~{u}ng (Tito)},
  title =	{{Algebraic Recognition of Regular Functions}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{117:1--117:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.117},
  URN =		{urn:nbn:de:0030-drops-181697},
  doi =		{10.4230/LIPIcs.ICALP.2023.117},
  annote =	{Keywords: string transducers, semigroups, category theory}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.ICALP.2022
LIPIcs, Volume 229, ICALP 2022, Complete Volume

Authors: Mikołaj Bojańczyk, Emanuela Merelli, and David P. Woodruff

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
LIPIcs, Volume 229, ICALP 2022, Complete Volume
Cite as

49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 1-2516, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Proceedings{bojanczyk_et_al:LIPIcs.ICALP.2022,
  title =	{{LIPIcs, Volume 229, ICALP 2022, Complete Volume}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{1--2516},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022},
  URN =		{urn:nbn:de:0030-drops-163400},
  doi =		{10.4230/LIPIcs.ICALP.2022},
  annote =	{Keywords: LIPIcs, Volume 229, ICALP 2022, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.ICALP.2022.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Mikołaj Bojańczyk, Emanuela Merelli, and David P. Woodruff

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 0:i-0:xxxvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bojanczyk_et_al:LIPIcs.ICALP.2022.0,
  author =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{0:i--0:xxxvi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.0},
  URN =		{urn:nbn:de:0030-drops-163417},
  doi =		{10.4230/LIPIcs.ICALP.2022.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.FSTTCS.2021
LIPIcs, Volume 213, FSTTCS 2021, Complete Volume

Authors: Mikołaj Bojańczyk and Chandra Chekuri

Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

Abstract
LIPIcs, Volume 213, FSTTCS 2021, Complete Volume
Cite as

41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 1-866, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Proceedings{bojanczyk_et_al:LIPIcs.FSTTCS.2021,
  title =	{{LIPIcs, Volume 213, FSTTCS 2021, Complete Volume}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{1--866},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021},
  URN =		{urn:nbn:de:0030-drops-155102},
  doi =		{10.4230/LIPIcs.FSTTCS.2021},
  annote =	{Keywords: LIPIcs, Volume 213, FSTTCS 2021, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.FSTTCS.2021.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Mikołaj Bojańczyk and Chandra Chekuri

Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bojanczyk_et_al:LIPIcs.FSTTCS.2021.0,
  author =	{Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{0:i--0:xvi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.0},
  URN =		{urn:nbn:de:0030-drops-155113},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.19
Some Remarks on Deciding Equivalence for Graph-To-Graph Transducers

Authors: Mikołaj Bojańczyk and Janusz Schmude

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
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.
Cite as

Mikołaj Bojańczyk and Janusz Schmude. Some Remarks on Deciding Equivalence for Graph-To-Graph Transducers. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bojanczyk_et_al:LIPIcs.MFCS.2020.19,
  author =	{Boja\'{n}czyk, Miko{\l}aj and Schmude, Janusz},
  title =	{{Some Remarks on Deciding Equivalence for Graph-To-Graph Transducers}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.19},
  URN =		{urn:nbn:de:0030-drops-127529},
  doi =		{10.4230/LIPIcs.MFCS.2020.19},
  annote =	{Keywords: equivalence for mso transductions, bounded treewidth, Hilbert basis theorem}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2020.113
Single-Use Automata and Transducers for Infinite Alphabets

Authors: Mikołaj Bojańczyk and Rafał Stefański

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
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.
Cite as

Mikołaj Bojańczyk and Rafał Stefański. Single-Use Automata and Transducers for Infinite Alphabets. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 113:1-113:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bojanczyk_et_al:LIPIcs.ICALP.2020.113,
  author =	{Boja\'{n}czyk, Miko{\l}aj and Stefa\'{n}ski, Rafa{\l}},
  title =	{{Single-Use Automata and Transducers for Infinite Alphabets}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{113:1--113:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.113},
  URN =		{urn:nbn:de:0030-drops-125200},
  doi =		{10.4230/LIPIcs.ICALP.2020.113},
  annote =	{Keywords: Automata, semigroups, data words, orbit-finite sets}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2019.106
String-to-String Interpretations With Polynomial-Size Output (Track B: Automata, Logic, Semantics, and Theory of Programming)

Authors: Mikołaj Bojańczyk, Sandra Kiefer, and Nathan Lhote

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
String-to-string MSO interpretations are like Courcelle’s MSO transductions, except that a single output position can be represented using a tuple of input positions instead of just a single input position. In particular, the output length is polynomial in the input length, as opposed to MSO transductions, which have output of linear length. We show that string-to-string MSO interpretations are exactly the polyregular functions. The latter class has various characterisations, one of which is that it consists of the string-to-string functions recognised by pebble transducers. Our main result implies the surprising fact that string-to-string MSO interpretations are closed under composition.
Cite as

Mikołaj Bojańczyk, Sandra Kiefer, and Nathan Lhote. String-to-String Interpretations With Polynomial-Size Output (Track B: Automata, Logic, Semantics, and Theory of Programming). In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 106:1-106:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bojanczyk_et_al:LIPIcs.ICALP.2019.106,
  author =	{Boja\'{n}czyk, Miko{\l}aj and Kiefer, Sandra and Lhote, Nathan},
  title =	{{String-to-String Interpretations With Polynomial-Size Output}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{106:1--106:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.106},
  URN =		{urn:nbn:de:0030-drops-106821},
  doi =		{10.4230/LIPIcs.ICALP.2019.106},
  annote =	{Keywords: MSO, interpretations, pebble transducers, polyregular functions}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact