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

graph-based algorithms for phase-type distributions

STATISTICS AND COMPUTING 2022年第6期32卷 103-103页

作者： Roikjer, Tobias Hobolth, Asger Munch, Kasper Aarhus Univ Bioinformat Res Ctr Universitetsbyen 813 Bldg 1872 DK-8000 Aarhus Denmark Aarhus Univ Dept Math Ny Munkegade 118 Bldg 1530 DK-8000 Aarhus Denmark

Phase-type distributions model the time until absorption in continuous or discrete-time Markov chains on a finite state space. The multivariate phase-type distributions have diverse and important applications by modeling rewards accumulated at visited states. However, even moderately sized state spaces make the traditional matrix-based equations computationally infeasible. State spaces of phase-type distributions are often large but sparse, with only a few transitions from a state. This sparseness makes a graph-based representation of the phase-type distribution more natural and efficient than the traditional matrix-based representation. In this paper, we develop graph-based algorithms for analyzing phase-type distributions. In addition to algorithms for state space construction, reward transformation, and moments calculation, we give algorithms for the marginal distribution functions of multivariate phase-type distributions and for the state probability vector of the underlying Markov chains of both time-homogeneous and time-inhomogeneous phase-type distributions. The algorithms are available as a numerically stable and memory-efficient open source software package written in C named ptdalgorithms. This library exposes all methods in the programming languages C and R. We compare the running time of ptdalgorithms to the fastest tools using a traditional matrix-based formulation. This comparison includes the computation of the probability distribution, which is usually computed by exponentiation of the sub-intensity or sub-transition matrix. We also compare time spent calculating the moments of (multivariate) phase-type distributions usually defined by inversion of the same matrices. The numerical results of our graph-based and traditional matrix-based methods are identical, and our graph-based algorithms are often orders of magnitudes faster. Finally, we demonstrate with a classic problem from population genetics how ptdalgorithms serves as a much faster, simpler, a

关键词： Phase-type distributions Computational statistics Moments Distribution graph-based algorithms

来源：评论

学校读者我要写书评

暂无评论

Assessing two graph-based algorithms in a model-based testing platform for Java applications 15

Assessing two graph-based algorithms in a model-based testin...

引用

15th Iberian Conference on Information Systems and Technologies (CISTI)

作者： Villalobos-Arias, Leonardo Quesada-Lopez, Christian Martinez, Alexandra Jenkins, Marcelo Univ Costa Rica Escuela Ciencias Comp & Informat San Jose Costa Rica

ISBN: (纸本)9789895465903

Model-based testing (MBT) is an approach for automatically generating test cases from a model of the system under test. Existing MBT tools support the automation of this process at varying degrees. One such tool is MBT4J, a research platform that extends ModelJUnit, offering a high level of automation. We extended MBT4J with two graph-based algorithms: the Chinese Postman Problem (CPP) and Breadth-First Search (BFS). The purpose of this study is to evaluate the efficacy of these two new algorithms added to MBT4J by comparing them to previous algorithms implemented in the platform. A case study was conducted using two open-source Java applications from public repositories, and twenty-one different configurations. The CPP tester performed similarly to previous testers in terms of time and coverage, and in addition, it resulted in a greater percentage of failed test cases in one application. The BFS tester was able to generate a greater amount of test cases when using fewer resources. We thus recommend using these algorithms for generating test cases for systems with complex models.

关键词： model-based testing MBT4J graph-based algorithms Java applications case study

来源：评论

学校读者我要写书评

暂无评论

Comparing graph-based algorithms to Generate Test Cases from Finite State Machines

引用

JOURNAL OF ELECTRONIC TESTING-THEORY AND APPLICATIONS 2019年第6期35卷 867-885页

