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

Linear time analysis of properties of conflict-free and general Petri nets

THEORETICAL COMPUTER SCIENCE 2011年第4-5期412卷 320-338页

作者： Alimonti, Paola Feuerstein, Esteban Laura, Luigi Nanni, Umberto Univ Roma La Sapienza Dipartimento Informat & Sistemist Antonio Ruberti I-00185 Rome Italy Univ Buenos Aires Dept Computac RA-1428 Buenos Aires DF Argentina

We introduce the notion of a T-path within Petri nets, and propose to adopt the model of directed hypergraphs in order to determine properties of nets: in particular, we study the relationships between T-paths and firable sequences of transitions. Let us consider a Petri net P = < P, T, A, M-0 > and the set of places with a positive marking in M-0, i.e., P-0 = {p vertical bar M-0(p) > 0}. If we regard the net as a directed graph, the existence of a simple path from any place in P-0 to a transition t is, of course, a necessary condition for the potential firability of t. This is sufficient only if the net is a state machine, where vertical bar(center dot)t vertical bar = vertical bar t(center dot)vertical bar = 1 for all t epsilon T. In this paper we show that the existence of a T-path from any subset of P-0 to a transition t is a more restrictive condition and is, again, a necessary condition for the potential firability of t. But, in this case: (a) if P is a conflict-free Petri net, this is also a sufficient condition, (b) if P is a general Petri net, t is potentially firable by increasing the number of tokens in P-0. For conflict-free nets (CFPN) we consider the following problems: (a) determining the set of firable transitions, (b) determining the set of covetable places, (c) determining the set of live transitions, (d) deciding the boundedness of the net. For all these problems we provide algorithms requiring linear space and time, i.e., O(vertical bar p vertical bar + vertical bar T vertical bar + vertical bar A vertical bar), for a net P = < P, T, A. M-0 >. Previous results for this class of networks are given by Howell et al. (1987) [20], providing algorithms for solving problems in conflict-free nets in O(vertical bar p vertical bar x vertical bar T vertical bar ) time and space. Given a Petri net and a marking M, the well-known coverability problem consists in finding a reachable marking M` such that M` >= M;this problem is known to be EXPSPACE hard (Rackof

关键词： Petri nets Conflict-free Petri nets Marked graphs Coverability Liveness Boundedness Directed hypergraphs incremental algorithms

来源：评论

学校读者我要写书评

暂无评论

Automated meta-control for adaptable real-time software

引用

REAL-TIME SYSTEMS 1998年第2期14卷 107-134页

作者： Jehuda, J Israeli, A Technion Israel Inst Technol Dept Elect Engn IL-31021 Haifa Israel Netanya Acad Coll Sch Comp Sci & Math IL-42100 Nethanya Israel

The software meta-controller is an online agent responsible for dynamically adapting an application's software configuration, e.g. altering operational modes and migrating tasks, to best accommodate varying runtime circumstances. In distributed real-time applications such adaptations must be carried out in a manner which maintains the schedulability of all critical tasks while maximizing some notion of system value for all other tasks. For large-scale real-time applications, considering all possible adaptations at the task-level is computationally intractable. This paper presents an automated aggregate approach to software meta-control, appropriate for large-scale distributed real-time systems. The aggregate automated meta-control problem is !;till NP-hard, but it has very practical approximate solutions. Introduced, here, are two very-effective approximation algorithms, QDP and G(2), with very reasonable polynomial time complexity. Both algorithms also provide us with upper bounds for optimum system values, useful for deriving absolute, albeit somewhat pessimistic, measures of actual performance. Extensive Monte Carlo analysis is used to illustrate that expected performance for both algorithms is generally suboptimal by no more than a few percent. Our flexible software meta-control model is also shown to be readily applied to a wide range of time-sensitive applications.

关键词： real-time software online adaptation software meta-control approximate optimization knapsack binpack dynamic programming gradient-greedy Monte Carlo analysis incremental algorithms

来源：评论

学校读者我要写书评

暂无评论

Learning model trees from evolving data streams

引用

DATA MINING AND KNOWLEDGE DISCOVERY 2011年第1期23卷 128-168页

作者： Ikonomovska, Elena Gama, Joao Dzeroski, Saso Jozef Stefan Inst Ljubljana 1000 Slovenia Univ Porto LIAAD INESC P-4050190 Oporto Portugal Univ Porto Fac Econ P-4200 Oporto Portugal Ss Cyril & Methodius Univ Fac Elect Engn & Informat Technol Skopje 1000 Macedonia

The problem of real-time extraction of meaningful patterns from time-changing data streams is of increasing importance for the machine learning and data mining communities. Regression in time-changing data streams is a relatively unexplored topic, despite the apparent applications. This paper proposes an efficient and incremental stream mining algorithm which is able to learn regression and model trees from possibly unbounded, high-speed and time-changing data streams. The algorithm is evaluated extensively in a variety of settings involving artificial and real data. To the best of our knowledge there is no other general purpose algorithm for incremental learning regression/model trees able to perform explicit change detection and informed adaptation. The algorithm performs online and in real-time, observes each example only once at the speed of arrival, and maintains at any-time a ready-to-use model tree. The tree leaves contain linear models induced online from the examples assigned to them, a process with low complexity. The algorithm has mechanisms for drift detection and model adaptation, which enable it to maintain accurate and updated regression models at any time. The drift detection mechanism exploits the structure of the tree in the process of local change detection. As a response to local drift, the algorithm is able to update the tree structure only locally. This approach improves the any-time performance and greatly reduces the costs of adaptation.

关键词： Non-stationary data streams Stream data mining Regression trees Model trees incremental algorithms On-line learning Concept drift On-line change detection

来源：评论

学校读者我要写书评

暂无评论

Three-way decisions method based on matrices approaches oriented dynamic interval-valued information system

引用

INTERNATIONAL JOURNAL OF APPROXIMATE REASONING 2022年第0期149卷 116-130页

作者： Shi, Ji Suo, Zhongying Air Force Engn Univ Grad Sch Xian 710000 Shaanxi Peoples R China Air Force Engn Univ Fundamentals Dept Xian 710000 Shaanxi Peoples R China

Interval-valued Information Systems (IvIS) reflect the uncertain information in real scene, in which the attribute value of objects are all interval values rather than single values. Data information analysed by three-way decisions is not static but dynamically changing in IvIS, which results in the updating of positive region, boundary region and negative region of decision class X. In this paper, a matrix computational framework based on lambda-similarity relation is proposed on the variation of the attribute set, attribute value and object set. Based on the framework, some incremental algorithms are proposed to calculate the positive, boundary and negative region of X in dynamic IvIS. Finally, comparative experiments on data sets from UCI are conducted when attribute set, attribute value and object set are updating over time, respectively. Experimental results show that in comparison with the traditional algorithm, the proposed algorithms can effectively save time for the computation of positive, boundary and negative region of X in dynamic IvIS. (C) 2022 Elsevier Inc. All rights reserved.

关键词： Interval-valued Information Systems (IvIS) lambda-similarity relation Matrix computational framework incremental algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for Dynamic Incomplete Decision Systems

引用

INTERNATIONAL JOURNAL OF DATA WAREHOUSING AND MINING 2021年第3期17卷 44-67页

作者： Thang, Nguyen Truong Nguyen, Giang Long Long, Hoang Viet Tuan, Nguyen Anh Tran, Tuan Manh Tan, Ngo Duy Vietnam Acad Sci & Technol Inst Informat Technol Hanoi Vietnam Peoples Police Univ Technol & Logist Hanoi Vietnam VinhPhuc Coll Vinh Phuc Vietnam Thuyloi Univ Fac Comp Sci & Engn Hanoi Vietnam

Attribute reduction is a crucial problem in the process of data mining and knowledge discovery in big data. In incomplete decision systems, the model using tolerance rough set is fundamental to solve the problem by computing the redact to reduce the execution time. However, these proposals used the traditional filter approach so that the reduct was not optimal in the number of attributes and the accuracy of classification. The problem is critical in the dynamic incomplete decision systems which are more appropriate for real-world applications. Therefore, this paper proposes two novel incremental algorithms using the combination of filter and wrapper approach, namely IFWA_ADO and IFWA_DEO, respectively, for the dynamic incomplete decision systems. The IFWA_ADO computes reduct incrementally in cases of adding multiple objects while IFWA_DEO updates reduct when removing multiple objects. These algorithms are also verified on six data sets. Experimental results show that the filter-wrapper algorithms get higher performance than the other filter incremental algorithms.

关键词： Incomplete Decision Systems incremental algorithms Metric Reduct Tolerance Rough Set

来源：评论

学校读者我要写书评

暂无评论

Two algorithms for LCS consecutive suffix alignment

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2007年第7期73卷 1095-1117页

作者： Landau, Gad M. Myers, Eugene Ziv-Ukelson, Michal Univ Haifa Dept Comp Sci IL-31905 Haifa Israel Polytech Univ MetroTech Ctr 6 Dept Comp & Informat Sci Brooklyn NY 11201 USA Univ Calif Berkeley Dept Comp Sci Berkeley CA 94720 USA Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

The problem of aligning two sequences A and B to determine their similarity is one of the fundamental problems in pattern matching. A challenging, basic variation of the sequence similarity problem is the incremental string comparison problem, denoted Consecutive Suffix Alignment, which is, given two strings A and B, to compute the alignment solution of each suffix of A versus B. Here, we present two solutions to the Consecutive Suffix Alignment Problem under the LCS (Longest Common Subsequence) metric, where the LCS metric measures the subsequence of maximal length common to A and B. The first solution is an O(nL) time and space algorithm-for constant alphabets, where the size of the compared strings is O(n) and L <= n denotes the size of the LCS of A and B. The second solution is an O(nL +n log vertical bar Sigma vertical bar) time and O(n) space algorithm for general alphabets, where Sigma denotes the alphabet of the compared strings. (c) 2007 Elsevier Inc. All rights reserved.

关键词： dynamic programming longest common subsequence match point arithmetic incremental algorithms

来源：评论

学校读者我要写书评

暂无评论

Interactive authoring of multimedia documents in a constraint-based authoring system

引用

MULTIMEDIA SYSTEMS 1999年第5期7卷 424-437页

作者： Song, JW Ramalingam, G Miller, R Yi, BK IBM Corp Thomas J Watson Res Ctr Yorktown Heights NY 10598 USA Univ Maryland College Pk MD 20742 USA

As multimedia applications spread widely, it is crucial for programming and design support systems to handle "time" in multimedia documents effectively and flexibly. This paper presents a set of interactive system support tools for designing and maintaining the temporal behavior of multimedia documents. The tool set provides mechanisms for anomaly detection, temporal query processing, and interactive scheduling. It is based on a fast incremental constraint solver we have developed, which can be adapted by any constraint-based system. The incremental constraint solver provides immediate feedback to the user, supporting a highly Interactive design process. Combined with existing optimal layout generation mechanisms proposed in the literature, our tools effectively utilize the flexibility provided by constraint-based systems.

关键词： multimedia documents multimedia authoring interactive systems temporal constraint systems incremental algorithms

来源：评论

学校读者我要写书评

暂无评论

Syntactic-semantic incrementality for agile verification

引用

SCIENCE OF COMPUTER PROGRAMMING 2015年第Part1期97卷 47-54页

作者： Bianculli, Domenico Filieri, Antonio Ghezzi, Carlo Mandrioli, Dino Univ Luxembourg SnT Ctr L-2721 Luxembourg Luxembourg Univ Stuttgart Inst Software Technol D-70569 Stuttgart Germany Politecn Milan DEEPSE Grp Dipartimento Elettron Informaz & Bioingn I-20133 Milan Italy

Modern software systems are continuously evolving, often because systems requirements change over time. Responding to requirements changes is one of the principles of agile methodologies. In this paper we envision the seamless integration of automated verification techniques within agile methodologies, thanks to the support for incrementality. incremental verification accommodates the changes that occur within the schedule of frequent releases of software agile processes. We propose a general approach to developing families of verifiers that can support incremental verification for different kinds of artifacts and properties. The proposed syntactic-semantic approach is rooted in operator precedence grammars and their support for incremental parsing. incremental verification procedures are encoded as attribute grammars, whose incremental evaluation goes hand in hand with incremental parsing. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Agile development Formal verification Operator-precedence grammars Attribute grammars incremental algorithms

来源：评论

学校读者我要写书评

暂无评论

Semi-dynamic breadth-first search in digraphs

引用

THEORETICAL COMPUTER SCIENCE 2001年第1-2期250卷 201-217页

作者： Franciosa, PG Frigioni, D Giaccio, R Univ Roma La Sapienza Dipartimento Informat & Sistemist I-00198 Rome Italy Univ Aquila Dipartimento Ingn Elettr I-67040 Laquila Italy

In this paper we propose dynamic algorithms for maintaining a breadth-first search tree from a given source vertex of a directed graph G in either an incremental or a decremental setting. During a sequence of q edge insertions or a sequence of q edge deletions the total time required is O(m(.)min{q, n}), where n is the number of vertices of G, and m is the final number of edges of G in the case of insertions or the initial number of edges of G in the case of deletions. This gives O(n) amortized time for each operation if the sequence has length Omega (m). Our algorithms require O(n + m) space. These are the first results in the literature concerning the dynamic maintenance of a breadth-first search tree for directed graphs, As a straightforward application of such algorithms we can maintain a shortest path tree for a directed graph in the case of unit edge weights within the same time bounds. In this case distance queries can be answered in constant time, while shortest path queries can be answered in time linear in the length of the retrieved path, (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： breadth-first search tree incremental algorithms decremental algorithms shortest paths amortized analysis

来源：评论

学校读者我要写书评

暂无评论

Localizer

引用

Constraints 2000年第1-2期5卷 43-84页

作者： Michel, Laurent Van, Hentenryck, Pascal Brown University Providence

Local search is a traditional technique to solve combinatorial search problems which has raised much interest in recent years. The design and implementation of local search algorithms is not an easy task in general and may require considerable experimentation and programming effort. However, contrary to global search, little support is available to assist the design and implementation of local search algorithms. This paper describes the design and implementation of LOCALIZER, a modeling language for implementing local search algorithms. LOCALIZER makes it possible to express local search algorithms in a notation close to their informal descriptions in scientific papers. Experimental results on Boolean satisfiability, graph coloring, graph partitioning, and job-shop scheduling show the feasibility of the approach.

关键词： modeling language local search incremental algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：