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

incremental algorithms for solving regular expression intersection non-emptiness

THEORETICAL COMPUTER SCIENCE 2025年 1043卷

作者： Chen, Haiming Huang, Hong Li, Rongchen Peng, Chengyao Su, Weihao Chinese Acad Sci Inst Software Key Lab Syst Software Beijing 100190 Peoples R China Chinese Acad Sci Inst Software State Key Lab Comp Sci Beijing 100190 Peoples R China Univ Chinese Acad Sci Beijing 101400 Peoples R China

The intersection non-emptiness problem of regular languages is one of the most classical and fundamental decision problems in formal language theory, which plays an important role in many areas of computer science. In this paper, we propose five incremental algorithms for checking the intersection of regular expressions, which avoid explicitly constructing automata and use coordinatewise quasi-orders among states to reduce the search space. We conduct experiments and compare the algorithms with seven state-of-the-art tools. The results show advantages of the algorithms over existing methods in terms of efficiency on two real-world benchmarks.

关键词： Regular expressions Intersection non-emptiness Automata Position automaton Continuation incremental algorithms

来源：评论

学校读者我要写书评

暂无评论

incremental algorithms for Safe and Reachable Frontier Detection for robot exploration

引用

ROBOTICS AND AUTONOMOUS SYSTEMS 2015年 72卷 189-206页

作者： Senarathne, P. G. C. N. Wang, Danwei Nanyang Technol Univ Sch Elect & Elect Engn Ctr E City EXQUISITUS Singapore 639798 Singapore

Majority of the autonomous robot exploration strategies operate by iteratively extracting the boundary between the mapped open space and unexplored space, frontiers, and sending the robot towards the "best" frontier. Traditional approaches process the entire map to retrieve the frontier information at each decision step. This operation however is not scalable to large map sizes and high decision frequencies. In this article, a computationally efficient incremental approach, Safe and Reachable Frontier Detection (SRFD), that processes locally updated map data to generate only the safe and reachable (i.e. valid) frontier information is introduced. This is achieved by solving the two sub-problems of a) incrementally updating a database of boundary contours between mapped-free and unknown cells that are safe for robot and b) incrementally identifying the reachability of the contours in the database. Only the reachable boundary contours are extracted as frontiers. Experimental evaluation on real world data sets validate that the proposed incremental update strategy provides a significant improvement in execution time while maintaining the global accuracy of frontier generation. The low computational footprint of proposed frontier generation approach provides the opportunity for exploration strategies to process frontier information at much higher frequencies which could be used to generate more efficient exploration strategies. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Autonomous exploration Frontier detection Reachability detection incremental algorithms Spanning trees

来源：评论

学校读者我要写书评

暂无评论

incremental algorithms for hierarchical classification

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2006年第1期7卷 31-54页

作者： Cesa-Bianchi, N Gentile, C Zaniboni, L Univ Milan Dipartimento Sci Informaz I-20135 Milan Italy Univ Insubria Dipartimento Informat & Comunicaz I-21100 Varese Italy Univ Milan Dipartimento Tecnol IInformaz I-26013 Crema CR Italy

We study the problem of classifying data in a given taxonomy when classifications associated with multiple and/or partial paths are allowed. We introduce a new algorithm that incrementally learns a linear-threshold classifier for each node of the taxonomy. A hierarchical classification is obtained by evaluating the trained node classifiers in a top-down fashion. To evaluate classifiers in our multipath framework, we define a new hierarchical loss function, the H-loss, capturing the intuition that whenever a classification mistake is made on a node of the taxonomy, then no loss should be charged for any additional mistake occurring in the subtree of that node. Making no assumptions on the mechanism generating the data instances, and assuming a linear noise model for the labels, we bound the H-loss of our on-line algorithm in terms of the H-loss of a reference classifier knowing the true parameters of the label-generating process. We show that, in expectation, the excess cumulative H-loss grows at most logarithmically in the length of the data sequence. Furthermore, our analysis reveals the precise dependence of the rate of convergence on the eigenstructure of the data each node observes. Our theoretical results are complemented by a number of experiments on texual corpora. In these experiments we show that, after only one epoch of training, our algorithm performs much better than Perceptron-based hierarchical classifiers, and reasonably close to a hierarchical support vector machine.

关键词： incremental algorithms online learning hierarchical classification second order perceptron support vector machines regret bound loss function

来源：评论

学校读者我要写书评

暂无评论

Novel incremental algorithms for Attribute Reduction From Dynamic Decision Tables Using Hybrid Filter-Wrapper With Fuzzy Partition Distance

引用

IEEE TRANSACTIONS ON FUZZY SYSTEMS 2020年第5期28卷 858-873页