作者： Mariano, Matheus Monteiro de Souza, Erica Ferreira Endo, Andre Takeshi Vijaykumar, Nandamudi Lankalapalli Natl Inst Space Res Lab Comp & Appl Math INPE Av Astronautas1-758 Jardim Granja BR-12227010 Sao Jose Dos Campos SP Brazil Fed Univ Technol Dept Comp UTFPR Av Alberto Carazzai 1640 BR-86300000 Cornelio Procopio PR Brazil Univ Fed Sao Paulo ICT Inst Sci & Technol Av Cesare Monsueto Giulio Lattes 1201 Sao Jose Dos Campos Brazil Natl Inst Space Res LABAC Av Astronautas 1758 Sao Jose Dos Campos Brazil

Model-based Testing (MBT) is a well-known technique that employs formal models to represent reactive systems' behavior and generates test cases. Such systems have been specified and verified using mostly Finite State Machines (FSMs). There is a plethora of test generation algorithms in the literature;most of them are based on graphs once an FSM can be formally defined as a graph. Nevertheless, there is a lack of studies on analyzing cost and efficiency of FSM-based test generation algorithms. This study compares graph-based algorithms adopted to generate test cases from FSM models. In particular, we compare the Chinese Postman Problem (CPP) and H-Switch Cover (HSC) algorithms with the well-known Depth-First Search (DFS) and Breadth-First Search (BFS) algorithms in the context of covering all-transitions and all-transition-pairs criteria in an FSM. First, a systematic literature mapping was conducted to summarize the methods that have been adopted in MBT, considering FSMs. Second, the main methods found were implemented and analyzed on randomly-generated FSMs, as well as real-world models that represent embedded systems of space applications. To make comparisons, we considered analyses in terms of cost (time), efficiency (mutant analysis) and characteristics of the generated test suites (number of test cases, average length of test cases, largest and smallest test cases, standard deviation and distribution of test cases). In general, CPP presented the best results in terms of number of test cases and test suite size. In addition, CPP also presented low distribution of average length compared to other algorithms.

关键词： Software testing Model based testing Finite state machine graph-based algorithms

来源：评论

学校读者我要写书评

暂无评论

Analyzing graph-based algorithms employed to generate test cases from finite state machines 20

Analyzing graph-based algorithms employed to generate test c...

引用

20th IEEE Latin American Test Symposium (LATS)

作者： Mariano, Matheus Monteiro Souza, Erica F. Endo, Andre T. Vijaykumar, Nandamudi L. Natl Inst Space Res INPE Lab Comp & Appl Math Sao Jose Dos Campos SP Brazil Fed Technol Univ UTFPR Dept Comp Cornelio Procopio PR Brazil

ISBN: (纸本)9781728117560

Context: Model-based Testing (MBT) is a technique that employs formal models to represent reactive systems' behavior and generates test cases. Such systems are mostly specified and verified using Finite State Machines (FSMs). There is a plethora of test generation algorithms in the literature. Most of them are graph-based once an FSM can be formally defined as a graph. Nevertheless, there is a lack of studies on analyzing cost and efficiency of FSM-based test generation algorithms. Objective: This study aims to compare graph-based algorithms employed to generate test cases from FSM models. In particular, we compare the Chinese Postman Problem (CPP) and H-Switch Cover (HSC) algorithms with the well-known depth-first and breadth-first searches algorithms in the context of covering all-transitions and all-transition-pairs criteria in an FSM. Method: First, a systematic literature mapping was conducted to summarize the algorithms that have been adopted in MBT, considering FSM. The main algorithms found were implemented and analyzed in different experiments. Results: CPP presented better results with the FSMs used in terms of number of test cases and test suite size. In addition, CPP also presented low distribution of average length compared to other algorithms.

关键词： Software Testing Model based Testing Finite State Machine graph-based algorithms

来源：评论

学校读者我要写书评

暂无评论

graph based algorithms to efficiently map VLSI circuits with simple cells

Graph based algorithms to efficiently map VLSI circuits with...

引用

作者： Matos, Jody Maick Araujo de

