Ändra sökning
Avgränsa sökresultatet
1 - 9 av 9
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Träffar per sida
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sortering
  • Standard (Relevans)
  • Författare A-Ö
  • Författare Ö-A
  • Titel A-Ö
  • Titel Ö-A
  • Publikationstyp A-Ö
  • Publikationstyp Ö-A
  • Äldst först
  • Nyast först
  • Skapad (Äldst först)
  • Skapad (Nyast först)
  • Senast uppdaterad (Äldst först)
  • Senast uppdaterad (Nyast först)
  • Disputationsdatum (tidigaste först)
  • Disputationsdatum (senaste först)
  • Standard (Relevans)
  • Författare A-Ö
  • Författare Ö-A
  • Titel A-Ö
  • Titel Ö-A
  • Publikationstyp A-Ö
  • Publikationstyp Ö-A
  • Äldst först
  • Nyast först
  • Skapad (Äldst först)
  • Skapad (Nyast först)
  • Senast uppdaterad (Äldst först)
  • Senast uppdaterad (Nyast först)
  • Disputationsdatum (tidigaste först)
  • Disputationsdatum (senaste först)
Markera
Maxantalet träffar du kan exportera från sökgränssnittet är 250. Vid större uttag använd dig av utsökningar.
  • 1.
    Enqvist, Sebastian
    Stockholms universitet, Humanistiska fakulteten, Filosofiska institutionen.
    Flat modal fixpoint logics with the converse modality2018Ingår i: Journal of logic and computation (Print), ISSN 0955-792X, E-ISSN 1465-363X, Vol. 28, nr 6, s. 1065-1097Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We prove a generic completeness result for a class of modal fixpoint logics corresponding to flat fragments of the two-way mu-calculus, with the restriction that the fixpoint connectives involved must be disjunctive formulas. This extends earlier work by Santocanale and Venema. We observe that Santocanale and Venema's proof that least fixpoints in the free algebras of flat fixpoint logics are constructive, using finitary adjoints, no longer works when the converse modality is introduced. Instead, our completeness proof directly constructs a model for a consistent formula, using the induction rule in a way that is similar to the standard completeness proof for propositional dynamic logic. This approach is combined with the concept of a focus, which has previously been used in tableau-based reasoning for modal fixpoint logics, and the use of networks, which is a well-known tool for proving completeness of modal logics.

  • 2.
    Enqvist, Sebastian
    et al.
    Stockholms universitet, Humanistiska fakulteten, Filosofiska institutionen. University of Amsterdam, The Netherlands.
    Seifan, Fatemeh
    Venema, Yde
    An expressive completeness theorem for coalgebraic modal mu-calculi2017Ingår i: Logical Methods in Computer Science, ISSN 1860-5974, E-ISSN 1860-5974, Vol. 13, nr 2, artikel-id 14Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    Generalizing standard monadic second-order logic for Kripke models, we introduce monadic second-order logic interpreted over coalgebras for an arbitrary set functor. We then consider invariance under behavioral equivalence of MSO-formulas. More specifically, we investigate whether the coalgebraic mu-calculus is the bisimulation-invariant fragment of the monadic second-order language for a given functor. Using automata theoretic techniques and building on recent results by the third author, we show that in order to provide such a characterization result it suffices to find what we call an adequate uniform construction for the coalgebraic type functor. As direct applications of this result we obtain a partly new proof of the Janin-Walukiewicz Theorem for the modal mu-calculus, avoiding the use of syntactic normal forms, and bisimulation invariance results for the bag functor (graded modal logic) and all exponential polynomial functors (including the game functor). As a more involved application, involving additional non-trivial ideas, we also derive a characterization theorem for the monotone modal mu-calculus, with respect to a natural monadic second-order language for monotone neighborhood models.

  • 3.
    Enqvist, Sebastian
    et al.
    Stockholms universitet, Humanistiska fakulteten, Filosofiska institutionen.
    Seifan, Fatemeh
    Venema, Yde
    Completeness for mu-calculi: A coalgebraic approach2019Ingår i: Annals of Pure and Applied Logic, ISSN 0168-0072, E-ISSN 1873-2461, Vol. 170, nr 5, s. 578-641Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We set up a generic framework for proving completeness results for variants of the modal mu-calculus, using tools from coalgebraic modal logic. We illustrate the method by proving two new completeness results: for the graded mu-calculus (which is equivalent to monadic second-order logic on the class of unranked tree models), and for the monotone modal mu-calculus. Besides these main applications, our result covers the Kozen-Walukiewicz completeness theorem for the standard modal mu-calculus, as well as the linear-time mu-calculus and modal fixpoint logics on ranked trees. Completeness of the linear time mu-calculus is known, but the proof we obtain here is different and places the result under a common roof with Walukiewicz' result. Our approach combines insights from the theory of automata operating on potentially infinite objects, with methods from the categorical framework of coalgebra as a general theory of state-based evolving systems. At the interface of these theories lies the notion of a coalgebraic modal one-step language. One of our main contributions here is the introduction of the novel concept of a disjunctive basis for a modal one-step language. Generalizing earlier work, our main general result states that in case a coalgebraic modal logic admits such a disjunctive basis, then soundness and completeness at the one-step level transfer to the level of the full coalgebraic modal mu-calculus.

  • 4.
    Enqvist, Sebastian
    et al.
    Stockholms universitet, Humanistiska fakulteten, Filosofiska institutionen.
    Sourabh, Sumit
    Bisimulations for coalgebras on Stone spaces2018Ingår i: Journal of logic and computation (Print), ISSN 0955-792X, E-ISSN 1465-363X, Vol. 28, nr 6, s. 991-1010Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We introduce and study bisimulations for coalgebras on Stone spaces (Kupke et al., 2004, Theoretical Computer Science, 327, 109-134), motivated by previous work on ultrafilter extensions for coalgebras (Kupke et al., 2005, Algebra and Coalgebra in Computer Science, 263-277), bisimulations for the Vietoris functor (Bezhanishvili et al., 2010, Journal of Logic and Computation, 20, 1017-1040) and building on an idea of Gorin and Schroder (2013, Algebra and Coalgebra in Computer Science, 8089, 253-266). We provide a condition under which our notion of bisimulation gives a sound and complete proof method for behavioural equivalence, and show that it generalizes Vietoris bisimulations. Our main technical result proves that the topological closure of any bisimulation between Stone coalgebras in our sense is still a bisimulation. This answers a question raised in Bezhanishvili et al. (2010, Journal of Logic and Computation, 20, 1017-1040), and also leads to a simpler proof of the main theorem in that paper, that the topological closure of a Kripke bisimulation is a Vietoris bisimulation. As a second application of our general bisimulation concept, we study neighbourhood bisimulations on descriptive frames for monotone modal logic as they were introduced in Hansen et al. (2009, Logical Methods in Computer Science, 5, 1-38). From our general results we derive that these are sound and complete for behavioural equivalence and that the topological closure of a neighbourhood bisimulation is still a neighbourhood bisimulation, in analogy with the main result in Bezhanishvili et al. (2010, Journal of Logic and Computation, 20, 1017-1040). Finally, we apply our result to bisimulations for Stone companions of set functors as defined in Kupke et al.

  • 5.
    Enqvist, Sebastian
    et al.
    Stockholms universitet, Humanistiska fakulteten, Filosofiska institutionen.
    Venema, Yde
    DISJUNCTIVE BASES: NORMAL FORMS AND MODEL THEORY FOR MODAL LOGICS2019Ingår i: Logical Methods in Computer Science, ISSN 1860-5974, E-ISSN 1860-5974, Vol. 15, nr 1, artikel-id 30Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We present the concept of a disjunctive basis as a generic framework for normal forms in modal logic based on coalgebra. Disjunctive bases were defined in previous work on completeness for modal fixpoint logics, where they played a central role in the proof of a generic completeness theorem for coalgebraic mu-calculi. Believing the concept has a much wider significance, here we investigate it more thoroughly in its own right. We show that the presence of a disjunctive basis at the one-step level entails a number of good properties for a coalgebraic mu-calculus, in particular, a simulation theorem showing that every alternating automaton can be transformed into an equivalent nondeterministic one. Based on this, we prove a Lyndon theorem for the full fixpoint logic, its fixpoint-free fragment and its one-step fragment, a Uniform Interpolation result, for both the full mu-calculus and its fixpoint-free fragment, and a Janin-Walukiewicz-style characterization theorem for the mu-calculus under slightly stronger assumptions. We also raise the questions, when a disjunctive basis exists, and how disjunctive bases arc related to Moss' coalgebraic nabla modalities. Nabla formulas provide disjunctive bases for many coalgebraic modal logics, but there are cases where disjunctive bases give useful normal forms even when nabla formulas fail to do so, our prime example being graded modal logic. We also show that disjunctive bases are preserved by forming sums, products and compositions of coalgebraic modal logics, providing tools for modular construction of modal logics admitting disjunctive bases. Finally, we consider the problem of giving a category-theoretic formulation of disjunctive bases, and provide a partial solution.

  • 6.
    Goranko, Valentin
    et al.
    Stockholms universitet, Humanistiska fakulteten, Filosofiska institutionen. University of Johannesburg, South Africa.
    Enqvist, Sebastian
    Stockholms universitet, Humanistiska fakulteten, Filosofiska institutionen.
    Socially Friendly and Group Protecting Coalition Logics2018Ingår i: Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2018) / [ed] Mehdi Dastani, Gita Sukthankar, Elisabeth André, Sven Koenig, The International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), 2018, s. 372-380Konferensbidrag (Refereegranskat)
    Abstract [en]

    We consider extensions of Coalition Logic (CL) which can express statements about inter-related powers of coalitions to achieve their respective goals. In particular, we introduce and study two new extensions of CL. One of them is the “Socially Friendly Coalition Logic” SFCL, which is also a multi-agent extension of the recently introduced “Instantial Neighborhood Logic” INL. SFCL can express the claim that a coalition has a collective strategy to guarantee achieving its explicitly stated goal while acting in a ‘socially friendly way’, by enabling the remaining agents to achieve other (again, explicitly stated) goals of their choice. The other new extension is the “Group Protecting Coalition Logic” GPCL which enables reasoning about entire coalitional goal assignments, in which every group of agents has its own specified goal. GPCL can express claims to the effect that there is an action profile of the grand coalition such that, by playing it, every sub-coalition of agents can guarantee satisfaction of its own private goal (and thus, protect its own interests) while acting towards achievement of the common goal of the grand coalition. For each of these logics, we discuss its expressiveness, introduce the respective notion of bisimulation and prove bisimulation invariance and Hennessy-Milner property. We then also present sound and complete axiomatic systems and prove decidability for both logics.

  • 7. van Benthem, Johan
    et al.
    Bezhanishvili, Nick
    Enqvist, Sebastian
    Stockholms universitet, Humanistiska fakulteten, Filosofiska institutionen.
    A New Game Equivalence and its Modal Logic2017Ingår i: Electronic Proceedings in Theoretical Computer Science, ISSN 2075-2180, E-ISSN 2075-2180, nr 251, s. 57-74Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We revisit the crucial issue of natural game equivalences, and semantics of game logics based on these. We present reasons for investigating finer concepts of game equivalence than equality of standard powers, though staying short of modal bisimulation. Concretely, we propose a more fine-grained notion of equality of 'basic powers' which record what players can force plus what they leave to others to do, a crucial feature of interaction. This notion is closer to game-theoretic strategic form, as we explain in detail, while remaining amenable to logical analysis. We determine the properties of basic powers via a new representation theorem, find a matching 'instantial neighborhood game logic', and show how our analysis can be extended to a new game algebra and dynamic game logic.

  • 8. van Benthem, Johan
    et al.
    Bezhanishvili, Nick
    Enqvist, Sebastian
    Stockholms universitet, Humanistiska fakulteten, Filosofiska institutionen. Stanford University, USA.
    A New Game Equivalence, its Logic and Algebra2019Ingår i: Journal of Philosophical Logic, ISSN 0022-3611, E-ISSN 1573-0433, Vol. 48, nr 4, s. 649-684Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We present a new notion of game equivalence that captures basic powers of interacting players. We provide a representation theorem, a complete logic, and a new game algebra for basic powers. In doing so, we establish connections with imperfect information games and epistemic logic. We also identify some new open problems concerning logic and games.

  • 9. van Benthem, Johan
    et al.
    Bezhanishvili, Nick
    Enqvist, Sebastian
    Stockholms universitet, Humanistiska fakulteten, Filosofiska institutionen.
    A Propositional Dynamic Logic for Instantial Neighborhood Semantics2019Ingår i: Studia Logica: An International Journal for Symbolic Logic, ISSN 0039-3215, E-ISSN 1572-8730, Vol. 107, nr 4, s. 719-751Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We propose a new perspective on logics of computation by combining instantial neighborhood logic INL with bisimulation safe operations adapted from PDL. INL is a recent modal logic, based on an extended neighborhood semantics which permits quantification over individual neighborhoods plus their contents. This system has a natural interpretation as a logic of computation in open systems. Motivated by this interpretation, we show that a number of familiar program constructors can be adapted to instantial neighborhood semantics to preserve invariance for instantial neighborhood bisimulations, the appropriate bisimulation concept for INL. We also prove that our extended logic IPDL is a conservative extension of dual-free game logic, and its semantics generalizes the monotone neighborhood semantics of game logic. Finally, we provide a sound and complete system of axioms for IPDL, and establish its finite model property and decidability.

1 - 9 av 9
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf