Mikolaj Bojanczyk

CoRR, 2020

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

[BibT_eX]

[DOI]

Janusz Schmude

Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, 2020

Extensions of ω-Regular Languages.

[BibT_eX]

[DOI]

Proceedings of the LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, 2020

First-order tree-to-tree functions.

[BibT_eX]

[DOI]

Amina Doumane

Proceedings of the LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, 2020

Single-Use Automata and Transducers for Infinite Alphabets.

[BibT_eX]

[DOI]

Rafal Stefanski

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

2019

The Hilbert method for transducer equivalence.

[BibT_eX]

[DOI]

ACM SIGLOG News, 2019

A non-regular language of infinite trees that is recognizable by a sort-wise finite algebra.

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2019

Regular tree languages in low levels of the Wadge Hierarchy.

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2019

EATCS Fellows 2020 - Call for Nominations.

[BibT_eX]

[DOI]

Bull. EATCS, 2019

Single use register automata for data words.

[BibT_eX]

[DOI]

Rafal Stefanski

CoRR, 2019

MSO+nabla is undecidable.

[BibT_eX]

[DOI]

Edon Kelmendi

CoRR, 2019

MSO+∇ is undecidable.

[BibT_eX]

[DOI]

Edon Kelmendi

Proceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science, 2019

String-to-String Interpretations With Polynomial-Size Output.

[BibT_eX]

[DOI]

Sandra Kiefer

Nathan Lhote

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018

Polyregular Functions.

[BibT_eX]

[DOI]

CoRR, 2018

Undecidability of MSO+"ultimately periodic".

[BibT_eX]

[DOI]

CoRR, 2018

Two monads for graphs.

[BibT_eX]

[DOI]

CoRR, 2018

A non-regular language of infinite trees that is recognizable by a finite algebra.

[BibT_eX]

[DOI]

CoRR, 2018

On computability and tractability for infinite sets.

[BibT_eX]

[DOI]

Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, 2018

Regular and First-Order List Functions.

[BibT_eX]

[DOI]

Shankara Narayanan Krishna

Laure Daviaud

Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, 2018

2017

Boundedness in languages of infinite words.

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2017

It is Undecidable if Two Regular Tree Languages can be Separated by a Deterministic Tree-walking Automaton.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2017

Some connections between universal algebra and logics for trees.

[BibT_eX]

[DOI]

Henryk Michalewski

CoRR, 2017

Emptiness of Zero Automata Is Decidable.

[BibT_eX]

[DOI]

Hugo Gimbert

Edon Kelmendi

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Which Classes of Origin Graphs Are Generated by Transducers.

[BibT_eX]

[DOI]

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Orbit-Finite Sets and Their Algorithms (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

Automata column.

[BibT_eX]

[DOI]

ACM SIGLOG News, 2016

Regular Languages of Thin Trees.

[BibT_eX]

[DOI]

Tomasz Idziaszek

Theory Comput. Syst., 2016

On the Regular Emptiness Problem of Subzero Automata.

[BibT_eX]

[DOI]

Henryk Michalewski

Matteo Mio

Proceedings of the Proceedings 9th Interaction and Concurrency Experience, 2016

The MSO+U Theory of (N, <) Is Undecidable.

[BibT_eX]

[DOI]

Pawel Parys

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

Decidable Extensions of MSO.

[BibT_eX]

[DOI]

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

Definability equals recognizability for graphs of bounded treewidth.

[BibT_eX]

[DOI]

Michal Pilipczuk

Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, 2016

Thin MSO with a Probabilistic Path Quantifier.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

McNaughton's theorem.

[BibT_eX]

[DOI]

ACM SIGLOG News, 2015

Circuits, Logic and Games (Dagstuhl Seminar 15401).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2015

Star Height via Games.

[BibT_eX]

[DOI]

Proceedings of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science, 2015

Containment of Monadic Datalog Programs via Bounded Clique-Width.

[BibT_eX]

[DOI]

Filip Murlak

Adam Witkowski

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Recognisable Languages over Monads.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory - 19th International Conference, 2015

2014

Rigidity is undecidable.

[BibT_eX]

[DOI]

Stanislaw Szawiel

Marek W. Zawadowski

Math. Struct. Comput. Sci., 2014

Automata theory in nominal sets.

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2014

Decomposition Theorems and Model-Checking for the Modal $μ$-Calculus.

[BibT_eX]

[DOI]

Christoph Dittmann

Stephan Kreutzer

CoRR, 2014

On the Decidability of MSO+U on Infinite Trees.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Weak MSO+U with Path Quantifiers over Infinite Trees.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Transducers with Origin Information.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Decomposition theorems and model-checking for the modal <i>μ</i>-calculus.

[BibT_eX]

[DOI]

Christoph Dittmann

Stephan Kreutzer

Proceedings of the 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), 2014

