Constant time BSR solutions to parenthesis matching, tree decoding, and tree reconstruction from its traversals

Stojmenovic I.

首页> 外文期刊>IEEE Transactions on Parallel and Distributed Systems >Constant time BSR solutions to parenthesis matching, tree decoding, and tree reconstruction from its traversals

【24h】

Constant time BSR solutions to parenthesis matching, tree decoding, and tree reconstruction from its traversals

机译：通过括号遍历的恒定时间BSR解决方案，用于括号匹配，树解码和树重构

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

Recently Akl et al. introduced a new model of parallel computation, called BSR (broadcasting with selective reduction) and showed that it is more powerful than any CRCW PRAM and yet requires no more resources for implementation than even EREW PRAM. The model allows constant time solutions to sorting, parallel prefix and other problems. In this paper, we describe constant time solutions to the parenthesis matching, decoding binary trees in bitstring representation, generating next tree shape in B-order, and the reconstruction of binary trees from their traversals, using the BSR model. They are the first constant time solutions to mentioned problems on any model of computation. The number of processors used is equal to the input size, for each problem. A new algorithm for sorting integers is also presented.

机译：最近，Akl等人。他介绍了一种称为BSR（有选择地减少广播）的并行计算新模型，并表明它比任何CRCW PRAM都更强大，而且比EREW PRAM所需的资源也更少。该模型允许使用固定时间的解决方案来解决排序，并行前缀和其他问题。在本文中，我们描述了用于括号匹配的恒定时间解，使用位串表示解码二叉树，生成B阶的下一棵树形以及使用BSR模型从遍历重建二叉树。它们是任何计算模型上提到的问题的第一个恒定时间解决方案。对于每个问题，使用的处理器数量等于输入大小。还提出了一种用于对整数进行排序的新算法。

著录项

来源
《IEEE Transactions on Parallel and Distributed Systems》 |1996年第2期|P.218-224|共7页
作者
Stojmenovic I.;
展开▼
作者单位

展开▼
收录信息
原文格式 PDF
正文语种 eng
中图分类计算技术、计算机技术;
关键词

相似文献

外文文献
中文文献
专利

1. Time optimal n-size matching parentheses and binary tree decoding algorithms on a p-processor BSR [J] . Limin Xiang, Kazuo Ushijiam, Jianjun Zhao Parallel Processing Letters . 2002,第3a4期

机译：p处理器BSR上的时间最佳n大小匹配括号和二叉树解码算法
2. Constant-Time Tree Traversal and Subtree Equality Check for Grammar-Compressed Trees [J] . Markus Lohrey, Sebastian Maneth, Carl Philipp Reh Algorithmica . 2018,第7期

机译：语法压缩树的恒定时间树遍历和子树相等性检查
3. Reconstruction of a Binary Search Tree from its Preorder Tree Traversal with the Unique Non-recursive Approach [J] . Manoj C. Lohani, Upendra S. Aswal, Ramesh S. Rawat Oriental journal of computer science and technology . 2011,第1期

机译：使用唯一的非递归方法从遍历树遍历重建二叉搜索树
4. Encoding a Binary Search Tree in Constant Time on BSR [C] . Limin Xiang, Kai Cheng, Ushijiam K. Water Event, 2005 . 2005

机译：在BSR上恒定时间编码二进制搜索树
5. Robust methods for human airway-tree segmentation and anatomical-tree matching. [D] . Graham, Michael W. 2008

机译：用于人体气道树分割和解剖树匹配的鲁棒方法。
6. ASTRAL-III: polynomial time species tree reconstruction from partially resolved gene trees [O] . Chao Zhang, Maryam Rabiee, Erfan Sayyari, 2018

机译：ASTRAL-III：从部分解析的基因树重建多项式时间树
7. Figure 6: (A) Tree resulted the standard MP analysis of the 98-loci supermatrix of the Great Apes (Hominidae, Primates, Mammalia) constructed using the modified summary of Lehtonen et al. (2011) (see “Materials and Methods” for the details) and a posteriori rooted relatively Papio (length = 12,092, CI = 0.7877, RI = 0.5597); 34,022 characters are constant, and the number of the parsimony-informative characters is equal to 4,311. MP BS values are provided below branches. The only characters with non-ambiguous value of the outgroup (Papio) have been saved within concatenated alignment; (B) the average consensus tree of the score 0.00084 resulted the analysis of the Hennigian forest of the 5,507 trees derived from the binary representation of the 98-loci supermatrix of the Great Apes (Hominidae, Primates, Mammalia) (see “Materials and Methods” for the details); Papio is assumed to be the best all-plesiomorphic group. “Additional…” FORESTER’s output tree file (see “Materials and Methods” for the details) selected for future analyses; (C) the average consensus tree of the score 0.00090 resulted the analysis of the Hennigian forest of the 5,339 trees derived from the modified binary representation of the 98-loci supermatrix of the Great Apes (Hominidae, Primates, Mammalia) (see 6.I. and “Materials and Methods” for the details), but with all 168 trees, which contain the clade (Homo plus Pan) have been removed from the input forest. “Additional…” FORESTER’s output tree file (see “Materials and Methods”) selected for future analyses. [O] . -1

机译：图6：（A）树导致的标准MP分析的98-基因座的类人猿（人科，灵长类动物，哺乳动物），使用莱赫托宁等人的修改的摘要构成的超级矩阵。（2011）（参见细节“材料和方法”）以及相对植根狒狒后验概率（长度= 12092，CI = 0.7877，RI = 0.5597）; 34022个字符是恒定的，并且简约信息的字符数等于4311。下面提供分支MP BS值。与外类群（狒狒）的非模糊值的唯一的字符已被保存的级联对准内; （B）的得分0.00084的平均一致树导致从巨猿（原始人类，灵长类动物，哺乳动物）的98座超级矩阵的二进制表示获得的5507棵的Hennigian森林的分析（见“材料和方法”为细节）;狒狒被认为是最好的全祖征群。 “其他...” FORESTER的输出树文件（请参阅详细信息“材料和方法”），用于进一步的分析; （C）的分数0.00090的平均一致树导致从98个位点的类人猿（人科，灵长类动物，哺乳动物）的超级矩阵（见6.I的改性二进制表示导出的5339种树木的Hennigian森林的分析以及“材料和方法”的详细说明），但所有168棵，其中包含的分支（智人加PAN）已经从输入林中删除。 “其他...” FORESTER的输出树文件（参见“材料和方法”），用于进一步的分析。

Constant time BSR solutions to parenthesis matching, tree decoding, and tree reconstruction from its traversals

摘要

著录项

相似文献

相关主题

期刊订阅