Search

In this paper we explore the linear logic of multi-agent knowledge using multivalued models. The logic of the language contains the unary operators $K_{j}$ --- $j$ --- the agent knows, $ULK_{G}$ --- unstable local knowledge, $E_{G}$ --- stable local knowledge in the group, and the binary logical operator $AP_{G}$ - the majority opinion. We will show some examples that demonstrate the diversity of this language and its capabilities. Technically we prove decidability of satisfiability problem in the resulting models for our multi-agent logic, develop verification technique and provide some examples.

In his famous letter to A. N. Prior dated 3 September 1958, Saul Kripke suggested the use of branching time in temporal logic. In this paper, however, it is argued that Prior worked with an idea close to the notion of branching time ('the big Y') already the year before he received Kripke's letter. It is likely that Prior's findings based on this early study can explain why Prior so quickly accepted the idea of branching time when he received Kripke's letter. [ABSTRACT FROM AUTHOR]

The rise of machine learning and cloud technologies has led to a remarkable influx of data within modern cyber-physical systems. However, extracting meaningful information from this data has become a significant challenge due to its volume and complexity. Timed pattern matching has emerged as a powerful specification-based runtime verification and temporal data analysis technique to address this challenge. In this paper, we provide a comprehensive tutorial on timed pattern matching that ranges from the underlying algebra and pattern specification languages to performance analyses and practical case studies. Analogous to textual pattern matching, timed pattern matching is the task of finding all time periods within temporal behaviors of cyber-physical systems that match a predefined pattern. Originally we introduced and solved several variants of the problem using the name of match sets, which has evolved into the concept of timed relations over the past decade. Here we first formalize and present the algebra of timed relations as a standalone mathematical tool to solve the pattern matching problem of timed pattern specifications. In particular, we show how to use the algebra of timed relations to solve the pattern matching problem for timed regular expressions and metric compass logic in a unified manner. We experimentally demonstrate that our timed pattern matching approach performs and scales well in practice. We further provide in-depth insights into the similarities and fundamental differences between monitoring and matching problems as well as regular expressions and temporal logic formulas. Finally, we illustrate the practical application of timed pattern matching through two case studies, which show how to extract structured information from temporal datasets obtained via simulations or real-world observations. These results and examples show that timed pattern matching is a rigorous and efficient technique in developing and analyzing cyber-physical systems. [ABSTRACT FROM AUTHOR]

We combine linear temporal logic (with both past and future modalities) with a deontic version of justification logic to provide a framework for reasoning about time and epistemic and normative reasons. In addition to temporal modalities, the resulting logic contains two kinds of justification assertions: epistemic justification assertions and deontic justification assertions. The former presents justification for the agent's knowledge and the latter gives reasons for why a proposition is obligatory. We present two kinds of semantics for the logic: one based on Fitting models and the other based on neighborhood models. The use of neighborhood semantics enables us to define the dual of deontic justification assertions properly, which corresponds to a notion of permission in deontic logic. We then establish the soundness and completeness of an axiom system of the logic with respect to these semantics. Further, we formalize the Protagoras versus Euathlus paradox in this logic and present a precise analysis of the paradox, and also briefly discuss Leibniz's solution. [ABSTRACT FROM AUTHOR]

Due to the popularity of web-based technologies and the cloud computing paradigm, organizations are adopting web services composition for the cost-effective development of business applications. Web services involved in composition can execute long-running transactions. Ensuring reliability in the execution of transaction-aware web services composition is a critical issue. Formal methods based approaches are helpful to model and verify the behaviour of web services composition before its development. This paper proposes a verification approach that presents mapping between BPEL and CSP constructs, and checks different assertions to get correct CSP and BPEL models. The proposed approach also verifies the transactional behaviour of web services composition. We have used failures-divergences refinement and new symbolic model checker tools for experiments that show the usefulness of our approach. [ABSTRACT FROM AUTHOR]

