1,721,040 research outputs found
CSTNU Tool: A Java library for checking temporal networks
Full text linkThis paper presents CSTNU Tool , a Java library for representing and checking different kinds of temporal constraint networks. In particular, CSTNU Tool offers an optimized implementation of some constraint-propagation algorithms to check the dynamic consistency/controllability (DC) of Conditional Simple Temporal Networks (CSTNs), Conditional Simple Temporal Networks with Uncertainty (CSTNUs), and Flexible Simple Temporal Networks with Uncertainty (FTNUs). The optimization is with respect to the management of labeled values that are present in conditional and flexible networks. The library offers also a simple GUI application to build/manage and check temporal networks in an intuitive way, and some Java programs for generating random temporal networks according to some input parameters
Adding flexibility to uncertainty: Flexible Simple Temporal Networks with Uncertainty (FTNU)
Full text linkA Flexible Simple Temporal Network with Uncertainty (FTNU) represents temporal constraints between time-points. Time-points are variables that must be set (executed) satisfying all the constraints. Some time-points are contingent. It means that they are set by the environment and only observed by the system executing the network. The ranges repre- senting temporal constraints associated with contingent time-points (guarded ranges) can be shrunk during execution only to some extent to have more flexibility in the execution of the network. Subsets of time-points/constraints may be executed/considered in different contexts according to some observed conditions. The main issue here consists of determining whether all the time-points, under the control of the system, are executable in a way that all the specified constraints are satisfied for any possible occurrence of contingent time-points and any possible context. Such property is called controllability. Even though an algorithm was proposed for checking the controllability of such networks, we show that such an algorithm has a limit. Indeed, it does not determine the right bounds for guarded links, and, therefore, it doesn’t permit the system to exploit the potential flexibility of the network. We then propose a new constraint-propagation algorithm for checking controllability, prove that such a new algorithm determines the right guarded ranges, and it is sound-and-complete. Thus, it can be used also for executing the network, by leveraging its flexibility
Dynamic-Consistency Checking for Conditional Simple Temporal Networks: Strengthening the Theoretical Foundations and Presenting a Faster Algorithm
Full text linkRecent work on Conditional Simple Temporal Networks (CSTNs) has focused on checking the dynamic consistency (DC) property for the case where an execution strategy can react instantaneously to observations. Three alternative semantics for such strategies—IR-dynamic, 0-dynamic, and π-dynamic—have been presented. However, the most practical DC-checking algorithm has only been analyzed with respect to the IR semantics. Meanwhile, 0-dynamic strategies were shown to permit a kind of circular dependence among simultaneous observations, making them impossible to implement, whereas π-dynamic strategies prohibit this kind of circularity. Whether IR-dynamic strategies allow this kind of circularity and, if so, what the consequences would be for the above-mentioned DC-checking algorithm remained open questions. This paper makes the following contributions: (1) it shows that IR-dynamic strategies do allow circular dependence and, thus, that the IR semantics does not properly capture instantaneous reactivity; (2) it shows that one of the constraint-propagation rules from the IR-DC-checking algorithm is unsound with respect to the IR semantics; (3) it presents a simpler DC-checking algorithm, called the π-DC-checking algorithm, that uses half of the rules from the earlier algorithm, and that it proves is sound and complete with respect to the π-DC semantics; (4) it empirically evaluates the new algorithm. Thus, the paper places practical DC checking for CSTNs in the case of instantaneous reaction on a solid theoretical foundation
Internationalizing Data-Intensive Web Applications
No full textNowadays a considerable amount of web sites are data-intensive web sites, meaning that web pages are generated by extracting their content on the fly from a database system. Systems of this type are often the result of an integration process between intranet legacy systems and Internet web applications that represent the front end of the organization towards the rest of the world. The globalization process, that influences the activities of any organization (company, public agencies, etc.), makes it necessary to provide information in different languages in order to enlarge the audience of the information presented through the web. Therefore, it is often required to extend the web system for handling information in more than one language. This process is called internationalization of an application or system. Another important requirement in this process is that it should be applied without a strong reorganization of the web applications that implements the web site, so that the main cost would regard the translation of the web contents. We propose a general framework for the internationalization of data-intensive web application based on the MVC-2 paradigm and a relational database system. Moreover it can be applied to existing web applications with a low impact on code restructuring. This framework has been applied at the University of Verona (Italy) for the internationalization of the web sites of all departments and faculties of this university
Recent Algorithmic Advances in Simple Temporal Networks with Uncertainty: from Faster Controllability Checking to Faster Execution
Full text linkThis paper presents theoretical and algorithmic contributions that advance the state of the art in the dynamic
controllability and dispatchability of Simple Temporal Networks with Uncertainty (STNUs).
The first new algorithm, findSRNC, identifies and compactly represents semi-reducible negative (SRN) cycles in STNUs that are not dynamically controllable (DC)—a key step toward repairing such networks. It runs in O(mn + k^2 n + k n log n) time, where n is the number of timepoints, m the number of constraints, and k the number of actions with uncertain durations. This matches the fastest DC-checking algorithms for STNUs and improves on
prior SRN-cycle detection methods. It also handles repeated edges—often overlooked in the literature—and uses only polynomial space even when fully expanded SRN cycles would be exponentially large.
The second new algorithm addresses dispatchability. Real-time execution of STNUs requires dispatchable ESTNUs (extended STNUs); being DC is not sufficient. In addition, to minimize execution overhead, it is crucial to reduce the number of edges in the dispatchable network. A previous algorithm, minDispESTNU , for computing an equivalent dispatchable network having a minimal number of edges runs in O(k n^3) time. Our new algorithm, minDisp+ESTNU, modifies minDispESTNU to improve its worst-case complexity from O(k n^3) to O(n^3 + k^2 n log n).
The third contribution is a rigorous and comprehensive theory of the canonical form of nested diamond structures in dispatchable ESTNUs that greatly facilitates the proofs of correctness for both minDispESTNU and minDisp+ESTNU, while also revealing and enabling the correction of a flaw in a previous algorithm, called fastMinDispESTNU.
The fourth contribution is an empirical evaluation of the two new algorithms using an improved open-source implementation to demonstrate their effectiveness.
For completeness, the paper first reviews several key existing algorithms from the literature, such as RUL2021 for DC checking, RTE^∗ for real-time execution, and minDispESTNU for dispatchability
Foundations of Dispatchability for Simple Temporal Networks with Uncertainty
Full text linkSimple Temporal Networks (STNs) are a widely used formalism for representing and reasoning about temporal constraints on activities. The dispatchability of an STN was originally defined as a guarantee that a specific real-time execution algorithm would necessarily satisfy all of the STN’s constraints while preserving maximum flexibility but requiring minimal computation. A Simple Temporal Network with Uncertainty (STNU) augments an STN to accommodate actions with uncertain durations. However, the dispatchability of an STNU was defined differently: in terms of the dispatchability of its so-called STN projections. It was then argued informally that this definition provided a similar real-time execution guarantee, but without specifying the execution algorithm. This paper formally defines a real-time execution algorithm for STNUs that similarly preserves maximum flexibility while requiring minimal computation. It then proves that an STNU is dispatchable if and only if every run of that real-time execution algorithm necessarily satisfies the STNU's constraints no matter how the uncertain durations play out. By formally connecting STNU dispatchability to an explicit real-time execution algorithm, the paper fills in important elements of the foundations of the dispatchability of STNUs
An Algorithm for the Selection of High-Contrast Color Sets
No full textNominal color coding is the aesthetic and functional use of color to convey qualitative information in graphical environments. The specification of high-contrast color sets is a fundamental step in this process. We formulate the color-coding problem here as a combinatorial optimization problem on graphs and present an algorithm that performs well and does not require that the function used to code the similarity between colors be a distance function
TimeAwareBPMN-js: An editor and temporal verification tool for Time-Aware BPMN processes
Full text linkThis paper presents TimeAwareBPMN-js, a graphical web-based editor for time-aware BPMN (Business Process Model and Notation) models that allows (1) creating and editing of BPMN processes enriched with temporal constraints, such as contingent durations and conditions, and (2) verifying that such constraints are well-defined and satisfy some (temporal) properties. The verification of temporal constraints is realized by plug-ins that can be easily added by the user thanks to the modular architecture of the application. Different plug-ins may verify different temporal properties. As a proof- of-concept, TimeAwareBPMN-js contains the CSTNU plug-in which verifies the dynamic controllability property, i.e., it checks, at design-time, whether there exists a run-time schedule for the process that satisfies all temporal constraints no matter how contingent durations and conditions are revealed during execution
Faster Dynamic-Consistency Checking for Conditional Simple Temporal Networks
Full text linkA Conditional Simple Temporal Network (CSTN) is a structure for representing and reasoning about time in domains where temporal constraints may be conditioned on outcomes of observations made in real time. A CSTN is dynamically consistent (DC) if there is a strategy for executing its time-points such that all relevant constraints will necessarily be satisfied no matter which outcomes happen to be observed. The literature on CSTNs contains only one sound-and-complete DC-checking algorithm that has been implemented and empirically evaluated. It is a graph-based algorithm that propagates labeled constraints/edges. A second algorithm has been proposed, but not evaluated. It aims to speed up DC checking by more efficiently dealing with so-called negative q-loops. This paper presents a new two-phase approach to DC-checking for CSTNs. The first phase focuses on identifying negative q-loops and labeling key time-points within them. The second phase focuses on computing (labeled) distances from each time-point to a single sink node. The new algorithm, which is also sound and complete for DC-checking, is then empirically evaluated against both pre-existing algorithms and shown to be much faster across not only previously published benchmark problems, but also a new set of benchmark problems. The results show that, on DC instances, the new algorithm tends to be an order of magnitude faster than both existing algorithms. On all other benchmark cases, the new algorithm performs better than or equivalently to the existing algorithms
Speeding Up the RUL ̄ Dynamic-Controllability-Checking Algorithm for Simple Temporal Networks with Uncertainty
Full text linkA Simple Temporal Network with Uncertainty (STNU) includes real-valued variables called time points, binary difference constraints on those time points, and contingent links that represent actions with uncertain durations. STNUs have been used for robot control, web service composition, and business processes. The most important property of an STNU is called dynamic controllability (DC), and algorithms for checking this property are called DC-checking algorithms. The DC-checking algorithm for STNUs with the best worst-case time complexity is the RUL ̄ algorithm due to Cairo, Hunsberger, and Rizzi. Its complexity is O(mn + k2n + kn log n), where n is the number of time points, m is the number of constraints, and k is the number of contingent links. It is expected that this worst-case complexity cannot be improved upon. However, this paper provides a new algorithm, called RUL2021, that improves its performance in practice by an order of magnitude, as demonstrated by a thorough empirical evaluation
- …
