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

Generating Rooted and Free Plane Trees

ACM TRANSACTIONS ON algorithmS 2006年第1期2卷 1-13页

作者： Sawada, Joe Univ Guelph Comp & Informat Sci Guelph ON N1G 2W1 Canada

This article has two main results. First, we develop a simple algorithm to list all nonisomorphic rooted plane trees in lexicographic order using a level sequence representation. Then, by selecting a unique centroid to act as the root of a free plane tree, we apply the rooted plane tree algorithm to develop an algorithm to list all nonisomorphic free plane trees. The latter algorithm also uses a level sequence representation and lists all free plane trees with a unique centroid first followed by all free plane trees with two centroids. Both algorithms are proved to run in constant amortized time using straightforward bounding methods.

关键词： cat algorithm chord diagram free plane tree necklace planar tree rooted plane tree

来源：评论

学校读者我要写书评

暂无评论

A simple shift rule for k-ary de Bruijn sequences

引用

DISCRETE MATHEMATICS 2017年第3期340卷 524-531页

作者： Sawada, Joe Williams, Aaron Wong, Dennis Univ Guelph Sch Comp Sci Guelph ON N1G 2W1 Canada Bard Coll Simons Rock Div Sci Math & Comp Great Barrington MA USA Northwest Missouri State Univ Sch Comp Sci & Informat Syst Maryville MO 64468 USA

A k-ary de Bruijn sequence of order n is a cyclic sequence of length k(n) in which each k-ary string of length n appears exactly once as a substring. A shift rule for a de Bruijn sequence of order n is a function that maps each length n substring to the next length n substring in the sequence. We present the first known shift rule for k-ary de Bruijn sequences that runs in O(1)-amortized time per symbol using O(n) space. Our rule generalizes the authors' recent shift rule for the binary case (A surprisingly simple de Bruijn sequence construction, Discrete Math. 339, 127-131). Published by Elsevier B.V.

关键词： k-ary de Bruijn sequence De Bruijn sequence Universal cycle Necklaces Shift Gray code cat algorithm Generate Shift rule Successor rule

来源：评论

学校读者我要写书评

暂无评论

A surprisingly simple de Bruijn sequence construction

引用

DISCRETE MATHEMATICS 2016年第1期339卷 127-131页

作者： Sawada, Joe Williams, Aaron Wong, Dennis Univ Guelph Sch Comp Sci Guelph ON N1G 2W1 Canada Bard Coll Div Math & Comp Sci Simons Rock MA USA NW Missouri State Univ Dept Math Comp Sci & Informat Syst Maryville MO USA

Pick any length n binary string b(1)b(2)...b(n) and remove the first bit b(1). If b(2)b(3)...b(n)1 is a necklace, then append the complement of b(1) to the end of the remaining string;otherwise append b(1). By repeating this process, eventually all 2(n) binary strings will be visited cyclically. This shift rule leads to a new de Bruijn sequence construction that can be generated in 0(1)-amortized time per bit. (C) 2015 Elsevier B.V. All rights reserved.

关键词： De Bruijn sequence Universal cycle Necklaces Shift Gray code cat algorithm Generate Shift rule Successor rule

来源：评论

学校读者我要写书评

暂无评论

Gray codes for signed involutions

引用

DISCRETE MATHEMATICS 2018年第9期341卷 2590-2601页

作者： Gutierres, Goncalo Mamede, Ricardo Santos, Jose Luis Univ Coimbra Dept Math CMUC Apartado 3008 P-3001501 Coimbra Portugal

In this paper we present two cyclic Gray codes for signed involutions. The first one has a natural construction, implemented by a cat algorithm, based in the recursive formula for the number of signed involutions. The second code, although with a higher computational cost, has the smallest possible Hamming distance for this family of objects. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Gray code Signed involution cat algorithm

来源：评论

学校读者我要写书评

暂无评论

Generating Cyclic Rotation Gray Codes for Stamp Foldings and Semi-meanders 34th

Generating Cyclic Rotation Gray Codes for Stamp Foldings and...

引用

34th International Workshop on Combinatorial algorithms (IWOCA)

作者： Liu, Bowie Wong, Dennis Macao Polytech Univ Macau Peoples R China

ISBN: (纸本)9783031343469;9783031343476

We present a simple algorithm that generates cyclic rotation Gray codes for stamp foldings and semi-meanders, where consecutive strings differ by a stamp rotation. These are the first known Gray codes for stamp foldings and semi-meanders, and we thus solve an open problem posted by Sawada and Li in [Electron. J. Comb. 19(2), 2012]. The algorithm generates each stamp folding and semi-meander in constant amortized time and O(n)-amortized time per string respectively, using a linear amount of memory.

关键词： Stamp foldings Meanders Semi-meanders Reflectable language Binary reflected Gray code Gray code cat algorithm

来源：评论

学校读者我要写书评

暂无评论

From Tetris to polyominoes generation

引用

Electronic Notes in Discrete Mathematics 2017年 59卷 79-98页

作者： Formenti, Enrico Massazza, Paolo Université Côte d'Azur CNRS I3S France Dipartimento di Scienze teoriche e applicate Università degli studi dell'Insubria Varese Italy

The behaviour of a bad Tetris player suggests a class of polyominoes that we call prefix-closed. Such a class contains all polyominoes P such that for any integer i>0 the first i columns of P form a polyomino. We provide a simple discrete dynamical system that allows us to define an algorithm for generating all prefix-closed polyominoes of size n in constant amortized time using O(n) space. © 2017 Elsevier B.V.