One of Pavel Tichý’s celebrated observations was that definite descriptions do not denote individuals but individual offices. In our paper, we compare Tichý’s concept of individual offices to the concept proposed by Arthur N. Prior, who differentiated between the strong and the weak "the". The aim of our paper is to point out parallels and differences. The differences stem in particular from their different approaches to contingency given by their accepted ontology. In addition, we would like to enrich Tichý’s analysis of individual offices by including certain features of Prior’s concept. The proposed outline might provide a challenge for a more detailed analysis of definite descriptions in Tichý’s Transparent Intensional Logic.

Abstract This paper considers the problem of communication protocols between leaders and its followers for motion planning in an initially partially known environment. In this setting, the leader observes the environment information to satisfy its own local objective and and the follower completes its own local objective by estimating the states of the leader and communicating with the leader to update its knowledge about the environment when it is necessary, where the local objectives can be expressed in temporal logic. A verifier construction is built first to contain all possible communication protocols between the leaders and the followers. Then, a two‐step synthesis procedure is proposed to capture all feasible communication protocol that satisfy the local objectives for the leader and follower, respectively. In the first step, a sub‐verifier is synthesized to satisfy the objective of the follower. In the second step, based on the obtained sub‐verifier, an iterative algorithm is proposed to extract communication protocols such that the objectives of the leader and follower are satisfied, respectively. A running example is provided to illustrate the proposed procedures.

A dendrocentric backpropagation spike timing-dependent plasticity learning rule has been derived based on temporal logic for a single octopus neuron. It receives parallel spike trains and collectively adjusts its synaptic weights in the range [0, 1] during training. After the training phase, it spikes in reaction to event signaling input patterns in sensory streams. The learning and switching behavior of the octopus cell has been implemented in field-programmable gate array (FPGA) hardware. The application in an FPGA is described and the proof of concept for its application in hardware that was obtained by feeding it with spike cochleagrams is given; also, it is verified by performing a comparison with the pre-computed standard software simulation results.

Runtime verification is a lightweight method for monitoring the formal specification of a system during its execution. It has recently been shown that a given state predicate can be monitored consistently by a set of crash-prone asynchronous distributed monitors observing the system, only if each monitor can emit verdicts taken from a large enough finite set. We revisit this impossibility result in the concrete context of linear-time logic (LTL) semantics for runtime verification, that is, when the correctness of the system is specified by an LTL formula on its execution traces. First, we show that monitors synthesized based on the 4-valued semantics of LTL (rv-LTL) may result in inconsistent distributed monitoring, even for some simple LTL formulas. More generally, given any LTL formula φ, we relate the number of different verdicts required by the monitors for consistently monitoring φ, with a specific structural characteristic of φ called its alternation number. Specifically, we show that, for every k ≥ 0, there is an LTL formula φ with alternation number k that cannot be verified at runtime by distributed monitors emitting verdicts from a set of cardinality smaller than k + 1. On the positive side, we define a family of logics, called distributed LTL (abbreviated as dLTL), parameterized by k ≥ 0, which refines RV-LTL by incorporating 2k + 4 truth values. Our main contribution is to show that, for every k ≥ 0, every LTL formula φ with alternation number k can be consistently monitored by distributed monitors, each running an automaton based on a (2⌈k/2⌉ + 4)-valued logic taken from the dltl family. [ABSTRACT FROM AUTHOR]

This paper considers the problem of communication protocols between leaders and its followers for motion planning in an initially partially known environment. In this setting, the leader observes the environment information to satisfy its own local objective and and the follower completes its own local objective by estimating the states of the leader and communicating with the leader to update its knowledge about the environment when it is necessary, where the local objectives can be expressed in temporal logic. A verifier construction is built first to contain all possible communication protocols between the leaders and the followers. Then, a two‐step synthesis procedure is proposed to capture all feasible communication protocol that satisfy the local objectives for the leader and follower, respectively. In the first step, a sub‐verifier is synthesized to satisfy the objective of the follower. In the second step, based on the obtained sub‐verifier, an iterative algorithm is proposed to extract communication protocols such that the objectives of the leader and follower are satisfied, respectively. A running example is provided to illustrate the proposed procedures. [ABSTRACT FROM AUTHOR]

