检索结果-内蒙古大学图书馆

38th IEEE/ACM International Conference on Automated Software Engineering (ASE)

作者： Samuel, Stanly D'Souza, Deepak Komondoor, Raghavan Indian Inst Sci Comp Sci & Automat Bengaluru India

ISBN: (纸本)9798350329964

Two-player games are a fruitful way to represent and reason about several important synthesis tasks. These tasks include controller synthesis (where one asks for a controller for a given plant such that the controlled plant satisfies a given temporal specification), program repair (setting values of variables to avoid exceptions), and synchronization synthesis (adding lock/unlock statements in multi-threaded programs to satisfy safety assertions). In all these applications, a solution directly corresponds to a winning strategy for one of the players in the induced game. In turn, logically-specified games offer a powerful way to model these tasks for large or infinitestate systems. Much of the techniques proposed for solving such games typically rely on abstraction-refinement or template-based solutions. In this paper, we show how to apply classical fixpoint algorithms, that have hitherto been used in explicit, finite-state, settings, to a symbolic logical setting. We implement our techniques in a tool called GENSYS-LTL and show that they are not only effective in synthesizing valid controllers for a variety of challenging benchmarks from the literature, but often compute maximal winning regions and maximally-permissive controllers. We achieve 46.38X speed-up over the state of the art and also scale well for non-trivial LTL specifications.

关键词： reactive synthesis symbolic algorithms program synthesis program repair two-player games

来源：评论

学校读者我要写书评

暂无评论

symbolic algorithms Computing Gram Congruences in the Coxeter Spectral Classification of Edge-bipartite Graphs, II. Isotropy Mini-groups

引用

FUNDAMENTA INFORMATICAE 2016年第1期145卷 49-80页

作者： Simson, Daniel Nicolaus Copernicus Univ Fac Math & Comp Sci Ul Chopina 12-18 PL-87100 Torun Poland

