Search

In this article, we introduce and investigate an extension of Halpern and Shoham’s interval temporal logic HS for the specification and verification of branching-time context-free requirements of pushdown systems under a state-based semantics over Kripke structures enforcing visibility of the pushdown operations. The proposed logic, called nested BHS , supports branching-time both in the past and in the future and is able to express non-regular properties of linear and branching behaviours of procedural contexts in a natural way. It strictly subsumes well-known linear time context-free extensions of LTL such as CaRet [ 4 ] and NWTL [ 2 ]. The main result is the decidability of the visibly pushdown model-checking problem against nested BHS . The proof exploits a non-trivial automata-theoretic construction.

The edge-cloud collaboration network is promising to support complex requirements with temporal constraints, where a requirement can be achieved through the composition of computation-demanding and delay-sensitive services. In this setting, most services should be optimally configured at the network edge, in order to decreasing service response latency and reducing network resource consumption. To address this challenge, this paper proposes an optimal service configuration mechanism, where temporal constraints between services are mined from event logs through our temporal interval discovery mechanism. Service configuration is formulated as a constrained multi-objective optimization problem, which is solved by our improved non-dominated sorting genetic algorithm II. Extensive experiments are conducted, and evaluation results demonstrate that our approach can find the close-to-optimal service configuration in comparison with the state-of-the-art techniques in terms of delay sensitivity and energy efficiency, especially when edge nodes can co-host a relatively large number of services.

Motion Blur is an important effect of photo-realistic rendering. Distribution ray tracing can simulate motion blur very well by integrating light, both over the spatial and the temporal domain. However, increasing the problem by the temporal dimension entails many challenges, particularly in cinematic multi-bounce path tracing of complex scenes, where heavy-weight geometry with complex lighting and even offscreen elements contribute to the final image. In this paper, we propose the Motion DAG (Directed Acyclic Graph), a novel data structure that filters an entire animation sequence of an object, both in the spatial and temporal domain. These Motion DAGs interleave a temporal interval binary tree for filtering time consecutive data and a sparse voxel octree (SVO), which simplifies spatially nearby data. Motion DAGs are generated in a pre-process and can be easily integrated in a conventional physically based path tracer. Our technique is designed to target motion blur of small objects, where coarse representations are sufficient. Specifically, in this scenario our results show that it is possible to significantly reduce both, memory consumption and render time.

Model checking for Halpern and Shoham's interval temporal logic HS has been recently investigated in a systematic way, and it is known to be decidable under three distinct semantics. Here, we focus on the trace-based semantics, where the infinite execution paths (traces) of the given (finite) Kripke structure are the main semantic entities. In this setting, each finite infix of a trace is interpreted as an interval, and a proposition holds over an interval if and only if it holds over each component state (homogeneity assumption). In this paper, we introduce a quantitative extension of HS over traces, called parametric HS (PHS). The novel logic allows to express parametric timing constraints on the duration (length) of the intervals. We show that checking the existence of a parameter valuation for which a Kripke structure satisfies a PHS formula (model checking), or a PHS formula admits a trace as a model under the homogeneity assumption (satisfiability) is decidable. Moreover, we identify a fragment of PHS which subsumes parametric LTL and for which model checking and satisfiability are shown to be EXPSPACE-complete., In Proceedings GandALF 2022, arXiv:2209.09333

Temporal moment localization (TML) aims to retrieve the temporal interval for a moment semantically relevant to a sentence query. This is challenging because it requires understanding a video, a sentence, and the relationship between them. Existing TML methods have shown impressive performances by modeling interactions between videos and sentences using fine-grained techniques. However, these fine-grained techniques require a high computational overhead, making them impractical. This work proposes an effective and efficient multi-perspective attention network for temporal moment localization. Inspired by the way humans understand an image from multiple perspectives and different contexts, we devise a novel multi-perspective attention mechanism consisting of perspective attention and multi-perspective modal interactions. Specifically, a perspective attention layer based on multi-head attention takes two memory sequences, one as the base and the other as the reference memory, as inputs. Perspective attention assesses the two different memories, models the relationship, and encourages the base memory to focus on features related to the reference memory, providing an understanding of the base memory from the perspective of the reference memory. Furthermore, multi-perspective modal interactions model the complex relationship between a video and sentence query, and obtain the modal-interacted memory, consisting of a visual feature that selectively learned query-related information. Similar to the heavyweight fine-grained TML methods, the proposed network obtains the accurate complex relationship while being lightweight like coarse-grained TML methods. We also adopt a fast action recognition network to efficiently extract visual features, which reduce the computational overhead. Through experiments on three TML benchmark datasets, we demonstrate the effectiveness and efficiency of the proposed network.

