You are not logged in | Log in

Mikołaj Bojańczyk

Number of publications: 107

2024

Mikołaj Bojańczyk , Lê Thành Dũng (Tito) Nguyen, Rafał Stefański , Function Spaces for Orbit-Finite Sets, 51st International Colloquium on Automata, Languages and Programming, Tallinn, Estonia, 8 July 2024 - 12 July 2024. See in PBN
Mikołaj Bojańczyk , Joanna Fijalkow, Bartek Klin, Joshua Moerman, Orbit-Finite-Dimensional Vector Spaces and Weighted Register Automata, TheoretiCS, Volume 3 2024, p. 1-41. See in PBN
Mikołaj Bojańczyk , Bartek Klin, Polyregular Functions on Unordered Trees of Bounded Height, Proceedings of the ACM on Programming Languages, 8 (POPL) 2024, p. 1326-1351. See in PBN
Mikołaj Bojańczyk , Pierre Ohlmann, Rank-decreasing transductions, 39th Annual ACM/IEEE Symposium on Logic in Computer Science, Tallinn, Estonia, 8 July 2024 - 11 July 2024, 17 2024, p. 1-13. See in PBN

2023

Mikołaj Bojańczyk , Lê Thành Dũng Nguyễn, Algebraic Recognition of Regular Functions, 50th EATCS International Colloquium on Automata, Languages and Programming, Padeborn, Germany, 10 July 2023 - 14 July 2023, 261 2023, p. 117:1-117:19. See in PBN
Mikołaj Bojańczyk , Folding interpretations, Thirty-Eighth Annual ACM/IEEE Symposium on Logic in Computer Science, Boston, the United States of America, 26 June 2023 - 29 June 2023, 170 2023, p. 1-13. See in PBN
Mikołaj Bojańczyk , On the Growth Rates of Polyregular Functions, Thirty-Eighth Annual ACM/IEEE Symposium on Logic in Computer Science, Boston, the United States of America, 26 June 2023 - 29 June 2023. See in PBN

2022

Mikołaj Bojańczyk , Michał Pilipczuk , Optimizing tree decompositions in MSO, Logical Methods in Computer Science, Volume 18, Issue 1 2022. See in PBN
Mikołaj Bojańczyk , Transducers of polynomial growth, 37'th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, 2 August 2022 - 5 August 2022. See in PBN

2021

Mikołaj Bojańczyk , Martin Grohe, Michał Pilipczuk , Definable decompositions for graphs of bounded linear cliquewidth, Logical Methods in Computer Science, 17 (1) 2021, p. 1-40. See in PBN
Mikołaj Bojańczyk , Bartosz Klin , Joshua Moerman, Orbit-Finite-Dimensional Vector Spaces and Weighted Register Automata, 36th Annual ACM/IEEE Symposium on Logic in Computer Science, Rome, Italy, 29 June 2021 - 2 July 2021. See in PBN
Mikołaj Bojańczyk , Thomas Brihaye, Christoph Haase, Sławomir Lasota , Joel Ouaknine, Igor Potapov, Preface, Information and Computation, 277 2021, p. 104579. See in PBN

2020

Georg Zetzsche, Mikołaj Bojańczyk , Rafał Stefański , Edon Kelmendi, Extensions of ω-Regular Languages, Thirty-Fifth Annual ACM/IEEE Symposium on Logic in Computer Science, Saarbrücken, Germany, 8 July 2020 - 11 July 2020. See in PBN
Amina Doumane, Mikołaj Bojańczyk , First-order tree-to-tree functions, Thirty-Fifth Annual ACM/IEEE Symposium on Logic in Computer Science, Saarbrücken, Germany, 8 July 2020 - 11 July 2020. See in PBN
Mikołaj Bojańczyk , Rafał Stefański , Single-Use Automata and Transducers for Infinite Alphabets, 47th International Colloquium on Automata, Languages and Programming, Saarbrücken, Germany, 8 July 2020 - 11 July 2020. See in PBN
Janusz Schmude, Mikołaj Bojańczyk , Some Remarks on Deciding Equivalence for Graph-To-Graph Transducers, 45th International Symposium on Mathematical Foundations of Computer Science, Prague, Czechia, 24 August 2020 - 28 August 2020, 170 2020, p. 19:1--19:14. See in PBN
Mikołaj Bojańczyk , Laure Daviaud, Sreejith Ajithkumar Vijayalekshmi, Vincent Penelle, Bruno Guillon, Undecidability of a weak version of MSO+U, Logical Methods in Computer Science, 16 (1) 2020. See in PBN