Today, various applications in different domains increasingly rely on high-performance computing (HPC) to accomplish computations swiftly. Integrating one or more programming models alongside the used programming language enhances system parallelism, thereby improving its performance. However, this integration can introduce runtime errors such as race conditions, deadlocks, or livelocks. Some of these errors may go undetected using conventional testing techniques, necessitating the exploration of additional methods for enhanced reliability. Formal methods, such as temporal logic, can be useful for detecting runtime errors since they have been widely used in real-time systems. Additionally, many software systems must adhere to temporal properties to ensure correct functionality. Temporal logics indeed serve as a formal frame that takes into account the temporal aspect when describing changes in elements or states over time. This paper proposes a temporal-logic-based testing tool utilizing instrumentation techniques designed for a dual-level programming model, namely, Message Passing Interface (MPI) and Open Multi-Processing (OpenMP), integrated with the C++ programming language. After a comprehensive study of temporal logic types, we found and proved that linear temporal logic is well suited as the foundation for our tool. Notably, while the tool is currently in development, our approach is poised to effectively address the highlighted examples of runtime errors by the proposed solution. This paper thoroughly explores various types and operators of temporal logic to inform the design of the testing tool based on temporal properties, aiming for a robust and reliable system. [ABSTRACT FROM AUTHOR]

In this paper, we prove the measurability of an event for which a general continuous–time stochastic process satisfies the continuous–time Metric Temporal Logic (MTL) formula. Continuous–time MTL can define temporal constraints for physical systems naturally. Several previous studies deal with the probability of continuous MTL semantics for stochastic processes. However, proving measurability for such events is not an obvious task, even though it is essential. The difficulty comes from the semantics of “until operator,” which is defined by the logical sum of uncountably many propositions. Given the difficulty in proving such an event’s measurability using classical measure-theoretic methods, we employ a theorem from stochastic analysis. This theorem is utilized to prove the measurability of hitting times for stochastic processes, and it stands as a profound result within the theory of capacity. Next, we provide an example that illustrates the failure of probability approximation when discretizing the continuous semantics of MTL–formulas with respect to time. Additionally, we prove that the probability of the discretized semantics converges to that of the continuous semantics when we impose restrictions on diamond operators to prevent nesting. [ABSTRACT FROM AUTHOR]

In this paper, we study temporal logic for finite linear structures and surjective bounded morphisms between them. We give a characterisation of such structures by modal formulas and show that every pair of linear structures with a bounded morphism between them can be uniquely characterised by a temporal formula up to an isomorphism. As the main result, we prove Kripke completeness of the logic with respect to the class of finite linear structures with bounded morphisms between them. [ABSTRACT FROM AUTHOR]

The object of research in this article is the process of modeling programs and their subsequent development. The purpose of this article is to develop a methodology for describing and building software models in the form of nondeterministic finite automat. To achieve this goal, a task was set to improve the method for describing such models using predicates based on the MODEL CHECKING technology. The result of this article is a method for describing and presenting program models directly according to the chosen algorithm using predicates. If the program algorithm is chosen and described correctly, the resulting model should also be correct. The model will be a non-deterministic state machine that will not require further checking, as provided by the MODEL CHECKING technology. Structurally, the model will represent a special database, the processing of which will allow turning the model into a program in any procedural programming language. When developing parallel programs that are widely used for control in aviation, land transport, military affairs, etc., two additional states of the automaton are introduced into the model, which take into account the features of such programs. Therefore, a state monitor is provided for access to shared resources and a state protocol to process parallel branches of the program. To describe the algorithm of the program, we propose to present it in the form of a connected sequence of certain actions using predicates with the use of extended temporal logic. This description covers both the logic of the program and its branches and the specific actions at each location of the program model. With the help of this methodology, a program model of a stack algorithm was developed, which is the main component for the future automated system of processing the description of program models. The program which was created according to this technology, is currently in the testing and verification stage. The sequence of processing steps of such a model is shown in the example of a floating-point constant translation program. This program is also created using this technology in the target language assembly, has been fully tested, and has shown its functionality. This description covers both the logic of the program with its branches and the specific actions at each location of the application model. Conclusions: with a correct description of the program algorithm, an adequate model of it is built, with the help of which the program itself is created in the target procedural programming language. Note that in the conditions of the rapid development of management and control automation systems in various spheres of human activity, research on the creation of reliable based on the description of their models is an urgent problem.004.414.23:510.637