When analyzing temporal networks, a fundamental task is the identification of dense structures (i.e., groups of vertices that exhibit a large number of links), together with their temporal span (i.e., the period of time for which the high density holds). In this paper we tackle this task by introducing a notion of temporal core decomposition where each core is associated with two quantities, its coreness, which quantifies how densely it is connected, and its span, which is a temporal interval: we call such cores \emph{span-cores}. For a temporal network defined on a discrete temporal domain $T$, the total number of time intervals included in $T$ is quadratic in $|T|$, so that the total number of span-cores is potentially quadratic in $|T|$ as well. Our first main contribution is an algorithm that, by exploiting containment properties among span-cores, computes all the span-cores efficiently. Then, we focus on the problem of finding only the \emph{maximal span-cores}, i.e., span-cores that are not dominated by any other span-core by both their coreness property and their span. We devise a very efficient algorithm that exploits theoretical findings on the maximality condition to directly extract the maximal ones without computing all span-cores. Finally, as a third contribution, we introduce the problem of \emph{temporal community search}, where a set of query vertices is given as input, and the goal is to find a set of densely-connected subgraphs containing the query vertices and covering the whole underlying temporal domain $T$. We derive a connection between this problem and the problem of finding (maximal) span-cores. Based on this connection, we show how temporal community search can be solved in polynomial-time via dynamic programming, and how the maximal span-cores can be profitably exploited to significantly speed-up the basic algorithm., Comment: ACM Transactions on Knowledge Discovery from Data (TKDD), 2020. arXiv admin note: substantial text overlap with arXiv:1808.09376

Knowledge, in practice, is time-variant and many relations are only valid for a certain period of time. This phenomenon highlights the importance of harvesting temporal-aware knowledge, i.e., the relational facts coupled with their valid temporal interval. Inspired by pattern-based information extraction systems, we resort to temporal patterns to extract time-aware knowledge from free text. However, pattern design is extremely laborious and time consuming even for a single relation, and free text is usually ambiguous which makes temporal instance extraction extremely difficult. Therefore, in this work, we study the problem of temporal knowledge extraction with two steps: (1) temporal pattern extraction by automatically analysing a large-scale text corpus with a small number of seed temporal facts, (2) temporal instance extraction by applying the identified temporal patterns. For pattern extraction, we introduce various techniques, including corpus annotation, pattern generation, scoring and clustering, to improve both accuracy and coverage of the extracted patterns. For instance extraction, we propose a double-check strategy to improve the accuracy and a set of node-extension rules to improve the coverage. We conduct extensive experiments on real world datasets and compared with state-of-the-art systems. Experimental results verify the effectiveness of our proposed methods for temporal knowledge harvesting.

Background Cellular automata (CA)-based models have been extensively used in urban sprawl modeling. Presently, most studies focused on the improvement of spatial representation in the modeling, with limited efforts for considering the temporal context of urban sprawl. In this paper, we developed a Logistic-Trend-CA model by proposing a trend-adjusted neighborhood as a weighting factor using the information of historical urban sprawl and integrating this factor in the commonly used Logistic-CA model. We applied the developed model in the Beijing-Tianjin-Hebei region of China and analyzed the model performance to the start year, the suitability surface, and the neighborhood size. Results Our results indicate the proposed Logistic-Trend-CA model outperforms the traditional Logistic-CA model significantly, resulting in about 18% and 14% improvements in modeling urban sprawl at medium (1 km) and fine (30 m) resolutions, respectively. The proposed Logistic-Trend-CA model is more suitable for urban sprawl modeling over a long temporal interval than the traditional Logistic-CA model. In addition, this new model is not sensitive to the suitability surface calibrated from different periods and spaces, and its performance decreases with the increase of the neighborhood size. Conclusion The proposed model shows potential for modeling future urban sprawl spanning a long period at regional and global scales.

We study an extension of temporal logic, a multi-agent logic on models with nontransitive linear time (which is, in a sense, also an extension of interval logic). The proposed relational models admit lacunas in admissibility relations among agents: information accessible for one agent may be inaccessible for others. A logical language uses temporary operators ‘until’ and ‘next’ (for each of the agents), via which we can introduce modal operations ‘possible’ and ‘necessary.’ The main problem under study for the logic introduced is the recognition problem for admissibility of inference rules. Previously, this problem was dealt with for a logic in which transitivity intervals have a fixed uniform length. Here the uniformity of length is not assumed, and the logic is extended by individual temporal operators for different agents. An algorithm is found which decides the admissibility problem in a given logic, i.e., it recognizes admissible inference rules.

Visual and central attention are limited in capacity. In conjunction search, visual attention is required to select the items and to bind their features (e.g., color, form, size), which results in a serial search process. In dual-tasks, central attention is required for response selection, but because central attention is limited in capacity, response selection can only be carried out for one task at a time. Here, we investigated whether visual and central attention rely on a common or on distinct capacity limitations. In two dual-task experiments, participants completed an auditory two-choice discrimination Task 1 and a conjunction search Task 2 that were presented with an experimentally modulated temporal interval between them (stimulus onset asynchrony [SOA]). In Experiment 1, Task 2 was a triple conjunction search task. Each item consisted of a conjunction of three features, so that target and distractors shared two features. In Experiment 2, Task 2 was a plus conjunction search task, in which target and distractors shared the same four features. The hypotheses for conjunction search time were derived from the locus-of-slack method. While plus conjunction search was performed after response selection in Task 1, a small part of triple conjunction search was still performed in parallel to response selection in Task 1. However, the between-experiment comparison was not significant, indicating that both search tasks may require central attention. Taken together, the present study provides evidence that visual and central attention share a common capacity limitation when conjunction search relies strongly on serial item selection.