2019

Mikołaj Bojańczyk , Bartosz Klin , A non-regular language of infinite trees that is recognized by a sort-wise finite Algebra, Logical Methods in Computer Science, 14 (4) 2019, p. 11:1–11:13. See in PBN
Mikołaj Bojańczyk , Edon Kelmendi, Michał Skrzypczak , MSO+∇ is undecidable, Thirty-Fourth Annual ACM/IEEE Symposium on Logic in Computer Science, Vancouver, Canada, 24 July 2019 - 27 July 2019. See in PBN
Mikołaj Bojańczyk , Filippo Cavallari, Thomas Place, Michał Skrzypczak , Regular tree languages in low levels of the Wadge Hierarchy, Logical Methods in Computer Science, 15 (3) 2019, p. 27:1–27:61. See in PBN
Mikołaj Bojańczyk , Sandra Kiefer, Nathan Lhote, String-to-String Interpretations With Polynomial-Size Output, 46th International Colloquium on Automata, Languages and Programming, Patras, Greece, 8 July 2019 - 12 July 2019. See in PBN

2018

Mikołaj Bojańczyk , Martin Grohe, Michał Pilipczuk , Definable decompositions for graphs of bounded linear cliquewidth, Thirty-Third Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Oxford, the United Kingdom of Great Britain and Northern Ireland, 9 July 2018 - 12 July 2018. See in PBN
Mikołaj Bojańczyk , Szymon Toruńczyk , On computability and tractability for infinite sets, Thirty-Third Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Oxford, the United Kingdom of Great Britain and Northern Ireland, 9 July 2018 - 12 July 2018. See in PBN

2017

Damian Niwiński , Henryk Michalewski , Wojciech Rytter , Joost Winter, Michał Skrzypczak , Szymon Toruńczyk , Michał Pilipczuk , Eryk Kopczyński , Sławomir Lasota , Paweł Parys , Joanna Ochremiak, Wojciech Czerwiński , Bartosz Klin , Igor Walukiewicz, Szczepan Hummel, Mikołaj Bojańczyk , Piotr Hofman , Lorenzo Clemente , Filip Mazowiecki, Filip Murlak , 200 Problems in Formal Languages and Automata Theory, 2017. See in PBN
Hugo Gimbert, Mikołaj Bojańczyk , Edon Kelmendi, Emptiness of Zero Automata Is Decidable, 44th International Colloquium on Automata, Languages, and Programming, Warszawa, Poland, 10 July 2017 - 14 July 2017. See in PBN
Mikołaj Bojańczyk , It is Undecidable if Two Regular Tree Languages can be Separated by a Deterministic Tree-walking Automaton, Fundamenta Informaticae, 154 (1-4) 2017, p. 37-46. See in PBN
Mikołaj Bojańczyk , Michał Pilipczuk , Optimizing Tree Decompositions in MSO, 34th International Symposium on Theoretical Aspects of Computer Science, Hannover, Germany, 8 March 2017 - 11 March 2017. See in PBN
Mikołaj Bojańczyk , Laure Daviaud, Bruno Guillon, Vincent Penelle, Which Classes of Origin Graphs Are Generated by Transducers, 44th International Colloquium on Automata, Languages, and Programming, Warszawa, Poland, 10 July 2017 - 14 July 2017. See in PBN

2016