Specification languages for runtime verification are commonly rooted in formal languages, such as temporal logic, automata, or regular expressions. We argue that, for practical purposes, specification languages for monitoring should allow language features similar to those found in general purpose programming languages, in addition to providing specialized monitoring constructs. Using a realistic and large event-log, we compare two such programming-oriented monitoring language systems to a temporal logic-based monitoring system that was previously evaluated on the same log. The first programming-oriented language is a library in Scala developed for runtime verification. The other language is a scripting language, originally developed for fast static code analysis. We formulate the same reasonably complex properties as in the temporal logic case, using both methods, and compare the efficiency with which they can be checked against the large event log, and the ease with which the properties can be formulated. [ABSTRACT FROM AUTHOR]

We introduce a weighted linear dynamic logic (weighted LDL for short) and show the expressive equivalence of its formulas to weighted rational expressions. This adds a new characterization for recognizable series to the fundamental Schützenberger theorem. Surprisingly, the equivalence does not require any restriction to our weighted LDL. Our results hold over arbitrary (resp. totally complete) semirings for finite (resp. infinite) words. As a consequence, the equivalence problem for weighted LDL formulas over fields is decidable in doubly exponential time. In contrast to classical logics, we show that our weighted LDL is expressively incomparable to weighted LTL for finite words. We determine a fragment of the weighted LTL such that series over finite and infinite words definable by LTL formulas in this fragment are definable also by weighted LDL formulas. This is an extended version of [17]. [ABSTRACT FROM AUTHOR]

The object of research in this article is the process of modeling programs and their subsequent development. The purpose of this article is to develop a methodology for describing and building software models in the form of nondeterministic finite automat. To achieve this goal, a task was set to improve the method for describing such models using predicates based on the MODEL CHECKING technology. The result of this article is a method for describing and presenting program models directly according to the chosen algorithm using predicates. If the program algorithm is chosen and described correctly, the resulting model should also be correct. The model will be a non-deterministic state machine that will not require further checking, as provided by the MODEL CHECKING technology. Structurally, the model will represent a special database, the processing of which will allow turning the model into a program in any procedural programming language. When developing parallel programs that are widely used for control in aviation, land transport, military affairs, etc., two additional states of the automaton are introduced into the model, which take into account the features of such programs. Therefore, a state monitor is provided for access to shared resources and a state protocol to process parallel branches of the program. To describe the algorithm of the program, we propose to present it in the form of a connected sequence of certain actions using predicates with the use of extended temporal logic. This description covers both the logic of the program and its branches and the specific actions at each location of the program model. With the help of this methodology, a program model of a stack algorithm was developed, which is the main component for the future automated system of processing the description of program models. The program which was created according to this technology, is currently in the testing and verification stage. The sequence of processing steps of such a model is shown in the example of a floating-point constant translation program. This program is also created using this technology in the target language assembly, has been fully tested, and has shown its functionality. This description covers both the logic of the program with its branches and the specific actions at each location of the application model. Conclusions: with a correct description of the program algorithm, an adequate model of it is built, with the help of which the program itself is created in the target procedural programming language. Note that in the conditions of the rapid development of management and control automation systems in various spheres of human activity, research on the creation of reliable based on the description of their models is an urgent problem. [ABSTRACT FROM AUTHOR]

We establish the precise complexity of the model-checking problem for the main logics of knowledge and time. While this problem was known to be non-elementary for agents with perfect recall, with a number of exponentials that increases with the alternation of knowledge operators, the precise complexity of the problem when the maximum alternation is fixed has been an open problem for 20 years. We close it by establishing improved upper bounds for CTL * with knowledge and providing matching lower bounds that also apply for epistemic extensions of LTL and CTL. We also study the model-checking problem for these logics on systems satisfying the "no learning" property, introduced by Halpern and Vardi in their taxonomy of logics of knowledge and time, and we settle the complexity in almost all cases. [ABSTRACT FROM AUTHOR]

