Vague notions, such as ‘generally’, ‘rarely’, ‘often’, ‘almost always’, ‘a meaningful subset of a whole’, ‘most’, etc., occur often in ordinary language and in some branches of science. We introduce modal logical systems, with generalized operators, for the precise treatment of assertions involving some versions of such vague notions. We examine modal logics, constructed in a modular fashion, with generalized operators corresponding to some versions of ‘generally’ and ‘rarely’.

Graphs are among the most frequently used structures in Computer Science. Some of the properties that must be checked in many applications are connectivity, acyclicity and the Eulerian and Hamiltonian properties. In this work, we analyze how we can express these four properties with modal logics. This involves two issues: whether each of the modal languages under consideration has enough expressive power to describe these properties and how complex it is to use these logics to actually test whether a given (...) graph has some desired property. First, we show that these properties are not definable in a basic modal logic or in any bisimulation-invariant extension of it, like the modal μ-calculus. We then show that it is possible to express some of the above properties in a basic hybrid logic. Unfortunately, the Hamiltonian and Eulerian properties still cannot be efficiently checked. In a second attempt, we propose an extension of CTL* with nominals and show that the Hamiltonian property can be more efficiently checked in this logic than in the previous one. In a third attempt, we extend the basic hybrid logic with the ↓ operator and show that we can check the Hamiltonian property with optimal complexity in this logic. Finally, we tackle the Eulerian property in two different ways. First, we develop a generic method to express edge-related properties in hybrid logics and use it to express the Eulerian property. Second, we express a necessary and sufficient condition for the Eulerian property to hold using a graded modal logic. (shrink)

This work introduces a two-dimensional modal logic to represent agents' Concurrent Common Knowledge in distributed systems. Unlike Common Knowledge, Concurrent Common Knowledge is a kind of agreement reachable in asynchronous environments. The formalization of such type of knowledge is based on a model for asynchronous systems and on the definition of Concurrent Knowledge introduced before in paper [5]. As a proper semantics, we review our concept of closed sub-product of modal logics which is based on the product of modal logics. (...) The key idea is to reason about Concurrent Knowledge under a two-dimensional approach, regarding asynchronous runs and consistent global states as dimensions. We present an axiomatic system for the logic and issue the corresponding soundness and completeness proofs. (shrink)

This paper introduces a two-dimensional modal logic to reason about knowledge in asynchronous multi-agent message-passing systems. We present a new theoretical definition for concurrent knowledge in order to describe the kind of knowledge typical in such asynchronous environments. To define concurrent knowledge, we propose the closed sub-product of modal logics: a two-dimensional formal semantics where one dimension corresponds to asynchronous runs, the other corresponds to consistent cuts and the concurrent knowledge is defined as the transitive closure over the product of (...) the former dimensions. We axiomatize the presented logic issuing proofs of soundness and completeness with respect to the class of closed sub-product of modal frames. (shrink)

In this paper we show that the class of fork squares has a complete orthodox axiomatization in fork arrow logic (FAL). This result may be seen as an orthodox counterpart of Venema's non-orthodox axiomatization for the class of squares in arrow logic. FAL is the modal logic of fork algebras (FAs) just as arrow logic is the modal logic of relation algebras (RAs). FAs extend RAs by a binary fork operator and are axiomatized by adding three equations to RAs equational (...) axiomatization. A proper FA is an algebra of relations where the fork is induced by an injective operation coding pair formation. In contrast to RAs, FAs are representable by proper ones and their equational theory has the expressive power of full first-order logic. A square semantics (the set of arrows is U×U for some set U) for arrow logic was defined by Y. Venema. Due to the negative results about the finite axiomatizability of representable RAs, Venema provided a non-orthodox finite axiomatization for arrow logic by adding a new rule governing the applications of a difference operator. We address here the question of extending the type of relational structures to define orthodox axiomatizations for the class of squares. Given the connections between this problem and the finitization problem addressed by I. Németi, we suspect that this cannot be done by using only logical operations. The modal version of the FA equations provides an orthodox axiomatization for FAL which is complete in view of the representability of FAs. Here we review this result and carry it further to prove that this orthodox axiomatization for FAL also axiomatizes the class of fork squares. (shrink)

In this paper we show that the class of fork squares has a complete orthodox axiomatization in fork arrow logic (FAL). This result may be seen as an orthodox counterpart of Venema's non-orthodox axiomatization for the class of squares in arrow logic. FAL is the modal logic of fork algebras (FAs) just as arrow logic is the modal logic of relation algebras (RAs). FAs extend RAs by a binary fork operator and are axiomatized by adding three equations to RAs equational (...) axiomatization. A proper FA is an algebra of relations where the fork is induced by an injective operation coding pair formation. In contrast to RAs, FAs are representable by proper ones and their equational theory has the expressive power of full first-order logic. A square semantics (the set of arrows is ᵎ x ᵎ for some set ᵎ) for arrow logic was defined by Y. Venema. Due to the negative results about the finite axiomatizability of representable RAs, Venema provided a non-orthodox finite axiomatization for arrow logic by adding a new rule governing the applications of a difference operator. We address here the question of extending the type of relational structures to define orthodox axiomatizations for the class of squares. Given the connections between this problem and the finitization problem addressed by I. Németi, we suspect that this cannot be done by using only logical operations. The modal version of the FA equations provides an orthodox axiomatization for FAL which is complete in view of the representability of FAs. Here we review this result and carry it further to prove that this orthodox axiomatization for FAL also axiomatizes the class of fork squares. (shrink)

We compare fork arrow logic, an extension of arrow logic, and its natural first-order counterpart (the correspondence language) and show that both have the same expressive power. Arrow logic is a modal logic for reasoning about arrow structures, its expressive power is limited to a bounded fragment of first-order logic. Fork arrow logic is obtained by adding to arrow logic the fork modality (related to parallelism and synchronization). As a result, fork arrow logic attains the expressive power of its first-order (...) correspondence language, so both can express the same input–output behavior of processes. (shrink)

We compare fork arrow logic, an extension of arrow logic, and its natural first-order counterpart (the correspondence language) and show that both have the same expressive power. Arrow logic is a modal logic for reasoning about arrow structures, its expressive power is limited to a bounded fragment of first-order logic. Fork arrow logic is obtained by adding to arrow logic the fork modality (related to parallelism and synchronization). As a result, fork arrow logic attains the expressive power of its first-order (...) correspondence language, so both can express the same input-output behavior of processes. (shrink)