5 citations · 12 across the 8 of their papers we have counts for
10 papers
Alternating Quantifiers in Uniform One-Dimensional Fragments with an Excursion into Three-Variable Logic
Oskar Fiuk, Emanuel Kieronski
The uniform one-dimensional fragment of first-order logic was introduced a few years ago as a generalization of the two-variable fragment to contexts involving relations of arity g…
A Uniform One-Dimensional Fragment with Alternation of Quantifiers
Emanuel Kieroński
The uniform one-dimensional fragment of first-order logic was introduced a few years ago as a generalization of the two-variable fragment of first-order logic to contexts involving…
One-Dimensional Fragment over Words and Trees
Emanuel Kieronski, Antti Kuusisto
One-dimensional fragment of first-order logic is obtained by restricting quantification to blocks of existential (universal) quantifiers that leave at most one variable free. We in…
One-dimensional guarded fragments
Emanuel Kieronski
We call a first-order formula one-dimensional if its every maximal block of existential (universal) quantifiers leaves at most one variable free. We consider the one-dimensional re…
Finite Satisfiability of Unary Negation Fragment with Transitivity
Daniel Danielski, Emanuel Kieronski
We show that the finite satisfiability problem for the unary negation fragment with arbitrary number of transitive relations is decidable and 2-ExpTime-complete. Our result actuall…
Unary negation fragment with equivalence relations has the finite model property
Daniel Danielski, Emanuel Kieronski
We consider an extension of the unary negation fragment of first-order logic in which arbitrarily many binary symbols may be required to be interpreted as equivalence relations. We…
Extending Two-Variable Logic on Trees
Bartosz Bednarczyk, Witold Charatonik, Emanuel Kieroński
The finite satisfiability problem for the two-variable fragment of first-order logic interpreted over trees was recently shown to be ExpSpace-complete. We consider two extensions o…
Finite Satisfiability of the Two-Variable Guarded Fragment with Transitive Guards and Related Variants
Emanuel Kieronski, Lidia Tendera
We consider extensions of the two-variable guarded fragment, GF2, where distinguished binary predicates that occur only in guards are required to be interpreted in a special way (a…
Complexity and Expressivity of Uniform One-Dimensional Fragment with Equality
Emanuel Kieroński, Antti Kuusisto
Uniform one-dimensional fragment UF1^= is a formalism obtained from first-order logic by limiting quantification to applications of blocks of existential (universal) quantifiers su…
Satisfiability of the Two-Variable Fragment of First-Order Logic over Trees
Witold Charatonik, Emanuel Kieroński, Filip Mazowiecki
We consider the satisfiability problem for the two-variable fragment of first-order logic over finite unranked trees. We work with signatures consisting of some unary predicates an…