作者： Nguyen Long Giang Le Hoang Son Tran Thi Ngan Tran Manh Tuan Ho Thi Phuong Abdel-Basset, Mohamed de Macedo, Antonio Roberto L. de Albuquerque, Victor Hugo C. Vietnam Acad Sci & Technol Inst Informat Technol Hanoi 100000 Vietnam Vietnam Natl Univ VNU Informat Technol Inst Hanoi 010000 Vietnam Thuyloi Univ Hanoi 116705 Vietnam Tay Nguyen Univ Buon Ma Thuot 630000 Vietnam Zagazig Univ Fac Comp & Informat Zagazig 44519 Egypt Univ Fortaleza BR-60811905 Fortaleza Ceara Brazil

Attribute reduction from decision tables has been much focused in recent years in which the incremental methods of the tradition rough set and extended models are mostly used for adding, removing, or updating the object or attribute set. However, when dealing with the dynamic decision tables, the existing incremental methods do not recalculate information which has been added into the decision table. In this article, we propose some new incremental methods using the hybrid filter-wrapper with fuzzy partition distance on fuzzy rough set. Experimental results indicate that the proposed algorithms decrease significantly the cardinality of reduct as well as achieve higher accuracy than the other filter incremental methods such as IV-FS-FRS-2, IARM, ASS-IAR, IFSA, and IFSD.

关键词： Rough sets Filtering algorithms Partitioning algorithms Classification algorithms Heuristic algorithms Filtering theory Fuzzy sets Attribute reduction decision tables fuzzy distances fuzzy rough sets incremental algorithms

来源：评论

学校读者我要写书评

暂无评论

On the optimality of neural-network approximation using incremental algorithms

引用

IEEE TRANSACTIONS ON NEURAL NETWORKS 2000年第2期11卷 323-337页

作者： Meir, R Maiorov, VE Technion Israel Inst Technol Dept Elect Engn IL-32000 Haifa Israel Technion Israel Inst Technol Dept Math IL-32000 Haifa Israel

The problem of approximating functions by neural networks using incremental algorithms is studied. For functions belonging to a rather general class, characterized by certain smoothness properties with respect to the La norm, we compute upper bounds on the approximation error where error is measured by the L-q norm, 1 less than or equal to q less than or equal to infinity. These results extend previous work? applicable in the case q = 2, and provide an explicit algorithm to achieve the derived approximation error rate. In the range q less than or equal to 2 near-optimal rates of convergence are demonstrated. A gap remains, however, with respect to a recently established lower bound in the case q > 2, although the rates achieved are provably better than those obtained by optimal linear approximation. Extensions of the results from the L-2 norm to L-p are also discussed, A further interesting conclusion from our results is that no loss of generality is suffered using networks with positive hidden-to-output weights. Moreover, explicit bounds on the size of the hidden-to-output weights are established, which are sufficient to guarantee the established convergence rates.

关键词： approximation bounds incremental algorithms neural networks

来源：评论

学校读者我要写书评

暂无评论

Efficiency Guarantees for Parallel incremental algorithms under Relaxed Schedulers 19

Efficiency Guarantees for Parallel Incremental Algorithms un...

引用

31st ACM Symposium on Parallelism in algorithms and Architecturess (SPAA)

作者： Alistarh, Dan Nadiradze, Giorgi Koval, Nikita IST Austria Klosterneuburg Austria IST Austria JetBrains Klosterneuburg Austria

ISBN: (纸本)9781450361842

Several classic problems in graph processing and computational geometry are solved via incremental algorithms, which split computation into a series of small tasks acting on shared state, which gets updated progressively. While the sequential variant of such algorithms usually specifies a fixed (but sometimes random) order in which the tasks should be performed, a standard approach to parallelizing such algorithms is to relax this constraint to allow for out-of-order parallel execution. This is the case for parallel implementations of Dijkstra's single-source shortest-paths (SSSP) algorithm, and for parallel Delaunay mesh triangulation. While many software frameworks parallelize incremental computation in this way, it is still not well understood whether this relaxed ordering approach can still provide any complexity guarantees. In this paper, we address this problem, and analyze the efficiency guarantees provided by a range of incremental algorithms when parallelized via relaxed schedulers. We show that, for algorithms such as Delaunay mesh triangulation and sorting by insertion, schedulers with a maximum relaxation factor of k in terms of the maximum priority inversion allowed will introduce a maximum amount of wasted work of O(logn poly (k)), where n is the number of tasks to be executed. For SSSP, we show that the additional work is O( poly (k) d(max)/w(min)), where d(max) is the maximum distance between two nodes, and w(min) is the minimum such distance. In practical settings where n >> k, this suggests that the overheads of relaxation will be outweighed by the improved scalability of the relaxed scheduler. On the negative side, we provide lower bounds showing that certain algorithms will inherently incur a non-trivial amount of wasted work due to scheduler relaxation, even for relatively benign relaxed schedulers.

关键词： relaxed data structures shortest path algorithms incremental algorithms