Mikołaj Bojańczyk , Michał Pilipczuk , Definability equals recognizability for graphs of bounded treewidth, 2016. See in PBN
Mikołaj Bojańczyk , Henryk Michalewski , Matteo Mio, On the Regular Emptiness Problem of Subzero Automata, 2016. See in PBN
Mikołaj Bojańczyk , Paweł Parys , Szymon Toruńczyk , The MSO+U Theory of (N,<) Is Undecidable, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), Orlean, France, 17 February 2016 - 20 February 2016. See in PBN
Mikołaj Bojańczyk , Thin MSO with a Probabilistic Path Quantifier, 2016. See in PBN

2015

Mikołaj Bojańczyk , Filip Murlak , Adam Witkowski, Containment of Monadic Datalog Programs via Bounded Clique-Width, 42nd International Colloquium on Automata, Languages, and Programming, Kyoto, Japan, 6 July 2015 - 10 July 2015. See in PBN
Mikołaj Bojańczyk , Sławomir Lasota , Igor Potapov, Reachability Problems - 9th International Workshop, {RP} 2015, Warsaw, Poland, September 21-23, 2015, Proceedings, Reachability Problems, Warsaw, Poland, 2015. See in PBN
Mikołaj Bojańczyk , Tomasz Idziaszek, Michał Skrzypczak , Regular languages of thin trees, Theory of Computing Systems, 2015. See in PBN

2014

Mikołaj Bojańczyk , Bartosz Klin , Sławomir Lasota , Automata theory in nominal sets, Logical Methods in Computer Science, 2014. See in PBN
Mikołaj Bojańczyk , Christoph Dittmann, Stephan Kreutzer, Decomposition theorems and model-checking for the modal \emph\(\mu\)-calculus, Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), CSL-LICS '14, Vienna, Austria, July 14 - 18, 2014, Vienna, Austria, 14 July 2015 - 18 July 2015. See in PBN
Mikołaj Bojańczyk , Tomasz Gogacz, Henryk Michalewski , Michał Skrzypczak , On the Decidability of MSO+U on Infinite Trees, International Colloquium on Automata, Languages and Programming, 2014. See in PBN
Mikołaj Bojańczyk , Stanisław Szawiel, Marek Zawadowski , Rigidity is undecidable, Mathematical Structures in Computer Science, 24 (6) 2014, p. 1-10. See in PBN
Mikołaj Bojańczyk , Transducers with Origin Information, Automata, Languages, and Programming - 41st International Colloquium, Kopenhaga, Denmark, 8 July 2013 - 11 July 2013. See in PBN
Mikołaj Bojańczyk , Weak MSO+U with Path Quantifiers over Infinite Trees, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II, 2014. See in PBN

2013