In Death and Nonexistence, Palle Yourgrau defends what he calls the principle of Prior Possibility: nothing comes to exist unless it was previously possible that it exists. While this seems like a plausible principle, it’s not strong enough; it allows the impossible to come to exist. I argue for a stronger principle: nothing exists unless its existence has always been possible. Further, I argue that we then have reason to accept a surprising result: nothing exists unless its existence is always possible. Or, more generally, that nothing is the case unless it’s always possible that it’s the case. [ABSTRACT FROM AUTHOR]

In this paper, we give a basic structure theorem based on the study of extreme cases for the value of ≺ (the classical precedence relation between ultrafilters), i.e., ≺ = ∅ and no isolated element in ≺. This gives rise, respectively, to the temporal varieties O and W , with the result that O generates a variety of temporal algebras. We also characterize the simple temporal algebras by means of arithmetical properties related to basical temporal operators; we conclude that the simplicity of the temporal algebra lies in being able to make 0 any element less than 1 by repeated application to it of the L operator. We then present an algebraic construction similar to a product but in which the temporal operations are not defined componentwise. This new "product" is shown to be useful in the study of algebra order and finding of bounds by means of something similar to a lifting process. Finally, we give an alternative proof of an already known result on atoms counting in free temporal algebras. [ABSTRACT FROM AUTHOR]

In 2003 Zia Movahed pointed to a passage of Avicenna, written probably in 1022, which Movahed claimed anticipated the modal formula of Barcan (that 'For every |$x$| necessarily |$\phi $| ' entails 'Necessarily for every |$x$| |$\phi $| '), and its converse. Since 2003, examination of early logical writings of Avicenna has clarified how he understood entailments between modal sentences, using his own new temporal language to provide a kind of semantics. In the light of that, Movahed's claim for the Barcan formula needs some tidying up but is basically correct. But by his semantics Avicenna should not have claimed the converse Barcan formula and probably didn't claim it. [ABSTRACT FROM AUTHOR]

We work towards a vocabulary to represent processes and temporal logic specifications as graph-structured data. Different fields use incompatible terminologies for describing essentially the same process-related concepts. In addition, processes can be represented from different perspectives and levels of abstraction: both state-centric and event-centric perspectives offer distinct insights into the underlying processes. In this work, we strive to unify the representation of processes and related concepts by leveraging the power of knowledge graphs. We survey approaches to representing processes and reasoning with process descriptions from different fields and provide a selection of scenarios to help inform the scope of a unified representation of processes. We focus on processes that can be executed and observed via web interfaces. We propose to provide a representation designed to combine state-centric and event-centric perspectives while incorporating temporal querying and reasoning capabilities on temporal logic specifications. A standardised vocabulary and representation for processes and temporal specifications would contribute towards bridging the gap between the terminologies from different fields and fostering the broader application of methods involving temporal logics, such as formal verification and program synthesis.

Superconducting technology is a prime candidate for the future of computing. However, current superconducting prototypes are limited to small-scale examples due to stringent area constraints and complex architectures inspired from voltage-level encoding in CMOS; this is at odds with the ps-wide Single Quantum Flux (SFQ) pulses used in superconductors to carry information. In this work, we propose a wave-pipelined Unary SFQ (U-SFQ) architecture that leverages the advantages of two data representations: pulse-streams and Race Logic (RL). We introduce novel building blocks such as multipliers, adders, and memory cells, which leverage the natural properties of SFQ pulses to mitigate area constraints. We then design and simulate three popular hardware accelerators: i) a Processing Element (PE), typically used in spatial architectures; ii) A dot-product-unit (DPU), one of the most popular accelerators in artificial neural networks and digital signal processing (DSP); and iii) A Finite Impulse Response (FIR) filter, a popular and computationally demanding DSP accelerator. The proposed U-SFQ building blocks require up to 200× fewer JJs compared to their SFQ binary counterparts, exposing an area-delay trade-off. This work mitigates the stringent area constraints of superconducting technology.