The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
Tasks' scheduling has always been a central problem in the embedded real-time systems community. As in general the scheduling problem is NP-hard, researchers have been looking for efficient heuristics to solve the scheduling problem in polynomial time. One of the most important scheduling strategies is the Earliest Deadline First (EDF). It is known that EDF is optimal for uniprocessor platforms for...
This paper describes a new application of a non-traditional parallel parsing technique for a Uniform Petal Language (UPL) program. Our bidirectional parser takes as input a UPL program, that is, a text representation of a UML specification. The benefits of parsing a UPL program are checking the correctness of the UML specification and obtaining the productions that lead to that UPL program. Consequently,...
Embedded and real-time systems are increasingly common and complex, requiring formal specification and verification in order to guarantee their satisfaction of desirable safety and timing requirements. Real-Time Logic (RTL) has been used to capture both the specification (denoted by SP) of a real-time system and the desirable safety assertions (denoted by SA) with respect to this system specification...
Cyberphysical systems are changing the way we interact with the physical world. The correctness of many systems and devices in our modern society depends not only on the effects or results they produce but also on the time at which these results are produced. Given the behavioral specification of a system (denoted by SP) and a safety assertion (denoted by SA) to be analyzed, the goal is to relate...
Automatic methods for discovering program runtime and proving program termination have always been a challenging problem in computer science. We present here a novel and systematic approach for calculating an upper bound of the maximum runtime of functions for a non-trivial class of programs. The proof is based on an induction over a tree of execution traces - a new mathematical data structure. As...
Formal specification and verification are critical to the development of safe real-time and embedded systems, which have become increasingly complex. Real-time logic (RTL) has been used to describe the specification and safety assertion of real-time systems. However, the satisfiability problem for RTL, as well as other first-order logics, is undecidable. There exist already non-trivial fragments of...
The problem of counting satisfiability, i.e. count the number of satisfying assignments for a SAT problem, is used successfully in a number of problems. For example, it can provide heuristics for guiding planning and search, where an estimation of the probability for a given search would help lead to a goal. Counting satisfiability is a valuable approach for problems like constraint satisfaction,...
The schedulability analysis problem for many realistic task models is known to be hard (NP or coNP). As this severely restricts the application of these task models, recently there has been a considerable amount of interest in relaxed or approximate notions of schedulability, with the hope that they can be checked more efficiently. In this paper we introduce yet another natural notion of relaxed schedulability,...
The scheduling problem answers the question whether a given set of input tasks is feasible. It has been studied since the 1970s and many important results have been revealed to the scientific community. This paper presents an implementation tool, PEARLS, i.e., Pliable EArliest Deadline First, Rate Monotonic, Least Laxity Schedulers, based on some of the most significant existing schedulability analytical...
Real-time logic (RTL) is useful for the verification of a safety assertion SA with respect to the specification SP of a real-time system. Since the satisfiability problem for RTL is undecidable, there were many efforts to find proper heuristics for proving that SPrarrSA holds. However, none of such heuristics necessarily finds an "optimal implication". After verifying SPrarrSA, and the system...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.