Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userError-tolerant Tree Matching
42
0
0.0
(
0
)
Added by
Kemal Oflazer
Publication date
1996
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
This paper presents an efficient algorithm for retrieving from a database of trees, all trees that match a given query tree approximately, that is, within a certain error tolerance. It has natural language processing applications in searching for matches in example-based translation systems, and retrieval from lexical databases containing entries of complex feature structures. The algorithm has been implemented on SparcStations, and for large randomly generated synthetic tree databases (some having tens of thousands of trees) it can associatively search for trees with a small error, in a matter of tenths of a second to few seconds.
rate research
Read More
This paper describes a generalization of previous methods for constructing tree-structured belief network with hidden variables. The major new feature of the described method is the ability to produce a tree decomposition even when there are errors in the correlation data among the input variables. This is an important extension of existing methods since the correlational coefficients usually cannot be measured with precision. The technique involves using a greedy search algorithm that locally minimizes an error function.
Consider a 2-D square array of qubits of extent $Ltimes L$. We provide a proof that the minimum weight perfect matching problem associated with running a particular class of topological quantum error correction codes on this array can be exactly solved with a 2-D square array of classical computing devices, each of which is nominally associated with a fixed number $N$ of qubits, in constant average time per round of error detection independent of $L$ provided physical error rates are below fixed nonzero values, and other physically reasonable assumptions. This proof is applicable to the fully fault-tolerant case only, not the case of perfect stabilizer measurements.
Reverse Engineering(RE) has been a fundamental task in software engineering. However, most of the traditional Java reverse engineering tools are strictly rule defined, thus are not fault-tolerant, which pose serious problem when noise and interference were introduced into the system. In this paper, we view reverse engineering as a statistical machine translation task instead of rule-based task, and propose a fault-tolerant Java decompiler based on machine translation models. Our model is based on attention-based Neural Machine Translation (NMT) and Transformer architectures. First, we measure the translation quality on both the redundant and purified datasets. Next, we evaluate the fault-tolerance(anti-noise ability) of our framework on test sets with different unit error probability (UEP). In addition, we compare the suitability of different word segmentation algorithms for decompilation task. Experimental results demonstrate that our model is more robust and fault-tolerant compared to traditional Abstract Syntax Tree (AST) based decompilers. Specifically, in terms of BLEU-4 and Word Error Rate (WER), our performance has reached 94.50% and 2.65% on the redundant test set; 92.30% and 3.48% on the purified test set.
Extensive quantum error correction is necessary in order to perform a useful computation on a noisy quantum computer. Moreover, quantum error correction must be implemented based on imperfect parity check measurements that may return incorrect outcomes or inject additional faults into the qubits. To achieve fault-tolerant error correction, Shor proposed to repeat the sequence of parity check measurements until the same outcome is observed sufficiently many times. Then, one can use this information to perform error correction. A basic implementation of this fault tolerance strategy requires $Omega(r d^2)$ parity check measurements for a distance-d code defined by r parity checks. For some specific highly structured quantum codes, Bombin has shown that single-shot fault-tolerant quantum error correction is possible using only r measurements. In this work, we demonstrate that fault-tolerant quantum error correction can be achieved using $O(d log(d))$ measurements for any code with distance $d geq Omega(n^alpha)$ for some constant $alpha > 0$. Moreover, we prove the existence of a sub-single-shot fault-tolerant quantum error correction scheme using fewer than r measurements. In some cases, the number of parity check measurements required for fault-tolerant quantum error correction is exponentially smaller than the number of parity checks defining the code.
Conventional fault-tolerant quantum error-correction schemes require a number of extra qubits that grows linearly with the codes maximum stabilizer generator weight. For some common distance-three codes, the recent flag paradigm uses just two extra qubits. Chamberland and Beverland (2018) provide a framework for flag error correction of arbitrary-distance codes. However, their construction requires conditions that only some code families are known to satisfy. We give a flag error-correction scheme that works for any stabilizer code, unconditionally. With fast qubit measurement and reset, it uses $d+1$ extra qubits for a distance-$d$ code.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