In this two parts article with the same title we continue the Coxeter spectral study of the category UBigr(m) of loop-free edge-bipartite (signed) graphs Delta, with m >= 2 vertices, we started in [SIAM J. Discr. Math. 27(2013), 827-854] for corank r = 0 and r = 1. Here we study the class of all non-negative edge-bipartite graphs Delta is an element of UBigr(n+r) of corank r >= 0, up to a pair of the Gram Z-congruences similar to Z and approximate to Z, by means of the non-symmetric Gram matrix G(Delta) is an element of Mn+r (Z) of Delta, the symmetric Gram matrix G(Delta) : = 1/2 [G(Delta) broken vertical bar G(Delta)(tr)] is an element of Mn+r(Z), the Coxeter matrix Cox(Delta) := G(Delta) . G(Delta)(-tr) is an element of Mn+r(Z), its spectrum specc(Delta) subset of C, called the Coxeter spectrum of Delta, and the Dynkin type Dyn(Delta) is an element of {A(n), D-n, E-6;E-7;E-8} associated in Part 1 of this paper. One of the aims in the study of the category UBigr(n+r) is to classify the equivalence classes of the non-negative edge-bipartite graphs in UBigr(n+r) with respect to each of the Gram congruences similar to Z and approximate to Z. In particular, the Coxeter spectral analysis question, when the congruence Delta approximate to(Z) Delta' holds (hence also Delta similar to(Z) Delta' holds), for a pair of connected non-negative graphs Delta,Delta' is an element of UBigr(n+r) such that specc(Delta) = specc(Delta') and Dyn(Delta) = Dyn(Delta'), is studied in the paper. One of our main aims in this Part 2 of the paper is to get an algorithmic description of a matrix B defining the strong Gram Z-congruence Delta approximate to(Z) Delta', that is, a Z-invertible matrix B is an element of Mn+r (Z) such that G(Delta') = B-tr . G(Delta) . B. We obtain such a description for a class of non-negative connected edge-bipartite graphs Delta is an element of UBigr(n+r) of corank r = 0 and r = 1. In particular, we construct symbolic algorithms for the calculation of the isotro

关键词： signed graph Gram congruence Coxeter spectrum symbolic algorithms Cartan matrix Coxeter-Dynkin type isotropy mini-group

来源：评论

学校读者我要写书评

暂无评论

Fast symbolic Computation of Bottom SCCs 30th

Fast Symbolic Computation of Bottom SCCs

引用

30th International Conference on Tools and algorithms for the Construction and Analysis of Systems (TACAS) Held as Part of the 27th European Joint Conferences on Theory and Practice of Software (ETAPS)

作者： Jakobsen, Anna Blume Jorgensen, Rasmus Skibdahl Melanchton van de Pol, Jaco Pavlogiannis, Andreas Aarhus Univ Aarhus Denmark

ISBN: (纸本)9783031572555;9783031572562

The computation of bottom strongly connected components (BSCCs) is a fundamental task in model checking, as well as in characterizing the attractors of dynamical systems. As such, symbolic algorithms for BSCCs have received special attention, and are based on the idea that the computation of an SCC can be stopped early, as soon as it is deemed to be non-bottom. In this paper we introduce Pendant, a new symbolic algorithm for computing BSCCs which runs in linear symbolic time. In contrast to the standard approach of escaping non-bottom SCCs, Pendant aims to start the computation from nodes that are likely to belong to BSCCs, and thus is more effective in sidestepping SCCs that are non-bottom. Moreover, we employ a simple yet powerful deadlock-detection technique, that quickly identifies singleton BSCCs before the main algorithm is run. Our experimental evaluation on three diverse datasets of 553 models demonstrates the efficacy of our two methods: Pendant is decisively faster than the standard existing algorithm for BSCC computation, while deadlock detection improves the performance of each algorithm significantly.

关键词： BDDs strongly connected components symbolic algorithms

来源：评论

学校读者我要写书评

暂无评论

symbolic algorithms for qualitative analysis of Markov decision processes with Buchi objectives

引用

FORMAL METHODS IN SYSTEM DESIGN 2013年第3期42卷 301-327页

作者： Chatterjee, Krishnendu Henzinger, Monika Joglekar, Manas Shah, Nisarg IST Austria Klosterneuburg Austria Univ Vienna Vienna Austria Stanford Univ Palo Alto CA 94304 USA Carnegie Mellon Univ Pittsburgh PA 15213 USA

We consider Markov decision processes (MDPs) with Buchi (liveness) objectives. We consider the problem of computing the set of almost-sure winning states from where the objective can be ensured with probability 1. Our contributions are as follows: First, we present the first subquadratic symbolic algorithm to compute the almost-sure winning set for MDPs with Buchi objectives;our algorithm takes symbolic steps as compared to the previous known algorithm that takes O(n (2)) symbolic steps, where n is the number of states and m is the number of edges of the MDP. In practice MDPs have constant out-degree, and then our symbolic algorithm takes symbolic steps, as compared to the previous known O(n (2)) symbolic steps algorithm. Second, we present a new algorithm, namely win-lose algorithm, with the following two properties: (a) the algorithm iteratively computes subsets of the almost-sure winning set and its complement, as compared to all previous algorithms that discover the almost-sure winning set upon termination;and (b) requires symbolic steps, where K is the maximal number of edges of strongly connected components (scc's) of the MDP. The win-lose algorithm requires symbolic computation of scc's. Third, we improve the algorithm for symbolic scc computation;the previous known algorithm takes linear symbolic steps, and our new algorithm improves the constants associated with the linear number of steps. In the worst case the previous known algorithm takes 5a <...n symbolic steps, whereas our new algorithm takes 4a <...n symbolic steps.

关键词： Markov decision processes Probabilistic verification Buchi objectives symbolic algorithms

来源：评论

学校读者我要写书评

暂无评论

Elementary Matrix-computational Proof of Quillen-Suslin Theorem for Ore Extensions

引用

FUNDAMENTA INFORMATICAE 2019年第1期164卷 41-59页

作者： Fajardo, William Lezama, Oswaldo Univ Nacl Colombia Dept Math Bogota Colombia

In this short note we present an elementary matrix-constructive algorithmic proof of the Quillen-Suslin theorem for Ore extensions A := K [x;sigma, delta], where K is a division ring, sigma : K -> K is a division ring automorphism and delta : K -> K is a a-derivation of K. It asserts that every finitely generated projective A-module is free. We construct a symbolic algorithm that computes the basis of a given finitely generated projective A-module. The algorithm is implemented in a computational package. Its efficiency is illustrated by four representative examples.

关键词： symbolic algorithms Maple non-commutative computational algebra projective modules Ore extensions

来源：评论

学校读者我要写书评

暂无评论

symbolic Limited Lookahead Control for Best-effort Dynamic Computing Resource Management

引用

IFAC-PapersOnLine 2018年第7期51卷 112-119页

作者： Berthier, Nicolas Marchand, Hervé Rutten, Éric Department of Computer Science University of Liverpool United Kingdom INRIA Rennes - Bretagne Atlantique France Univ. Grenoble Alpes Inria CNRS Grenoble INP LIG GrenobleF-38000 France

We put forward a new modeling technique for Dynamic Resource Management (DRM) based on discrete events control for symbolic logico-numerical systems, especially Discrete Controller Synthesis (DCS). The resulting models involve state and input variables defined on an infinite domain (Integers), thereby no exact DCS algorithm exists for safety control. We thus formally define the notion of limited lookahead, and associated best-effort control objectives targeting safety and optimization on a sliding window for a number of steps ahead. We give symbolic algorithms, illustrate our approach on an example model for DRM, and report on performance results based on an implementation in our tool ReaX. © 2018

关键词： Resource allocation Discrete event simulation Natural resources management Computing resource management Discrete controller synthesis Dynamic resource management Infinite state systems Look ahead control Modeling technique Supervisory control symbolic algorithms

来源：评论

学校读者我要写书评

暂无评论

symbolic Algorithm for Generating the Orthonormal Bargmann-Moshinsky Basis for SU(3) Group 1

引用

20th International Workshop on Computer Algebra in Scientific Computing (CASC)

作者： Deveikis, A. Gusev, A. A. Gerdt, V. P. Vinitsky, S. I. Gozdz, A. Pedrak, A. Vytautas Magnus Univ Dept Appl Informat Kaunas Lithuania Joint Inst Nucl Res Dubna Russia RUDN Univ 6 Miklukho Maklaya Moscow 117198 Russia Marie Curie Sklodowska Univ Inst Phys Lublin Poland Natl Ctr Nucl Res Warsaw Poland

ISBN: (数字)9783319996394

ISBN: (纸本)9783319996394;9783319996387

A symbolic algorithm which can be implemented in any computer algebra system for generating the Bargmann-Moshinsky (BM) basis with the highest weight vectors of SO(3) irreducible representations is presented. The effective method resulting in analytical formula of overlap integrals in the case of the non-canonical BM basis [S. Alisauskas, P. Raychev, R. Roussev, J. Phys. G 7, 1213 (1981)] is used. A symbolic recursive algorithm for orthonormalisation of the obtained basis is developed. The effectiveness of the algorithms implemented in Mathematica 10.1 is investigated by calculation of the overlap integrals for up to mu = 5 with lambda > mu and orthonormalization of the basis for up to mu = 4 with lambda > mu. The action of the zero component of the quadrupole operator onto the basis vectors with mu = 4 is also obtained.

关键词： SU(3) non-canonical basis Group theory Gram-Schmidt orthonormalization symbolic algorithms

来源：评论

学校读者我要写书评

暂无评论

Layering Assume-Guarantee Contracts for Hierarchical System Design

引用

PROCEEDINGS OF THE IEEE 2018年第9期106卷 1616-1654页

作者： Filippidis, Ioannis Murray, Richard M. CALTECH Control & Dynam Syst Dept Pasadena CA 91125 USA

Specifications for complex engineering systems are typically decomposed into specifications for individual subsystems in a manner that ensures they are implementable and simpler to develop further. We describe a method to algorithmically construct component specifications that implement a given specification when assembled. By eliminating variables that are irrelevant to realizability of each component, we simplify the specifications and reduce the amount of information necessary for operation. We parametrize the information flow between components by introducing parameters that select whether each variable is visible to a component. The decomposition algorithm identifies which variables can be hidden while preserving realizability and ensuring correct composition, and these are eliminated from component specifications by quantification and conversion of binary decision diagrams to formulas. The resulting specifications describe component viewpoints with full information with respect to the remaining variables, which is essential for tractable algorithmic synthesis of implementations. The specifications are written in TLA(+), with liveness properties restricted to an implication of conjoined recurrence properties, known as GR(1). We define an operator for forming open systems from closed systems, based on a variant of the "while-plus" operator. This operator simplifies the writing of specifications that are realizable without being vacuous. To convert the generated specifications from binary decision diagrams to readable formulas over integer variables, we symbolically solve a minimal covering problem. We show with examples how the method can be applied to obtain contracts that formalize the hierarchical structure of system design.

关键词： Algorithmic game theory assume-guarantee contracts binary decision diagrams formal languages open systems reactive synthesis realizability temporal logic symbolic algorithms system specification TLA

来源：评论

学校读者我要写书评

暂无评论

Integer Parameter Synthesis for Real-Time Systems

引用

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING 2015年第5期41卷 445-461页

作者： Jovanovic, Aleksandra Lime, Didier Roux, Olivier H. Ecole Cent Nantes IRCCyN UMR CNRS 6597 Nantes France

We provide a subclass of parametric timed automata (PTA) that we can actually and efficiently analyze, and we argue that it retains most of the practical usefulness of PTA for the modeling of real-time systems. The currently most useful known subclass of PTA, L/U automata, has a strong syntactical restriction for practical purposes, and we show that the associated theoretical results are mixed. We therefore advocate for a different restriction scheme: since in classical timed automata, real-valued clocks are always compared to integers for all practical purposes, we also search for parameter values as bounded integers. We show that the problem of the existence of parameter values such that some TCTL property is satisfied is PSPACE-complete. In such a setting, we can of course synthesize all the values of parameters and we give symbolic algorithms, for reachability and unavoidability properties, to do it efficiently, i.e., without an explicit enumeration. This also has the practical advantage of giving the result as symbolic constraints between the parameters. We finally report on a few experimental results to illustrate the practical usefulness of our approach.

关键词： Timed automata parameters synthesis model-checking real-time systems symbolic algorithms

来源：评论

学校读者我要写书评

暂无评论

Computing resultants on Graphics Processing Units: Towards GPU-accelerated computer algebra

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2013年第11期73卷 1494-1505页

作者： Emeliyanenko, Pavel Max Planck Inst Informat D-66123 Saarbrucken Germany

In this article we report on our experience in computing resultants of bivariate polynomials on Graphics Processing Units (GPU). Following the outline of Collins' modular approach [6], our algorithm starts by mapping the input polynomials to a finite field for sufficiently many primes m. Next, the GPU algorithm evaluates the polynomials at a number of fixed points x is an element of Z(m), and computes a set of univariate resultants for each modular image. Afterwards, the resultant is reconstructed using polynomial interpolation and Chinese remaindering. The GPU returns resultant coefficients in the form of Mixed Radix (MR) digits. Finally, large integer coefficients are recovered from the MR representation on the CPU. All computations performed by the algorithm (except for, partly, Chinese remaindering) are outsourced to the graphics processor thereby minimizing the amount of work to be done on the host machine. The main theoretical contribution of this work is the modification of Collins' modular algorithm using the methods of matrix algebra to make an efficient realization on the GPU feasible. According to the benchmarks, our algorithm outperforms a CPU-based resultant algorithm from 64-bit Maple 14 by a factor of 100. (C) 2012 Elsevier Inc. All rights reserved.

关键词： symbolic algorithms Resultants Modular computations GPU CUDA Parallel computing

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：