2013

Nominal Monoids.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2013

Solutions in XML data exchange.

[BibT_eX]

[DOI]

Leszek Aleksander Kolodziejczyk

Filip Murlak

J. Comput. Syst. Sci., 2013

Nominal Computation Theory (Dagstuhl Seminar 13422).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2013

Modelling Infinite Structures with Atoms.

[BibT_eX]

[DOI]

Proceedings of the Logic, Language, Information, and Computation, 2013

Verification of database-driven systems via amalgamation.

[BibT_eX]

[DOI]

Luc Segoufin

Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2013

Turing Machines with Atoms.

[BibT_eX]

[DOI]

Proceedings of the 28th Annual ACM/IEEE Symposium on Logic in Computer Science, 2013

Automata and Algebras for Infinite Words and Trees.

[BibT_eX]

[DOI]

Proceedings of the Algebra and Coalgebra in Computer Science, 2013

2012

Algorithms for regular languages that use algebra.

[BibT_eX]

[DOI]

SIGMOD Rec., 2012

Finite satisfiability for guarded fixpoint logic.

[BibT_eX]

[DOI]

Vince Bárány

Inf. Process. Lett., 2012

Minimization of semilinear automata

[BibT_eX]

[DOI]

CoRR, 2012

Wreath Products of Forest Algebras, with Applications to Tree Logics

[BibT_eX]

[DOI]

Howard Straubing

Igor Walukiewicz

Log. Methods Comput. Sci., 2012

Piecewise testable tree languages

[BibT_eX]

[DOI]

Luc Segoufin

Howard Straubing

Log. Methods Comput. Sci., 2012

An extension of data automata that captures XPath

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2012

Weak MSO+U over infinite trees.

[BibT_eX]

[DOI]

Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

Fraenkel-Mostowski Sets with Non-homogeneous Atoms.

[BibT_eX]

[DOI]

Proceedings of the Reachability Problems - 6th International Workshop, 2012

Towards nominal computation.

[BibT_eX]

[DOI]

Proceedings of the 39th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 2012

Toward Model Theory with Data Values.

[BibT_eX]

[DOI]

Thomas Place

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Regular Languages of Infinite Trees That Are Boolean Combinations of Open Sets.

[BibT_eX]

[DOI]

Thomas Place

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

A Machine-Independent Characterization of Timed Languages.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Imperative Programming in Sets with Atoms.

[BibT_eX]

[DOI]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2012

Decidable classes of documents for XPath.

[BibT_eX]

[DOI]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2012

2011

Two-variable logic on data words.

[BibT_eX]

[DOI]

ACM Trans. Comput. Log., 2011

Weak MSO with the Unbounding Quantifier.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2011

Foreword.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2011

XPath evaluation in linear time.

[BibT_eX]

[DOI]

Pawel Parys

J. ACM, 2011

Data Monoids.

[BibT_eX]

[DOI]

Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

Efficient evaluation for a temporal logic on changing XML documents.

[BibT_eX]

[DOI]

Diego Figueira

Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2011

Automata with Group Actions.

[BibT_eX]

[DOI]