Mikołaj Bojańczyk , Nominal Monoids, Theory of Computing Systems, 53 (2) 2013, p. 194-222. See in PBN
Mikołaj Bojańczyk , Tomasz Idziaszek, Michał Skrzypczak , Regular languages of thin trees, 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, Kiel, Germany, 27 February 2013 - 2 March 2013. See in PBN
Mikołaj Bojańczyk , Leszek Kołodziejczyk , Filip Murlak , Solutions in XML data exchange, Journal of Computer and System Sciences, 79 (6) 2013, p. 785-815. See in PBN
Mikołaj Bojańczyk , Bartosz Klin , Sławomir Lasota , Szymon Toruńczyk , Turing machines with atoms, 28th Annual ACM/IEEE Symposium on Logic in Computer Science, the United States of America, 25 June 2013 - 28 June 2013. See in PBN
Mikołaj Bojańczyk , Luc Segoufin, Szymon Toruńczyk , Verification of database-driven systems via amalgamation, {Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2013. See in PBN

2012

Sławomir Lasota , Mikołaj Bojańczyk , A machine-independent characterization of timed languages, Lecture Notes in Computer Science, International Colloquium on Automata, Languages and Programming, 2012. See in PBN
Mikołaj Bojańczyk , Algorithms for regular languages that use algebra, SIAM Journal on Computing, 2012. See in PBN
Mikołaj Bojańczyk , Sławomir Lasota , An extension of data automata that captures XPath, Logical Methods in Computer Science, 2012. See in PBN
Mikołaj Bojańczyk , Vince Bárány, Diego Figueira, Paweł Parys , Decidable Classes of Documents for XPath, 2012. See in PBN
Mikołaj Bojańczyk , Vince Bárány, Finite satisfiability for guarded fixpoint logic, Information Processing Letters, 2012. See in PBN
Mikołaj Bojańczyk , Sławomir Lasota , Fraenkel-Mostowski Sets with Non-homogeneous Atoms, 2012. See in PBN
Mikołaj Bojańczyk , Szymon Toruńczyk , Imperative Programming in Sets with Atoms, 2012. See in PBN
Mikołaj Bojańczyk , Luc Segoufin, Howard Straubing, Piecewise testable tree languages, Logical Methods in Computer Science, 2012. See in PBN
Eryk Kopczyński , Mikołaj Bojańczyk , Szymon Toruńczyk , Ramsey’s theorem for colors from a metric space, Semigroup Forum, 2012. See in PBN
Mikołaj Bojańczyk , Thomas Place, Regular Languages of Infinite Trees That Are Boolean Combinations of Open Sets, 2012. See in PBN
Mikołaj Bojańczyk , Thomas Place, Toward Model Theory with Data Values, 2012. See in PBN
Laurent Braud, Sławomir Lasota , Bartek Klin, Mikołaj Bojańczyk , Towards nominal computation, ACM SIGPLAN NOTICES, 39th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Philadelphia, the United States of America, 22 January 2012 - 28 January 2012. See in PBN
Mikołaj Bojańczyk , Szymon Toruńczyk , Weak MSO+U over infinite trees, 2012. See in PBN
Mikołaj Bojańczyk , Howard Straubing, Igor Walukiewicz, Wreath Products of Forest Algebras, with Applications to Tree Logics, Logical Methods in Computer Science, 2012. See in PBN

2011

Mikołaj Bojańczyk , Bartosz Klin , Sławomir Lasota , Automata with group actions, 2011. See in PBN
Mikołaj Bojańczyk , Data Monoids, 2011. See in PBN
Mikołaj Bojańczyk , Diego Figueira, Efficient evaluation for a temporal logic on changing XML documents, 2011. See in PBN
Albert Atserias, Mikołaj Bojańczyk , Ronald Fagin, Floris Geerts, Kenneth Ross, Balder ten Cate, Foreword, Theory of Computing Systems, 2011. See in PBN
Mikołaj Bojańczyk , Leszek Kołodziejczyk , Filip Murlak , Solutions in XML data exchange, 2011. See in PBN
Mikołaj Bojańczyk , Claire David, Anca Muscholl, Thomas Schwentick, Luc Segoufin, Two-variable logic on data words, ACM Transactions on Computational Logic, 2011. See in PBN
Mikołaj Bojańczyk , Weak MSO with the Unbounding Quantifier, Theory of Computing Systems, 2011. See in PBN
Mikołaj Bojańczyk , Paweł Parys , XPath Evaluation in Linear Time, JOURNAL OF THE ACM, 2011. See in PBN

2010

Mikołaj Bojańczyk , Sławomir Lasota , An Extension of Data Automata that Captures XPath, 2010. See in PBN
Mikołaj Bojańczyk , Automata for Data Words and Data Trees, 2010. See in PBN
Mikołaj Bojańczyk , Beyond omega-Regular Languages, 2010. See in PBN
Mikołaj Bojańczyk , Paweł Parys , Efficient Evaluation of Nondeterministic Automata Using Factorization Forests, Lecture Notes in Computer Science, 2010. See in PBN
Mikołaj Bojańczyk , Damian Niwiński , Alexander Rabinovich, Adam Radziwonczyk-Syta, Michał Skrzypczak , On the Borel Complexity of MSO Definable Sets of Branches, Fundamenta Informaticae, 2010. See in PBN
Mikołaj Bojańczyk , Luc Segoufin, Tree Languages Defined in First-Order Logic with One Quantifier Alternation, Logical Methods in Computer Science, 2010. See in PBN

2009

Mikołaj Bojańczyk , Tomasz Idziaszek, Algebra for Infinite Forests with an Application to the Temporal Logic EF, Lecture Notes in Computer Science, 2009. See in PBN
Mikołaj Bojańczyk , Algebra for Tree Languages, Lecture Notes in Computer Science, 2009. See in PBN
Mikołaj Bojańczyk , Szymon Toruńczyk , Deterministic Automata and Extensions of Weak MSO, 2009. See in PBN
Mikołaj Bojańczyk , Factorization Forests, Lecture Notes in Computer Science, 2009. See in PBN
Mikołaj Bojańczyk , Anca Muscholl, Thomas Schwentick, Luc Segoufin, Two-variable logic on data trees and XML reasoning, JOURNAL OF THE ACM, 2009. See in PBN
Mikołaj Bojańczyk , Two-Way Unary Temporal Logic over Trees, Logical Methods in Computer Science, 2009. See in PBN
Mikołaj Bojańczyk , Weak MSO with the Unbounding Quantifier, 2009. See in PBN
Mikołaj Bojańczyk , Howard Straubing, Igor Walukiewicz, Wreath Products of Forest Algebras, with Applications to Tree Logics, 2009. See in PBN

2008

Mikołaj Bojańczyk , Luc Segoufin, Howard Straubing, Piecewise Testable Tree Languages, 2008. See in PBN
Mikołaj Bojańczyk , The Common Fragment of ACTL and LTL, Lecture Notes in Computer Science, 2008. See in PBN
Mikołaj Bojańczyk , Luc Segoufin, Tree Languages Defined in First-Order Logic with One Quantifier Alternation, Lecture Notes in Computer Science, 2008. See in PBN
Mikołaj Bojańczyk , Tree-Walking Automata, Lecture Notes in Computer Science, 2008. See in PBN
Mikołaj Bojańczyk , Thomas Colcombet, Tree-Walking Automata Do Not Recognize All Regular Languages, SIAM Journal on Computing, 2008. See in PBN
Mikołaj Bojańczyk , Paweł Parys , XPath Evaluation in Linear Time, 2008. See in PBN

2007

Mikołaj Bojańczyk , A new algorithm for testing if a regular language is locally threshold testable, Information Processing Letters, 2007. See in PBN
Henrik Bjorklund, Mikołaj Bojańczyk , Bounded Depth Data Trees, Lecture Notes in Computer Science, 2007. See in PBN
Mikołaj Bojańczyk , Forest Expressions, Lecture Notes in Computer Science, 2007. See in PBN
Mikołaj Bojańczyk , Piotr Hoffman, Reachability in Unions of Commutative Rewriting Systems Is Decidable, Lecture Notes in Computer Science, 2007. See in PBN
Henrik Bjorklund, Mikołaj Bojańczyk , Shuffle Expressions and Words with Nested Data, Lecture Notes in Computer Science, 2007. See in PBN
Mikołaj Bojańczyk , Two-way unary temporal logic over trees, 2007. See in PBN

2006

Mikołaj Bojańczyk , Thomas Colcombet, Bounds in w-Regularity, 2006. See in PBN
Mikołaj Bojańczyk , Mathias Samuelides, Thomas Schwentick, Luc Segoufin, Expressive Power of Pebble Automata, Lecture Notes in Computer Science, 2006. See in PBN
Mikołaj Bojańczyk , Thomas Colcombet, Tree-walking automata cannot be determinized, Theoretical Computer Science, 2006. See in PBN
Mikołaj Bojańczyk , Claire David, Anca Muscholl, Thomas Schwentick, Luc Segoufin, Two-variable logic on data trees and XML reasoning, 2006. See in PBN
Mikołaj Bojańczyk , Claire David, Anca Muscholl, Thomas Schwentick, Luc Segoufin, Two-Variable Logic on Words with Data, 2006. See in PBN

2005

Mikołaj Bojańczyk , Thomas Colcombet, Tree-walking automata do not recognize all regular languages, SYMPOSIUM ON THEORY OF COMPUTING, 2005. See in PBN