Zobrazeno 1 - 10
of 21
pro vyhledávání: '"Eryk Kopczynski"'
Autor:
Eryk Kopczynski, Tony Tan
Publikováno v:
Logical Methods in Computer Science, Vol Volume 14, Issue 2 (2018)
The spectrum of a first-order sentence is the set of the cardinalities of its finite models. In this paper, we consider the spectra of sentences over binary relations that use at least three variables. We show that for every such sentence $\Phi$, the
Externí odkaz:
https://doaj.org/article/9fde4781a7974e698a098abfc113e44c
Autor:
Eryk Kopczynski
Publikováno v:
Logical Methods in Computer Science, Vol Volume 11, Issue 1 (2015)
We consider commutative regular and context-free grammars, or, in other words, Parikh images of regular and context-free languages. By using linear algebra and a branching analog of the classic Euler theorem, we show that, under an assumption that th
Externí odkaz:
https://doaj.org/article/016d7b1557a445d99fb75536680ea714
Publikováno v:
Logical Methods in Computer Science, Vol Volume 9, Issue 4 (2013)
Motivated by the quest for a logic for PTIME and recent insights that the descriptive complexity of problems from linear algebra is a crucial aspect of this problem, we study the solvability of linear equation systems over finite groups and rings fro
Externí odkaz:
https://doaj.org/article/3b3c33cc1b6b4f09b1547805e9f47c12
Autor:
Eryk Kopczynski
Publikováno v:
Fundamenta Informaticae. 176:129-138
We construct a formula $\phi$ which axiomatizes non-narrow rectangular grids without using any binary relations other than the grid neighborship relations. As a corollary, we prove that a set $A \subseteq \mathbb{N}$ is a spectrum of a formula which
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6e5e2270a09552c900360f090082f8de
https://doi.org/10.3233/fi-2020-1966
https://doi.org/10.3233/fi-2020-1966
Autor:
Eryk Kopczynski
Publikováno v:
Fundamenta Informaticae. 152:323-339
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::d86b8fb2dffb57981161abc7293a9337
https://doi.org/10.3233/fi-2017-1523
https://doi.org/10.3233/fi-2017-1523
Publikováno v:
Fundamenta Informaticae. 140:123-127
We consider sequences of vectors from N d . Each coordinate of a vector can be reset or incremented by1 with respect to the same coordinate of the preceding vector. We give an example of non-dominating sequence, like in Dickson's Lemma, of lengt h 2
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e6ebc76dad700c8d0bf48e94b5ca481f
https://doi.org/10.3233/fi-2015-1247
https://doi.org/10.3233/fi-2015-1247
Publikováno v:
IJCAI
Scopus-Elsevier
Scopus-Elsevier
Gossip protocols deal with a group of communicating agents, each holding a private information, and aim at arriving at a situation in which all the agents know each other secrets. Distributed epistemic gossip protocols are particularly simple distrib
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::48739745300a9a9c56b7626a0fbd74ed
https://doi.org/10.24963/ijcai.2017/106
https://doi.org/10.24963/ijcai.2017/106
Autor:
Eryk Kopczynski
Publikováno v:
LICS
Context free languages allow one to express data with hierarchical structure, at the cost of losing some of the useful properties of languages recognized by finite automata on words. However, it is possible to restore some of these properties by maki
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::49b1d60287a1999a3c94e8f293159ab2
https://doi.org/10.1145/2933575.2933579
https://doi.org/10.1145/2933575.2933579
Publikováno v:
Combinatorica. 32:85-110
We study the problem of acute triangulations of convex polyhedra and the space ℝ n . Here an acute triangulation is a triangulation into simplices whose dihedral angles are acute. We prove that acute triangulations of the n-cube do not exist for n
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::05ccf1976217f7e921ffc80298da74dc
https://doi.org/10.1007/s00493-012-2691-2
https://doi.org/10.1007/s00493-012-2691-2
Publikováno v:
LICS
First-order definable structures with atoms are infinite, but exhibit enough symmetry to be effectively manipulated. We study Constraint Satisfaction Problems (CSPs) where both the instance and the template are definable structures with atoms. As an
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::3769db47d127d61db482c8e5fd7ba90a
https://doi.org/10.1109/lics.2015.51
https://doi.org/10.1109/lics.2015.51