Proceedings of the 26th Annual IEEE Symposium on Logic in Computer Science, 2011

2010

On the Borel Complexity of MSO Definable Sets of Branches.

[BibT_eX]

[DOI]

Damian Niwinski

Alexander Rabinovich

Adam Radziwonczyk-Syta

Fundam. Informaticae, 2010

Tree Languages Defined in First-Order Logic with One Quantifier Alternation

[BibT_eX]

[DOI]

Luc Segoufin

Log. Methods Comput. Sci., 2010

Beyond omega-Regular Languages.

[BibT_eX]

[DOI]

Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

Automata for Data Words and Data Trees.

[BibT_eX]

[DOI]

Proceedings of the 21st International Conference on Rewriting Techniques and Applications, 2010

Efficient Evaluation of Nondeterministic Automata Using Factorization Forests.

[BibT_eX]

[DOI]

Pawel Parys

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

2009

Two-variable logic on data trees and XML reasoning.

[BibT_eX]

[DOI]

J. ACM, 2009

Two-Way Unary Temporal Logic over Trees

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2009

Deterministic Automata and Extensions of Weak MSO.

[BibT_eX]

[DOI]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2009

Factorization Forests.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 13th International Conference, 2009

Algebra for Tree Languages.

[BibT_eX]

[DOI]

Proceedings of the Computer Science Logic, 23rd international Workshop, 2009

Algebra for Infinite Forests with an Application to the Temporal Logic EF.

[BibT_eX]

[DOI]

Tomasz Idziaszek

Proceedings of the CONCUR 2009 - Concurrency Theory, 20th International Conference, 2009

2008

Tree-Walking Automata Do Not Recognize All Regular Languages.

[BibT_eX]

[DOI]

SIAM J. Comput., 2008

Effective characterizations of tree logics.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2008

Tree-Walking Automata.

[BibT_eX]

[DOI]

Proceedings of the Language and Automata Theory and Applications, 2008

The Common Fragment of ACTL and LTL.

[BibT_eX]

[DOI]

Proceedings of the Foundations of Software Science and Computational Structures, 2008

Forest algebras.

[BibT_eX]

Igor Walukiewicz

Proceedings of the Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas]., 2008

2007

A new algorithm for testing if a regular language is locally threshold testable.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2007

Reachability in Unions of Commutative Rewriting Systems Is Decidable.

[BibT_eX]

[DOI]

Piotr Hoffman

Proceedings of the STACS 2007, 2007

Shuffle Expressions and Words with Nested Data.

[BibT_eX]

[DOI]

Henrik Björklund

Proceedings of the Mathematical Foundations of Computer Science 2007, 2007

Bounded Depth Data Trees.

[BibT_eX]

[DOI]

Henrik Björklund

Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

Forest Expressions.

[BibT_eX]

[DOI]

Proceedings of the Computer Science Logic, 21st International Workshop, 2007

2006

Characterizing EF and EX tree logics.

[BibT_eX]

[DOI]

Igor Walukiewicz

Theor. Comput. Sci., 2006

Tree-walking automata cannot be determinized.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2006

Two-variable logic on data trees and XML reasoning.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2006

Two-Variable Logic on Words with Data.

[BibT_eX]

[DOI]

Proceedings of the 21th IEEE Symposium on Logic in Computer Science (LICS 2006), 2006

Bounds in w-Regularity.

[BibT_eX]

[DOI]

Proceedings of the 21th IEEE Symposium on Logic in Computer Science (LICS 2006), 2006

Expressive Power of Pebble Automata.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

2004

A Bounding Quantifier.

[BibT_eX]

[DOI]

Proceedings of the Computer Science Logic, 18th International Workshop, 2004

2003

The finite graph problem for two-way alternating automata.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2003

1-Bounded TWA Cannot Be Determinized.

[BibT_eX]

[DOI]

Proceedings of the FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science, 2003

2002

Two-Way Alternating Automata and Finite Models.

[BibT_eX]

[DOI]