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

Streaming Pattern Matching with d Wildcards

ALGORITHMICA 2019年第5期81卷 1988-2015页

作者： Golan, Shay Kopelowitz, Tsvi Porat, Ely Bar Ilan Univ Ramat Gan Israel

In the pattern matching with d wildcards problem one is given a text T of length n and a pattern P of length m that contains d wildcard characters, each denoted by a special symbol '?'. A wildcard character matches any other character. The goal is to establish for each m-length substring of T whether it matches P. In the streaming model variant of the pattern matching with d wildcards problem the text T arrives one character at a time and the goal is to report, before the next character arrives, if the last m characters match P while using only o(m) words of space. In this paper we introduce two new algorithms for the d wildcard pattern matching problem in the streaming model. The first is a randomized Monte Carlo algorithm that is parameterized by a constant 0 <= delta <= 1. This algorithm uses (O) over tilde (d(1-delta)) amortized time per character and (O) over tilde (d(1+delta)) words of space. The second algorithm, which is used as a black box in the first algorithm, is a randomized Monte Carlo algorithm which uses O(d + log m) worst-case time per character and O(d + log m) words of space.

关键词： Pattern matching Streaming algorithms Fingerprints string combinatorics

来源：评论

学校读者我要写书评

暂无评论

On arithmetically progressed suffix arrays and related Burrows-Wheeler transforms

引用

DISCRETE APPLIED MATHEMATICS 2024年 355卷 180-199页

作者： Daykin, Jacqueline W. Koppl, Dominik Kubel, David Stober, Florian Aberystwyth Univ Dept Comp Sci Aberystwyth Wales Normandie Univ Univ Rouen Normandie Univ Le Havre Normandie INSA Rouen NormandieLITIS F-76000 Rouen France Stellenbosch Univ Dept Informat Sci Stellenbosch South Africa Univ Yamanashi Dept Comp Sci & Engn Kofu Japan Univ Bonn Inst Comp Sci Bonn Germany Univ Stuttgart Inst Formal Methods Comp Sci FMI Stuttgart Germany

We characterize those strings whose suffix arrays are based on arithmetic progressions, in particular, arithmetically progressed permutations where all pairs of successive entries of the permutation have the same difference modulo the respective string length. We show that an arithmetically progressed permutation P coincides with the suffix array of a unary, binary, or ternary string. We further analyze the conditions of a given P under which we can find a uniquely defined string over either a binary or ternary alphabet having P as its suffix array. For the binary case, we show its connection to lower Christoffel words, balanced words, and Fibonacci words. In addition to solving the arithmetically progressed suffix array problem, we give the shape of the Burrows- Wheeler transform of those strings solving this problem. These results give rise to numerous future research directions. (c) 2024 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).

关键词： Arithmetic progression Burrows-Wheeler transform Christoffel words Suffix array string combinatorics

来源：评论

学校读者我要写书评

暂无评论

Mapping cones in the bounded derived category of a gentle algebra

引用

JOURNAL OF ALGEBRA 2019年第0期530卷 163-194页

作者： Canakci, Ilke Pauksztello, David Schroll, Sibylle Newcastle Univ Sch Math Stat & Phys Newcastle Upon Tyne NE1 7RU Tyne & Wear England Univ Lancaster Dept Math & Stat Lancaster LA1 4YF England Univ Leicester Dept Math Univ Rd Leicester LE1 7RH Leics England

In this article we describe the triangulated structure of the bounded derived category of a gentle algebra by describing the triangles induced by the morphisms between indecomposable objects in a basis of their Horn-s... 详细信息

关键词： Bounded derived category Gentle algebra Homotopy string and band string combinatorics Mapping cone

来源：评论

学校读者我要写书评

暂无评论

Morphisms between indecomposable complexes in the bounded derived category of a gentle algebra

引用

JOURNAL OF ALGEBRA 2016年第0期467卷 1-46页

作者： Arnesen, Kristin Krogh Laking, Rosanna Pauksztello, David Norwegian Univ Sci & Technol NTNU Fac Teacher & Interpreter Educ N-7491 Trondheim Norway Univ Manchester Sch Math Oxford Rd Manchester M13 9PL Lancs England

In this article we provide a simple combinatorial description of morphisms between indecomposable complexes in the bounded derived category of a gentle algebra. (C) 2016 The Authors. Published by Elsevier Inc. This is... 详细信息

关键词： Bounded derived category Gentle algebra Homotopy string and band string combinatorics Morphism

来源：评论

学校读者我要写书评

暂无评论

On Extensions for Gentle Algebras

引用

CANADIAN JOURNAL OF MATHEMATICS-JOURNAL CANADIEN DE MATHEMATIQUES 2021年第1期73卷 249-292页

作者： Canakci, Ilke Pauksztello, David Schroll, Sibylle Vrije Univ Amsterdam Dept Math NL-1081 HV Amsterdam Netherlands Univ Lancaster Dept Math & Stat Lancaster LA1 4YF England Univ Leicester Dept Math Univ Rd Leicester LE1 7RH Leics England

We give a complete description of a basis of the extension spaces between indecomposable string and quasi-simple band modules in the module category of a gentle algebra.

