You are not logged in | Log in

Mikołaj Bojańczyk

Number of publications: 108

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, 51st ACM SIGPLAN Symposium on Principles of Programming Languages, London, the United Kingdom of Great Britain and Northern Ireland, 14 January 2024 - 20 January 2024, 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, 18 (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

Mikołaj Bojańczyk , Sławomir Lasota , A Machine-Independent Characterization of Timed Languages, ICALP 2012, 2012. See in PBN
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