This thesis introduces a set of graph-based algorithms for efficiently mapping VLSI circuits using simple cells. The proposed algorithms are concerned to, first, effectively minimize the number of logic elements implementing the synthesized circuit. Then, we focus a significant effort on minimizing the number of inverters in between these logic elements. Finally, this logic representation is mapped into a circuit comprised of only two-input NANDs and NORS, along with the inverters. Two-input XORs and XNORs can also be optionally considered. As we also consider sequential circuits in this work, flip-flops are taken into account as well. Additionally, with high-effort optimization on the number of logic elements, the generated circuits may contain some cells with unfeasible fanout for current technology nodes. In order to fix these occurrences, we propose an area-oriented, level-aware algorithm for fanout limitation. The proposed algorithms were applied over a set of benchmark circuits and the obtained results have shown the usefulness of the method. We show that efficient implementations in terms of inverter count, transistor count, area, power and delay can be generated from circuits with a reduced number of both simple cells and inverters, combined with XOR/XNOR-based optimizations. The proposed buffering algorithm can handle all unfeasible fanout occurrences, while (i) optimizing the number of added inverters; and (ii) assigning cells to the inverter tree based on their level criticality. When comparing with academic and commercial approaches, we are able to simultaneously reduce the average number of inverters, transistors, area, power dissipation and delay up to 48%, 5%, 5%, 5%, and 53%, respectively. As the adoption of a limited set of simple standard cells have been showing benefits for a variety of modern VLSI circuits constraints, such as layout regularity, routability constraints, and/or ultra low power constraints, the proposed methods can be of special i

关键词： graph-based algorithms Microeletrônica Vlsi Simple cells Síntese lógica Standard cell library Technology mapping Logic synthesis Tese

来源：评论

学校读者我要写书评

暂无评论

Multiplierless Design of Very Large Constant Multiplications in Cryptography

引用

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS II-EXPRESS BRIEFS 2022年第11期69卷 4503-4507页

作者： Aksoy, Levent Roy, Debapriya Basu Imran, Malik Karl, Patrick Pagliarini, Samuel Tallinn Univ Technol Ctr Hardware Secur Dept Comp Syst EE-12618 Tallinn Estonia Tech Univ Munich Dept Elect & Comp Engn Chair Secur Informat Technol D-80333 Munich Germany

This brief addresses the problem of implementing very large constant multiplications by a single variable under the shift-adds architecture using a minimum number of adders/subtractors. Due to the intrinsic complexity of the problem, we introduce an approximate algorithm, called TOLL, which partitions the very large constants into smaller ones. To reduce the number of operations, TOLL incorporates graph-based and common subexpression elimination methods proposed for the shift-adds design of constant multiplications. It can also consider the delay of a multiplierless design defined in terms of the maximum number of operations in series, i.e., the number of adder-steps, while reducing the number of operations. High-level experimental results show that the adder-steps of a shift-adds design can be reduced significantly with a little overhead in the number of operations. Gate-level experimental results indicate that while the shift-adds design can lead to a 36.6% reduction in gate-level area with respect to a design using a multiplier, the delay-aware optimization can yield a 48.3% reduction in minimum achievable delay of the shift-adds design when compared to the area-aware optimization.

关键词： Very large constant multiplication shift-adds design graph-based algorithms common subexpression elimination delay-aware optimization cryptography

来源：评论

学校读者我要写书评

暂无评论

Web Services for Guiding Persons with Locomotor Impairments in Public Spaces 26

Web Services for Guiding Persons with Locomotor Impairments ...

引用

26th International Conference on System Theory, Control and Computing (ICSTCC)

作者： Damian, Ioan Lacatusu, Marian Lacatusu, Florin Ionita, Anca Daniela Univ Politehn Bucuresti Automat & Ind Informat Dept Bucharest Romania

ISBN: (数字)9781665467469

ISBN: (纸本)9781665467469

