Výsledky vyhledávání - "Szymon Toruńczyk"

Akademický článek

Publikováno v: Logical Methods in Computer Science, Vol Volume 18, Issue 1 (2022)

We introduce a model of register automata over infinite trees with extrema constraints. Such an automaton can store elements of a linearly ordered domain in its registers, and can compare those values to the suprema and infima of register values in s

Externí odkaz: https://doaj.org/article/260cffaa6e0248c8935a890171f7cb28

Zobrazit plný text záznamu

Akademický článek

Definable isomorphism problem

Autor: Khadijeh Keshvardoost, Bartek Klin, Sławomir Lasota, Joanna Ochremiak, Szymon Toruńczyk

Publikováno v: Logical Methods in Computer Science, Vol Volume 15, Issue 4 (2019)

We investigate the isomorphism problem in the setting of definable sets (equivalent to sets with atoms): given two definable relational structures, are they related by a definable isomorphism? Under mild assumptions on the underlying structure of ato

Externí odkaz: https://doaj.org/article/bdf04fdf9e0b498e98dd319f487e9f0a

Zobrazit plný text záznamu

Model Checking on Interpretations of Classes of Bounded Local Cliquewidth

Autor: Édouard Bonnet, Jan Dreier, Jakub Gajarský, Stephan Kreutzer, Nikolas Mählmann, Pierre Simon, Szymon Toruńczyk

Publikováno v: Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science
37th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2022

We present a fixed-parameter tractable algorithm for first-order model checking on interpretations of graph classes with bounded local cliquewidth. Notably, this includes interpretations of planar graphs, and more generally, of classes of bounded gen

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::7ecb50be125f488864d484e7d60e4115
https://doi.org/10.1145/3531130.3533367

Zobrazit plný text záznamu

Stable graphs of bounded twin-width

Autor: Jakub Gajarský, Michał Pilipczuk, Szymon Toruńczyk

Publikováno v: Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science
37th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2022

We prove that every class of graphs $\mathscr C$ that is monadically stable and has bounded twin-width can be transduced from some class with bounded sparse twin-width. This generalizes analogous results for classes of bounded linear cliquewidth and

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9e262b55418974a63dda5fea04e57c53
https://doi.org/10.1145/3531130.3533356

Zobrazit plný text záznamu

Treelike decompositions for transductions of sparse graphs

Autor: Jan Dreier, Jakub Gajarský, Sandra Kiefer, Michał Pilipczuk, Szymon Toruńczyk

Publikováno v: Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science
37th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2022

We give new decomposition theorems for classes of graphs that can be transduced in first-order logic from classes of sparse graphs -- more precisely, from classes of bounded expansion and from nowhere dense classes. In both cases, the decomposition t

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::92f064f2d63335e82fb168700d2d3baa
http://arxiv.org/abs/2201.11082

Zobrazit plný text záznamu

Autor: Thomas Zeume, Szymon Toruńczyk

Publikováno v: LICS

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0151ab59def1950f4b5ecca8f63f5f4a

Zobrazit plný text záznamu

Nondeterministic and co-Nondeterministic Implies Deterministic, for Data Languages

Autor: Bartek Klin, Szymon Toruńczyk, Sławomir Lasota

Publikováno v: FoSSaCS
Lecture Notes in Computer Science
Lecture Notes in Computer Science-Foundations of Software Science and Computation Structures
Lecture Notes in Computer Science ISBN: 9783030719944

We prove that if a data language and its complement are both recognized by nondeterministic register automata (without guessing), then they are also recognized by deterministic ones.

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::749eac62388465b257173bebf1d5390e

Zobrazit plný text záznamu

Uniformisations of Regular Relations Over Bi-Infinite Words

Autor: Grzegorz Fabiański, Szymon Toruńczyk, Michał Skrzypczak

Publikováno v: LICS
Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science

We consider the problem of deciding whether a given mso-definable relation over bi-infinite words contains an mso-definable function with the same domain. We prove that this problem is decidable. There are two obstacles to the existence of such unifo

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4990271da1fb8fbc70afd78bdcdc69b8
https://doi.org/10.1145/3373718.3394782

Zobrazit plný text záznamu

Aggregate Queries on Sparse Databases

Autor: Szymon Toruńczyk

Publikováno v: PODS

We propose an algebraic framework for studying efficient algorithms for query evaluation, aggregation, enumeration, and maintenance under updates, on sparse databases. Our framework allows to treat those problems in a unified way, by considering vari

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0f01cf95dd913e091408f53e9f07a918

Zobrazit plný text záznamu

On computability and tractability for infinite sets

Autor: Szymon Toruńczyk, Mikołaj Bojańczyk

Publikováno v: LICS

We propose a definition for computable functions on hereditarily definable sets. Such sets are possibly infinite data structures that can be defined using a fixed underlying logical structure, such as (N, =). We show that, under suitable assumptions

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::6210acef283f8ed48da742c4ee5cfae9
https://doi.org/10.1145/3209108.3209190

Zobrazit plný text záznamu

Vyhledávací nástroje:

Upřesnit hledání