关键词： gentle algebra extensions bounded derived category homotopy string and bands string combinatorics

来源：评论

学校读者我要写书评

暂无评论

Auslander-Reiten components of symmetric special biserial algebras

引用

JOURNAL OF ALGEBRA 2018年 508卷 475-511页

作者： Duffield, Drew

We provide a combinatorial algorithm for constructing the stable Auslander-Reiten component containing a given indecomposable module of a symmetric special biserial algebra using only information from its underlying Brauer graph. We also show that the structure of the Auslander-Reiten quiver is closely related to the distinct Green walks of the Brauer graph and detail the relationship between the precise shape of the stable Auslander-Reiten components for domestic Brauer graph algebras and their underlying graph. Furthermore, we show that the specific component containing a given simple or indecomposable projective module for any Brauer graph algebra is determined by the edge in the Brauer graph associated to the module. Crown Copyright (C) 2018 Published by Elsevier Inc. All rights reserved.

关键词： Representation theory Auslander-Reiten theory Special biserial algebras Brauer graph algebras Finite dimensional algebras string modules string combinatorics

来源：评论

学校读者我要写书评

暂无评论

Lattice bijections for string modules, snake graphs and the weak Bruhat order

引用

ADVANCES IN APPLIED MATHEMATICS 2021年 126卷 102094-102094页

作者： Canakci, Ilke Schroll, Sibylle Vrije Univ Amsterdam Dept Math NL-1081 HV Amsterdam Netherlands Univ Leicester Dept Math Univ Rd Leicester LE1 7RH Leics England

In this paper we introduce abstract string modules and give an explicit bijection between the submodule lattice of an abstract string module and the perfect matching lattice of the corresponding abstract snake graph. In particular, we make explicit the direct correspondence between a submodule of a string module and the perfect matching of the corresponding snake graph. For every string module we define a Coxeter element in a symmetric group. We then establish a bijection between the submodule lattice of the string module and the lattice given by the interval in the weak Bruhat order determined by the Coxeter element. Using the correspondence between string modules and snake graphs, we give a new concise formulation of snake graph calculus. (c) 2020 Published by Elsevier Inc.

关键词： string combinatorics Snake graphs Perfect matchings Symmetric groups Bruhat order Distributive lattices

来源：评论

学校读者我要写书评

暂无评论

Breathing Mankind Thoughts 16

Breathing Mankind Thoughts

引用

13th ACM SIGMETRICS/IFIP Performance Joint International Conference on Measurement and Modeling of Computer Science (ACM SIGMETRICS/IFIP)

作者： Jacquet, Philippe Nokia Bell Labs Nozay France

ISBN: (纸本)9781450342667

Mankind has never been connected as it is now and as it will be tomorrow. Nowadays thanks to the rise of social networks such as Tweeter and Facebook, we can follow in real time the thought of millions of people. In fact we can almost feel the thoughts of a whole humanity and maybe project ourselves in a position where we could predict the major trends in the collective behavior of this humanity. However such an ambitious aim would require considerable resources in processing and networking which may be far from affordable. Indeed trends and topics are carried in a multiple of small texts written in various language and vocabularies like an hologram carries information in a dispersed way. Their capture and classification pose serious problems of data mining and analytics. Processes based on pure semantic analysis would require too much processing power and memory. We will present alternative methods based on string complexity also inspired on geolocalization in wireless networks which saves processing power by several order of magnitude. The ultimate goal is to detect when people are thinking about the very same topics before they become aware. Beyond the problem of topic detection and classification one must also estimate the potential of an isolated topic to become a lasting trend. In other word one must probe the topic foundations, for example by challenging how trustworthy are its sources. Designing an efficient source finder algorithm is indissociable with building realistic models about topic propagation. If we suppose that topics propagate inside communities via the followers-followees links, the propagation is highly amplified by the unbalances in the graph topology. It is established that dominating and semi dominating nodes such as the CNN Tweeter site are the main accelerator of topic propagation. The difficulty is to find the actual source of a topic beyond those screening nodes and the search is prone to false positive and true negative effects. In fact

关键词： Social networks topic detection string combinatorics topic propagation

来源：评论

学校读者我要写书评

暂无评论

Corrigendum to “Mapping cones for morphisms involving a band complex in the bounded derived category of a gentle algebra” [J. Algebra 530 (2019) 163–194]

引用

Journal of Algebra 2021年 569卷 856-874页

作者： İlke Çanakçı David Pauksztello Sibylle Schroll Department of Mathematics VU Amsterdam Amsterdam 1081 HV the Netherlands Department of Mathematics and Statistics Lancaster University Lancaster LA1 4YF United Kingdom Department of Mathematics University of Leicester University Road Leicester LE1 7RH United Kingdom

In this note we correct two oversights in Çanakçi et al. (2019) [6] which only occur when a band complex is involved. As a consequence we see that the mapping cone of a morphism between two band complexes ca... 详细信息

关键词： 18G80 16G10 05E10 Bounded derived category Gentle algebra Homotopy string and band string combinatorics Mapping cone

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：