关键词： cat algorithm exhaustive generation polyomino

来源：评论

学校读者我要写书评

暂无评论

A Modified BCE algorithm for Fault-Tolerance Scheduling of Periodic Tasks in Hard Real-Time Systems

A Modified BCE Algorithm for Fault-Tolerance Scheduling of P...

引用

3rd Asia International Conference on Modelling and Simulation

作者： Asadi, M. Menhaj, M. B. Yavari, E. Amirkabir Univ Technol Fac Elect Engn Tehran Iran Tarbiat Modares Univ Fac Elect & Comp Engn Tehran Iran

ISBN: (纸本)9781424441549

Fault tolerance is an important aspect of real-time control systems, due to unavoidable timing constraints. In this paper, the timing problem of a set of concurrent periodic tasks is considered where each task has primary and alternate versions. In the literature, probability of fault in the alternate version of a task is assumed to be zero. Here, a fault probability with uniform distribution has been used. In addition, to cover the situations in which both versions are scheduled with some time overlapping, a criterion is defined for prioritizing primary version against the alternate version. A new scheduling algorithm is proposed based on the defined criterion. Simulation results show that an increase in the number of executed primary tasks which improves the efficiency of processor utilization, hence prove the efficiency of the proposed algorithm.

关键词： Scheduling Fault tolerant Periodic Tasks Real-time systems cat algorithm EIT algorithm

来源：评论

学校读者我要写书评

暂无评论

Novel universal cycle constructions for a variety ofcombinatorial objects

Novel universal cycle constructions for a variety ofcombinat...

引用

作者： Wong, Chi Him University of Guelph

学位级别：doctor

The cyclic sequence 0000100110101111 has the unlikelyproperty that the 16 unique binary substrings of length 4 appearexactly once in the sequence as a substring. This sequence is anexample of a universal cycle. A universal cycle for an arbitraryset S is a cyclic sequence of length |S| whose substrings of lengthn encode |S| distinct instances in S. When S is the set of k-arystrings of length n, these sequences are commonly studied under thename de Bruijn sequence. Universal cycles have been studied fora wide variety of combinatorial objects including permutations,partitions, subsets, multisets, labeled graphs, various functionsand passwords. The study of universal cycles has a long historywith applications including dynamic connections in overlaynetworks, genomics, software calculation of the ruler function incomputer words, and indexing a 1 in a computer word. There arestandard proofs to demonstrate the existence of universal cyclesfor a variety of combinatorial objects; however, only a smallnumber of universal cycles can be constructed efficiently andpractically. This thesis provides novel efficient constructions togenerate universal cycles for a variety of combinatorial objects. Our research leads to several new results. Firstly, we propose anovel shift rule to construct de Bruijn sequence for length nbinary strings. The shift rule provides a simple and efficientsuccessor rule to find the next bit in the de Bruijn sequence andis applicable to all values of n. We then extend the shift rule toconstruct de Bruijn sequence for k-ary strings of length ***, we generalize the Fredricksen-Kessler-Maiorana (FKM)construction and Greedy construction to generate universal cyclesfor a broad class of k-ary strings. We also prove that theuniversal cycles produced are the lexicographically smallest forthe sets. Lastly, we provide the first known efficient constructionto generate universal cycles for length n binary strings where thenumber of 1s range from c to d given 0 <

关键词： universal cycle de Bruijn sequence combinatorics on words FKM algorithm shift rule necklace prefix algorithm Gray code cat algorithm Greedy algorithm successor rule nonlinear feedback shift register

来源：评论

学校读者我要写书评

暂无评论

A Fast algorithm to Generate Open Meandric Systems and Meanders

引用

ACM TRANSACTIONS ON algorithmS 2010年第2期6卷 1–12页

作者： Bobier, Bruce Sawada, Joe Univ Waterloo Ctr Theoret Nuerosci Waterloo ON N2L 3G1 Canada Univ Guleph Sch Comp Sci Guleph ON N1G 2W1 Canada

An open meandric system is a planar configuration of acyclic curves crossing an infinite horizontal line in the plane such that the curves may extend in both horizontal directions. We present a fast, recursive algorithm to exhaustively generate open meandric systems with n crossings. We then illustrate how to modify the algorithm to generate unidirectional open meandric systems ( the curves extend only to the right) and nonisomorphic open meandric systems where equivalence is taken under horizontal reflection. Each algorithm can be modified to generate systems with exactly k curves. In the unidirectional case when k = 1, we can apply a minor modification along with some additional optimization steps to yield the first fast and simple algorithm to generate open meanders.

关键词： algorithms cat algorithm meander open meandric system

来源：评论

学校读者我要写书评

暂无评论

Generating 2-Gray codes for ballot sequences in constant amortized time

引用

DISCRETE MATHEMATICS 2023年第1期346卷

作者： Wong, Dennis Calero, Fabio Sedhai, Kushal Macao Polytech Univ Macau Peoples R China SUNY Univ Korea South Korea

We present a simple algorithm that generates a cyclic 2-Gray code for ballot sequences. The algorithm generates each ballot sequence in constant amortized time using a linear amount of space. This is the first known cyclic 2-Gray code for ballot sequences that achieves this time bound. In addition, the algorithm can be easily modified to output ballot sequences in binary reflected Gray code order in constant amortized time per string using a linear amount of space.(c) 2022 Elsevier B.V. All rights reserved.

关键词： Ballot sequence Gray code cat algorithm Binary reflected Gray code Flip-swap language Dyck

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：