The navigation of pedestrians to a certain destination poses a challenge for large or unknown public spaces, even for those with very good wayfinding designs. This is amplified when people having locomotory impairments try to orientate themselves while being limited by accessibility restrictions. The approach presented here is based on modeling public spaces as graphs and adding weights corresponding to the potential difficulty to cross their edges. The typical path generation algorithm is extended to deliver the right guidance to pedestrians with mobility problems. By selecting a policy specific to their needs in the routing application, the users can have details on how hard it is to access a certain location of the public space. The paper presents an implementation using RESTful web services and an example of routing directions inside a building from our faculty.

关键词： RESTful Web Services graph-based algorithms assistive software

来源：评论

学校读者我要写书评

暂无评论

ESA*: A generic framework for semi-supervised inductive learning

引用

NEUROCOMPUTING 2021年 447卷 102-117页

作者： Yang, Shuyi Ienco, Dino Esposito, Roberto Pensa, Ruggero G. Univ Turin Comp Sci Dept Cso Svizzera 185 I-10149 Turin Italy Intesa Sanpaolo Turin Italy INRAE UMR TETIS Montpellier France

Semi-supervised learning is crucial in many applications where accessing class labels is unaffordable or costly. The most promising approaches are graph-based but they are transductive and they do not provide a generalized model working on inductive scenarios. To address this problem, we propose a generic framework, ESA*, for inductive semi-supervised learning based on three components: an ensemble of semi-supervised autoencoders providing a new data representation that leverages the knowledge supplied by the reduced amount of available labels;a graph-based step that helps augmenting the training set with pseudo-labeled instances and, finally, a classifier trained with labeled and pseudo-labeled instances. Additionally, we also introduce two variants of our framework adopting different graph-based pseudo-labeling strategies: the first, ESA(LP), is based on a confidence-aware label propagation algorithm, while the second, ESA(GAT), on a graph convolutional attention network. The experimental results show that our framework outperforms state-of-the-art inductive semi-supervised methods. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Semi-supervised learning graph-based algorithms Inductive methods

来源：评论

学校读者我要写书评

暂无评论

Treatment Recommendations for COVID-19 Patients along with Robust Explanations 34

Treatment Recommendations for COVID-19 Patients along with R...

引用

34th IEEE International Symposium on Computer-based Medical Systems (IEEE CBMS)

作者： Symeonidis, Panagiotis Andras, Christos Zanker, Markus Univ Aegean Samos Greece Int Hellen Univ Thessaloniki Greece Free Univ Bozen Bolzano Bolzano Italy

ISBN: (纸本)9781665441216

The global response to the pandemic introduced by COVID-19 is unprecedented. Scientists develop methods, which analyze data to identify an effective treatment that uncovers possible responses to the SARS-COV-2 virus. However, our global response should be based on knowledge exchange and collaboration among countries. In this paper, we present a recommender system for treatment recommendations, which exploits similar patterns among patients of different clinical studies, and recommends them health interventions (such as to provide oxygen therapy) and drugs (e.g., Remdesivir) based on their symptoms' or diseases' similarity with patients of other similar clinical studies. Our approach can also provide explanations along with recommended treatments to assist doctors in understanding the reasons behind a suggested drug or health intervention. We also perform experiments to identify the effectiveness of our system in terms of recommendation accuracy. Our results demonstrate that our system is able to minimize the false positive and false negative prediction rates. Finally, we provide web links to download both (i) our program's setup file and (ii) our Neo4j database file.

关键词： recommender systems graph-based algorithms meta path

来源：评论

学校读者我要写书评

暂无评论

引用

21st International Conference on Web Engineering (ICWE)

作者： Symeonidis, Panagiotis Univ Aegean Samos Greece

ISBN: (纸本)9783030742966;9783030742959

In this tutorial, we provide a rich blend of theory and practice regarding graph algorithms, to deal with challenging issues such as scalability, data noise, and sparsity in recommender systems. We also demonstrate real-life systems that use the graph algorithms for Social Media (http://***/moviexplain/), News (http://***) and Health (https://***) industry along with user studies which were used to evaluate the acceptance of the users for these systems.

关键词： Recommender systems graph-based algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：