We show that the existential fragment of Buchi arithmetic is strictly less expressive than full Buchi arithmetic of any base, and moreover establish that its Sigma(2)-fragment is already expressively complete. Further...
详细信息
ISBN:
(数字)9783030719951
ISBN:
(纸本)9783030719951;9783030719944
We show that the existential fragment of Buchi arithmetic is strictly less expressive than full Buchi arithmetic of any base, and moreover establish that its Sigma(2)-fragment is already expressively complete. Furthermore, we show that regular languages of polynomial growth are definable in the existential fragment of Buchi arithmetic.
We introduce a formal language for specifying dynamic updates for software Defined Networks. Our language builds upon Network Kleene Algebra with Tests (NetKAT) and adds constructs for synchronisations and multi-packe...
详细信息
ISBN:
(数字)9783030992538
ISBN:
(纸本)9783030992538;9783030992521
We introduce a formal language for specifying dynamic updates for software Defined Networks. Our language builds upon Network Kleene Algebra with Tests (NetKAT) and adds constructs for synchronisations and multi-packet behaviour to capture the interaction between the control- and data-plane in dynamic updates. We provide a sound and ground-complete axiomatisation of our language. We exploit the equational theory and provide an efficient method for reasoning about safety properties. We implement our equational theory in DyNetiKAT - a tool prototype, based on the Maude Rewriting Logic and the NetKAT tool, and apply it to a case study. We show that we can analyse the case study for networks with hundreds of switches using our tool prototype.
this paper discusses a number of methods to prove termination of higher-order term rewriting systems, with a particular focus on large systems. In first-order term rewriting, the dependency pair framework can be used ...
详细信息
Existing graph transformation (GT) tools treat graphs as ephemeral data structures, i.e., the successful application of a GT rule to a graph G rewrites that graph to produce a modified graph G'. the original graph...
详细信息
ISBN:
(纸本)9783031098437;9783031098420
Existing graph transformation (GT) tools treat graphs as ephemeral data structures, i.e., the successful application of a GT rule to a graph G rewrites that graph to produce a modified graph G'. the original graph G is lost during that update. In contrast to ephemeral data structures, persistent data structures preserve access to all previous versions when data is modified and fully persistent data structures even allow all previous versions to be modified. In earlier work, we introduced the Graph Rewriting and Persistence Engine Grape as a tool for specifying and executing transformations on large-scale graphs and integrated it with a computational notebook platform (GrapePress). While the term "persistence" has been in the tool's acronym from the start, it was chosen to indicate that graphs were maintained in a database with transactional support. Until now, Grape (and GrapePress) treated graphs as ephemeral data structures, i.e., previous graph versions were not retained upon modification. this paper presents a major revision of the tool (called GrapeVine) to support functional graph rewriting based on a fully persistent data structure.
Nowadays, different perovskite structures are widely investigated because they can be potentially used in many branches of industry. If two materials are deposited alternately on a substrate, then a superlattice havin...
详细信息
Deploying 5G networks in urban areas is crucial for meeting the increasing demand for high-speed, low-latency wireless communications. However, the complex topography and diverse building structures in urban environme...
详细信息
ISBN:
(纸本)9783031611360;9783031611377
Deploying 5G networks in urban areas is crucial for meeting the increasing demand for high-speed, low-latency wireless communications. However, the complex topography and diverse building structures in urban environments have challenges in identifying suitable locations for base stations. this research explores leveraging deep learning neural networks to analyze satellite imagery, creating a predictive tool for identifying potential rooftop locations. Integrating these predictions into a user-friendly desktop application simplifies the site selection process, reducing the need for costly and labor-intensive site visits in 5G network deployment. this approach democratizes the deployment process, making it accessible to a broader audience. the combination of advanced technology and satellite imagery offers a promising solution to efficiently deploy 5G base stations in urban landscapes, contributing to the widespread adoption of this technology in densely populated areas and advancing 5G connectivity globally.
We define nominal equational problems of the form E (W) over bar for all(Y) over bar : P, where P consists of conjunctions and disjunctions of equations s approximate to(alpha) t, freshness constraints a#t and their n...
详细信息
ISBN:
(数字)9783030719951
ISBN:
(纸本)9783030719951;9783030719944
We define nominal equational problems of the form E (W) over bar for all(Y) over bar : P, where P consists of conjunctions and disjunctions of equations s approximate to(alpha) t, freshness constraints a#t and their negations: s not approximate to(alpha) t and a # t, where a is an atom and s, t nominal terms. We give a general definition of solution and a set of simplification rules to compute solutions in the nominal ground term algebra. For the latter, we define notions of solved form from which solutions can be easily extracted and show that the simplification rules are sound, preserving, and complete. With a particular strategy for rule application, the simplification process terminates and thus specifies an algorithm to solve nominal equational problems. these results generalise previous results obtained by Comon and Lescanne for first-order languages to languages with binding operators. In particular, we show that the problem of deciding the validity of a first-order equational formula in a language with binding operators (i.e., validity modulo alpha-equality) is decidable.
this paper presents a data management model targeting heterogeneous distributed systems integrating reconfigurable accelerators. the purpose of this model is to reduce the complexity of developing applications with mu...
详细信息
ISBN:
(纸本)9783031061561;9783031061554
this paper presents a data management model targeting heterogeneous distributed systems integrating reconfigurable accelerators. the purpose of this model is to reduce the complexity of developing applications with multidimensional sparse data structures. It relies on a shared memory paradigm, which is convenient for parallel programming of irregular applications. the distributed data, sliced in chunks, are managed by a software-Distributed Shared Memory (S-DSM). the integration of reconfigurable accelerators in this S-DSM, by breaking the master-slave model, allows devices to initiate access to chunks in order to accept data-dependent accesses. We use chunk partitioning of multidimensional sparse data structures, such as sparse matrices and unstructured meshes, to access them as a continuous data stream. this model enables to regularize memory accesses of irregular applications, to avoid the transfer of unnecessary data by providing fine-grained data access, and to efficiently hide data access latencies by implicitly overlaying the transferred data flow withthe processed data flow. We have used two case studies to validate the proposed data management model: General Sparse Matrix-Matrix Multiplication (SpGEMM) and Shallow Water Equations (SWE) over an unstructured mesh. the results obtained show that the proposed model efficiently hides the data access latencies by reaching computation speeds close to those of an ideal case (i.e. without latency).
Probabilistic Buchi automata are a natural generalization of PFA to infinite words, but have been studied in-depth only rather recently and many interesting questions are still open. PBA are known to accept, in genera...
详细信息
ISBN:
(纸本)9783030452315;9783030452308
Probabilistic Buchi automata are a natural generalization of PFA to infinite words, but have been studied in-depth only rather recently and many interesting questions are still open. PBA are known to accept, in general, a class of languages that goes beyond the regular languages. In this work we extend the known classes of restricted PBA which are still regular, strongly relying on notions concerning ambiguity in classical omega-automata. Furthermore, we investigate the expressivity of the not yet considered but natural class of weak PBA, and we also show that the regularity problem for weak PBA is undecidable.
暂无评论