The Experts below are selected from a list of 26100 Experts worldwide ranked by ideXlab platform

Emanuel Kieronski - One of the best experts on this subject based on the ideXlab platform.

  • LICS - Unary negation fragment with equivalence relations has the Finite Model Property
    Proceedings of the 33rd Annual ACM IEEE Symposium on Logic in Computer Science, 2018
    Co-Authors: Daniel Danielski, Emanuel Kieronski
    Abstract:

    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 show that this extension has the Finite Model Property. More specifically, we show that every satisfiable formula has a Model of at most doubly exponential size. We argue that the satisfiability (= Finite satisfiability) problem for this logic is 2-ExpTime-complete. We also transfer our results to a restricted variant of the guarded negation fragment with equivalence relations.

  • Unary negation fragment with equivalence relations has the Finite Model Property
    arXiv: Logic in Computer Science, 2018
    Co-Authors: Daniel Danielski, Emanuel Kieronski
    Abstract:

    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 show that this extension has the Finite Model Property. More specifically, we show that every satisfiable formula has a Model of at most doubly exponential size. We argue that the satisfiability (= Finite satisfiability) problem for this logic is TwoExpTime-complete. We also transfer our results to a restricted variant of the guarded negation fragment with equivalence relations.

  • small substructures and decidability issues for first order logic with two variables
    Journal of Symbolic Logic, 2012
    Co-Authors: Emanuel Kieronski, Martin Otto
    Abstract:

    We study first-order logic with two variables FO 2 and establish a small substructure Property. Similar to the small Model Property for FO 2 we obtain an exponential size bound on embedded substructures, relative to a fixed surrounding structure that may be inFinite. We apply this technique to analyse the satisfiability problem for FO 2 under constraints that require several binary relations to be interpreted as equivalence relations. With a single equivalence relation, FO 2 has the Finite Model Property and is complete for non-deterministic exponential time, just as for plain FO 2 . With two equivalence relations, FO 2 does not have the Finite Model Property, but is shown to be decidable via a construction of regular Models that admit Finite descriptions even though they may necessarily be inFinite. For three or more equivalence relations, FO 2 is undecidable.

  • LPAR - On Finite satisfiability of the guarded fragment with equivalence or transitive guards
    Logic for Programming Artificial Intelligence and Reasoning, 1
    Co-Authors: Emanuel Kieronski, Lidia Tendera
    Abstract:

    The guarded fragment of first-order logic, GF, enjoys the Finite Model Property, so the satisfiability and the Finite satisfiability problems coincide. We are concerned with two extensions of the two-variable guarded fragment that do not possess the Finite Model Property, namely, GF2 with equivalence and GF2 with transitive guards. We prove that in both cases every Finitely satisfiable formula has a Model of at most double exponential size w.r.t. its length. To obtain the result we invent a strategy of building Finite Models that are formed from a number of multidimensional grids placed over a cylindrical surface. The construction yields a 2NEXPTIME-upper bound on the complexity of the Finite satisfiability problem for these fragments. For the case with equivalence guards we improve the bound to 2EXPTIME.

  • LICS - Small substructures and decidability issues for first-order logic with two variables
    20th Annual IEEE Symposium on Logic in Computer Science (LICS' 05), 1
    Co-Authors: Emanuel Kieronski, Martin Otto
    Abstract:

    We study first-order logic with two variables FO/sup 2/ and establish a small substructure Property. Similar to the small Model Property for FO/sup 2/ we obtain an exponential size bound on embedded substructures, relative to a fixed surrounding structure that may be inFinite. We apply this technique to analyse the satisfiability problem for FO/sup 2/ under constraints that require several binary relations to be interpreted as equivalence relations. With a single equivalence relation, FO/sup 2/ has the Finite Model Property and is complete for non-deterministic exponential time, just as for plain FO/sup 2/. With two equivalence relations, FO/sup 2/ does not have the Finite Model Property, but is shown to be decidable via a construction of regular Models that admit Finite descriptions even though they may necessarily be inFinite. For three or more equivalence relations, FO/sup 2/ is undecidable.

Tommaso Flaminio - One of the best experts on this subject based on the ideXlab platform.

  • on standard completeness and Finite Model Property for a probabilistic logic on łukasiewicz events
    International Journal of Approximate Reasoning, 2021
    Co-Authors: Tommaso Flaminio
    Abstract:

    Abstract The probabilistic logic FP ( Ł , Ł ) was axiomatized with the aim of presenting a formal setting for reasoning about the probability of inFinite-valued Łukasiewicz events. Besides several attempts, proving that axiomatic system to be complete with respect to a class of standard Models, remained an open problem since the first paper on FP ( Ł , Ł ) was published in 2007. In this article we give a solution to it. In particular we introduce two semantics for that probabilistic system: a first one based on Łukasiewicz states and a second one based on regular Borel measures and we prove that FP ( Ł , Ł ) is complete with respect to both these classes of Models. Further, we will show that the Finite Model Property holds for FP ( Ł , Ł ) .

Gert Smolka - One of the best experts on this subject based on the ideXlab platform.

Agi Kurucz - One of the best experts on this subject based on the ideXlab platform.

  • bimodal logics with a weakly connected component without the Finite Model Property
    Notre Dame Journal of Formal Logic, 2017
    Co-Authors: Agi Kurucz
    Abstract:

    There are two known general results on the Finite Model Property (fmp) of commutators [L0, L1] (bimodal logics with commuting and confluent modalities). If L is Finitely axiomatisable by modal formulas having universal Horn first-order correspondents, then both [L,K] and [L,S5] are determined by classes of frames that admit filtration, and so have the fmp. On the negative side, if both L0 and L1 are determined by transitive frames and have frames of arbitrarily large depth, then [L0, L1] does not have the fmp. In this paper we show that commutators with a ‘weakly connected’ component often lack the fmp. Our results imply that the above positive result does not generalise to universally axiomatisable component logics, and even commutators without ‘transitive’ components such as [K3,K] can lack the fmp. We also generalise the above negative result to cases where one of the component logics has frames of depth one only, such as [S4.3,S5] and the decidable product logic S4.3×S5. We also show cases when already half of commutativity is enough to force inFinite frames.

  • Bimodal logics with a `weakly connected' component without the Finite Model Property
    Notre Dame Journal of Formal Logic, 2017
    Co-Authors: Agi Kurucz
    Abstract:

    There are two known general results on the Finite Model Property (fmp) of commutators [L,L'] (bimodal logics with commuting and confluent modalities). If L is Finitely axiomatisable by modal formulas having universal Horn first-order correspondents, then both [L,K] and [L,S5] are determined by classes of frames that admit filtration, and so have the fmp. On the negative side, if both L and L' are determined by transitive frames and have frames of arbitrarily large depth, then [L,L'] does not have the fmp. In this paper we show that commutators with a `weakly connected' component often lack the fmp. Our results imply that the above positive result does not generalise to universally axiomatisable component logics, and even commutators without `transitive' components such as [K.3,K] can lack the fmp. We also generalise the above negative result to cases where one of the component logics has frames of depth one only, such as [S4.3,S5] and the decidable product logic S4.3xS5. We also show cases when already half of commutativity is enough to force inFinite frames.

  • products of modal logics with diagonal constant lacking the Finite Model Property
    Frontiers of Combining Systems, 2009
    Co-Authors: Agi Kurucz
    Abstract:

    Two-dimensional products of modal logics having at least one 'non-transitive' component, such as K × K, K × K4, and K × S5, are often known to be decidable and have the Finite Model Property. Here we show that by adding the diagonal constant to the language this might change: one can have formulas that are only satisfiable in inFinite 'abstract' Models for these logics.

  • FroCoS - Products of modal logics with diagonal constant lacking the Finite Model Property
    Frontiers of Combining Systems, 2009
    Co-Authors: Agi Kurucz
    Abstract:

    Two-dimensional products of modal logics having at least one 'non-transitive' component, such as K × K, K × K4, and K × S5, are often known to be decidable and have the Finite Model Property. Here we show that by adding the diagonal constant to the language this might change: one can have formulas that are only satisfiable in inFinite 'abstract' Models for these logics.

Martin Otto - One of the best experts on this subject based on the ideXlab platform.

  • small substructures and decidability issues for first order logic with two variables
    Journal of Symbolic Logic, 2012
    Co-Authors: Emanuel Kieronski, Martin Otto
    Abstract:

    We study first-order logic with two variables FO 2 and establish a small substructure Property. Similar to the small Model Property for FO 2 we obtain an exponential size bound on embedded substructures, relative to a fixed surrounding structure that may be inFinite. We apply this technique to analyse the satisfiability problem for FO 2 under constraints that require several binary relations to be interpreted as equivalence relations. With a single equivalence relation, FO 2 has the Finite Model Property and is complete for non-deterministic exponential time, just as for plain FO 2 . With two equivalence relations, FO 2 does not have the Finite Model Property, but is shown to be decidable via a construction of regular Models that admit Finite descriptions even though they may necessarily be inFinite. For three or more equivalence relations, FO 2 is undecidable.

  • LICS - Small substructures and decidability issues for first-order logic with two variables
    20th Annual IEEE Symposium on Logic in Computer Science (LICS' 05), 1
    Co-Authors: Emanuel Kieronski, Martin Otto
    Abstract:

    We study first-order logic with two variables FO/sup 2/ and establish a small substructure Property. Similar to the small Model Property for FO/sup 2/ we obtain an exponential size bound on embedded substructures, relative to a fixed surrounding structure that may be inFinite. We apply this technique to analyse the satisfiability problem for FO/sup 2/ under constraints that require several binary relations to be interpreted as equivalence relations. With a single equivalence relation, FO/sup 2/ has the Finite Model Property and is complete for non-deterministic exponential time, just as for plain FO/sup 2/. With two equivalence relations, FO/sup 2/ does not have the Finite Model Property, but is shown to be decidable via a construction of regular Models that admit Finite descriptions even though they may necessarily be inFinite. For three or more equivalence relations, FO/sup 2/ is undecidable.