来源：评论

学校读者我要写书评

暂无评论

An integral linear interpolation approach to the design of incremental line algorithms

引用

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS 1999年第1期102卷 3-19页

作者： Yao, CF Rokne, JG Univ Calgary Dept Comp Sci Calgary AB T2N 1N4 Canada

A unified treatment of incremental line-drawing algorithms understood from the viewpoint of rounded interpolation, covering Bresenham's algorithm, run-length algorithms, and multistep versions of both. (C) 1999 El... 详细信息

关键词： scan conversion of lines integral linear interpolation incremental algorithms run-length algorithms

来源：评论

学校读者我要写书评

暂无评论

incremental model checking for fuzzy computation tree logic

引用

FUZZY SETS AND SYSTEMS 2025年 500卷

作者： Pan, Haiyu Zhou, Jie Lin, Yuming Cao, Yongzhi Guilin Univ Elect Technol Guangxi Key Lab Trusted Software Guilin 541004 Peoples R China Shanghai Normal Univ Math & Sci Coll Shanghai 200234 Peoples R China Peking Univ Sch Comp Sci Key Lab High Confidence Software Technol MOE Beijing 100871 Peoples R China

Fuzzy model checking, also called multi-valued model checking, has proved to be an effective technique in verifying properties of fuzzy systems. One important issue with fuzzy model checking, is that a model adopted in fuzzy model checking is frequently updated with small changes, and it is too costly to run a model-checking algorithm from scratch in response to every update. To address the issue, in this paper, we consider the incremental model-checking approach for fuzzy systems by making maximal use of previous model checking results or in other words, by minimizing unnecessary recomputation. The models of our study are fuzzy Kripke structures, which are a fuzzy counterpart of Kripke structures and used to describe fuzzy systems, while the properties of fuzzy systems are expressed using fuzzy computation tree logic, a fuzzy temporal logic derived from computation tree logic. The focus of the paper is on how to design incremental model-checking algorithms for two until-formulas which characterize the maximal or dually minimum constrained reachability properties with respect to fuzzy Kripke structures under transition insertions or deletions but not both. The feasibility of our approach is illustrated by an example arising from the path planning problem of mobile robots.

关键词： Computation tree logic Fuzzy logic incremental algorithms Model checking Triangular norm

来源：评论

学校读者我要写书评

暂无评论

String-averaging incremental stochastic subgradient algorithms

引用

OPTIMIZATION METHODS & SOFTWARE 2019年第3期34卷 665-692页

作者： Oliveira, R. M. Helou, E. S. Costa, E. F. Univ Sao Paulo Dept Appl Math & Stat Inst Math & Comp Sci Sao Carlos SP Brazil

We present a method to solve constrained convex stochastic optimization problems when the objective is a finite sum of convex functions . Our method is based on incremental Stochastic Subgradient algorithms and String-Averaging techniques, with an assumption that the subgradient directions are affected by random errors in each iteration. Our analysis allows the method to perform approximate projections onto the feasible set in each iteration. We provide convergence results for the case where a diminishing step-size rule is used. We test our method in a large set of random instances of a stochastic convex programming problem and we compare its performance with the robust mirror descent stochastic approximation algorithm proposed in Nemirovski et al. (Robust stochastic approximation approach to stochastic programming, SIAM J Optim 19 (2009), pp. 15741609).

关键词： Convex optimization stochastic optimization incremental algorithms stochastic subgradient methods approximate projection methods string-averaging algorithms

来源：评论

学校读者我要写书评

暂无评论

Adapting stable matchings to forced and forbidden pairs

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2025年 147卷

作者： Boehmer, Niclas Heeger, Klaus TU Berlin Ernst Reuter Pl 7 D-10587 Berlin Germany Univ Potsdam Hasso Plattner Inst Potsdam Germany Ben Gurion Univ Negev Beer Sheva Israel

We introduce the problem of adapting a stable matching to forced and forbidden pairs. Given a stable matching M-1, a set Q of forced pairs, and a set P of forbidden pairs, we want to find a stable matching that includes all pairs from Q, no pair from P, and is as close as possible to M-1. We study this problem in four classic stable matching settings: Stable Roommates (with Ties) and Stable Marriage (with Ties). Our main contribution is a polynomial-time algorithm, based on the theory of rotations, for adapting Stable Roommates matchings to forced pairs. In contrast, we show that the same problem for forbidden pairs is NP-hard. However, our polynomial-time algorithm for forced pairs can be extended to a fixed-parameter tractable algorithm with respect to the number of forbidden pairs. Moreover, we study the setting where preferences contain ties: Some of our algorithmic results can be extended while other problems become intractable. (c) 2024 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).

关键词： Stable Marriage Stable Roommates Forced and forbidden pairs incremental algorithms Rotations NP-hardness Polynomial-time algorithm W-hardness FPT

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：