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

JOURNAL OF FUNCTIONAL PROGRAMMING 2012年第6期22卷 747-756页

作者： Spivey, Michael Univ Oxford Dept Comp Sci Oxford England

Many variations upon the theme of parser combinators have been proposed, too many to list here, but the main idea is simple: A parser for phrases of type a is a function that takes an input string and produces results (x, rest), where x is a value of type α, and rest is the remainder of the input after the phrase with value x has been consumed. The results are often arranged into a list, because this allows a parser to signal failure with the empty list of results, an unambiguous success with one result, or multiple possibilities with a longer \'list of successes\'.

关键词： Remainder Parser Enough rest input string Themes

来源：评论

学校读者我要写书评

暂无评论

Incremental construction of minimal acyclic finite-state automata

引用

COMPUTATIONAL LINGUISTICS 2000年第1期26卷 3-16页

作者： Daciuk, J Mihov, S Watson, BW Watson, RE Gdansk Univ Technol Dept Appl Informat PL-80952 Gdansk Poland Bulgarian Acad Sci Linguist Modelling Lab LPDP BG-1040 Sofia Bulgaria Univ Pretoria Dept Comp Sci ZA-0002 Pretoria South Africa

In this paper, we describe a new method for constructing minimal, deterministic, acyclic finite-state automata from a set of strings. Traditional methods consist of two phases: the first to construct a trie, the second one to minimize it. Our approach is to construct a minimal automaton in a single phase by adding new strings one by one and minimizing the resulting automaton on-the-fly. We present a general algorithm as well as a specialization that relies upon the lexicographical ordering oft he input strings. Our method is fast and significantly lowers memory requirements in comparison to other methods.

关键词： Automata TWO-PHASE Specialization Minimal single phase Fasting new methods generalized algorithm input string Robot memory requirements Cosmic strings

来源：评论

学校读者我要写书评

暂无评论

Fast approximate search in large dictionaries

引用

COMPUTATIONAL LINGUISTICS 2004年第4期30卷 451-477页

作者： Mihov, S Schulz, KU Bulgarian Acad Sci Inst Parallel Proc Linguist Modelling Dept BU-1113 Sofia Bulgaria Univ Munich Ctr Informat & Sprachverarbeitung D-80538 Munich Germany

The need to correct garbled strings arises in many areas of natural language processing. If a dictionary is available that covers all possible input tokens, a natural set of candidates for correcting an erroneous input P is the set of all words in the dictionary for which the Levenshtein distance to P does not exceed a given (small) bound k. In this article we describe methods for efficiently selecting such candidate sets. After introducing as a starting point a basic correction method based on the concept of a "universal Levenshtein automaton," we show how two filtering methods known from the field of approximate text search can be used to improve the basic procedure in a significant way. The first method, which uses standard dictionaries plus dictionaries with reversed words, leads to very short correction times for most classes of input strings. Our evaluation results demonstrate that correction times for fixed-distance bounds depend on the expected number of correction candidates, which decreases for longer input words. Similarly the choice of an optimal filtering method depends on the length of the input words.

关键词： CONTEXTUAL WORD RECOGNITION TEXT RECOGNITION SPELLING CORRECTION CONSTRUCTION ALGORITHM stringS MATCHES ERRORS SYSTEM Levenshtein distance Printed text recognition algorithms input string Dictionaries as Topic input word Cosmic strings

来源：评论

学校读者我要写书评

暂无评论

On mobile agent verifiable problems

引用

INFORMATION AND COMPUTATION 2018年第0期260卷 51-71页

作者： Bampas, Evangelos Ilcinkas, David Aix Marseille Univ LIS Marseille France CNRS Marseille France CNRS LaBRI Bordeaux France Univ Bordeaux Bordeaux France

We consider decision problems that are solved in a distributed fashion by synchronous mobile agents operating in an unknown, anonymous network. Each agent has a unique identifier and an input string and they have to decide collectively a property which may involve their input strings, the graph on which they are operating, and their particular starting positions. Building on recent work by Fraigniaud and Pelc [J. Parallel Distrib. Comput, vol. 109, pp. 117-128], we introduce several natural new computability classes allowing for a finer classification of problems below MAV or its complement class co-MAV, the former being the class of problems that are verifiable when the agents are provided with an appropriate certificate. We provide inclusion and separation results among all these classes. We also determine their closure properties with respect to set-theoretic operations. Our main technical tool, which is of independent interest, is a new metaprotocol that enables the execution of a possibly infinite number of mobile agent protocols essentially in parallel, similarly to the well-known dovetailing technique from classical computability theory. (C) 2018 Elsevier Inc. All rights reserved.

关键词： Legal Executions computability Unique Identifier KLHL2 gene Agents Computation theory input string closure property Classes Mobile agents

来源：评论

学校读者我要写书评

暂无评论

Fast motif recognition via application of statistical thresholds

引用

BMC BIOINFORMATICS 2010年第Sup1期11卷 1-8页

作者： Boucher, Christina King, James Univ Waterloo David R Cheriton Sch Comp Sci Waterloo ON N2L 3G1 Canada McGill Univ Sch Comp Sci Montreal PQ Canada

Background: Improving the accuracy and efficiency of motif recognition is an important computational challenge that has application to detecting transcription factor binding sites in genomic data. Closely related to motif recognition is the CONSENSUS string decision problem that asks, given a parameter d and a set of l-length strings S = {s(1), ... , s(n)}, whether there exists a consensus string that has Hamming distance at most d from any string in S. A set of strings S is pairwise bounded if the Hamming distance between any pair of strings in S is at most 2d. It is trivial to determine whether a set is pairwise bounded, and a set cannot have a consensus string unless it is pairwise bounded. We use CONSENSUS string to determine whether or not a pairwise bounded set has a consensus. Unfortunately, CONSENSUS string is NP-complete. The lack of an efficient method to solve the CONSENSUS string problem has caused it to become a computational bottleneck in MCL-WMR, a motif recognition program capable of solving difficult motif recognition problem instances. Results: We focus on the development of a method for solving CONSENSUS string quickly with a small probability of error. We apply this heuristic to develop a new motif recognition program, sMCL-WMR, which has impressive accuracy and efficiency. We demonstrate the performance of sMCL-WMR in detecting weak motifs in large data sets and in real genomic data sets, and compare the performance to other leading motif recognition programs. In our preliminary discussion of our CONSENSUS string algorithm we give insight into the issue of sampling pairwise bounded sets, and discuss its relevance to motif recognition. Conclusion: Our novel heuristic gives birth to a state of the art program, sMCL-WMR, that is capable of detecting weak motifs in data sets with a large number of strings. sMCL-WMR is orders of magnitude faster than its predecessor MCL-WMR and is capable of solving previously unsolved synthetic motif recognition pro

关键词： Weak Motif Motif Recognition input string Graph Cluster Position Weight Matrix

来源：评论

学校读者我要写书评

暂无评论

Learning dependency translation models as collections of finite-state head transducers

引用

COMPUTATIONAL LINGUISTICS 2000年第1期26卷 45-60页

作者： Alshawi, H Bangalore, S Douglas, S AT&T Labs Res Shannon Lab Florham Pk NJ 07932 USA

The paper defines weighted head transducers,finite-state machines that perform middle-out st ring transduction. These transducers are strictly more expressive than the special case of standard left-to-right finite-state transducers. Dependency transduction models are then defined as collections of weighted head transducers that are applied hierarchically A dynamic programming search algorithm is described for finding the optimal transduction of an input string with respect to a dependency transduction model. A method for automatically training a dependency transduction model from a set of input-output example strings is presented. The method first searches for hierarchical alignments of the training examples guided by correlation statistics, and then constructs the transitions of head transducers that are consistent with these alignments. Experimental results are given for applying the training method to translation from English to Spanish and Japanese.

关键词： .dynamic programming strings Finite-State training examples Translation Models input string Learning Dependency Head Transducers weighted head middle-out dependency transduction model hierarchical alignments training method

来源：评论

学校读者我要写书评

暂无评论

Stochastic phonographic transduction for English

引用

COMPUTER SPEECH AND LANGUAGE 1996年第2期10卷 133-153页

作者： Luk, RWP Damper, RI HONG KONG POLYTECH DEPT COMPKOWLOONHONG KONG

This paper introduces and reviews stochastic phonographic transduction (SPT), a trainable (''data-driven'') technique for letter-to-phoneme conversion based on formal language theory, as well as describing and detailing one particularly simple realization of SPT. The spellings and pronunciations of English words are modelled as the productions of a stochastic grammar, inferred from example data in the form of a pronouncing dictionary. The terminal symbols of the grammar are letter-phoneme correspondences, and the rewrite (production) rules of the grammar specify how these are combined to form acceptable English word spellings and their pronunciations. Given the spelling of a word as input, a pronunciation can then be produced as output by parsing the input string according to the letter-part of the terminals and selecting the ''best'' sequence of corresponding phoneme-parts according to some well-motivated criteria. Although the formalism is in principle very general, restrictive assumptions must be made if practical, trainable systems are to be realized. We have assumed at this stage that the grammar is regular. Further, word generation is modelled as a Markov process in which terminals (correspondences) are simply concatenated. The SPT learning task then amounts to the inference of a set of correspondences and estimation from the training data of their associated transition probabilities. Transduction to produce a pronunciation for a word given its spelling is achieved by Viterbi decoding, using a maximum likelihood criterion. Results are presented for letter-phoneme alignment and transduction for the dictionary training data, unseen dictionary words, unseen proper nouns and novel (pseudo-)words. Two different ways of inferring correspondences are described and compared. It is found that the provision of quite limited information about the alternating vowel/consonant structure of words aids the inference process significantly. Best transduction performance obtaine

关键词： English input string Dictionaries as Topic Word AGXT gene Pronunciation syntax English language Spelling formal language theory Device Terminal Transduction Markov chain Viterbi decoding

来源：评论

学校读者我要写书评

暂无评论

Finite automata over free groups

引用

INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION 2000年第6期10卷 725-737页

作者： Dassow, J Mitrana, V Otto Von Guericke Univ Fak Informat D-39016 Magdeburg Germany Univ Bucharest Fac Math Bucharest 70109 Romania

Finite automata are extended by adding an element of a given group to each of their configurations. An input string is accepted if and only if the neutral element of the group is associated to a final configuration reached by the automaton. We get a new characterisation of the context-free languages as soon as the considered group is the binary free group. The result cannot be carried out in the deterministic case. Some remarks about finite automata over other groups are also presented.

关键词： Automata context-free languages input string If and only if finite automata

来源：评论

学校读者我要写书评

暂无评论

Unbounded length contexts for PPM

引用

COMPUTER JOURNAL 1997年第2-3期40卷 67-75页

作者： Cleary, JG Teahan, WJ Department of Computer Science University of Waikato Hamilton New Zealand Email: jcleary{at}cs.waikato.ac.nz wjt{at}cs.waikato.ac.nz

The PPM data compression scheme has set the performance standard in lossless compression of text throughout the past decade, PPM is a finite context statistical modelling technique that can be viewed as blending together several fixed-order context models to predict the next character in the input sequence, This paper gives a brief introduction to PPM, and describes a variant of the algorithm, called PPM*, which exploits contexts of unbounded length. Although requiring considerably greater computational resources (in both time and space), this reliably achieves compression superior to the benchmark PPMC version, Its major contribution is that it shows that the full. information available by considering all substrings of the input string can be used effectively to generate high-quality predictions, Hence, it provides a useful tool for exploring the bounds of compression.

关键词： Data-compression scheme Performance metrics input string compression lossless compression Pulse position modulation

来源：评论

学校读者我要写书评

暂无评论

On the emergence of rules in neural networks

引用

NEURAL COMPUTATION 2002年第9期14卷 2245-2268页

作者： Hanson, SJ Negishi, M Rutgers State Univ Dept Psychol Newark NJ 07102 USA

A simple associationist neural network learns to factor abstract rules (i.e., grammars) from sequences of arbitrary input symbols by inventing abstract representations that accommodate unseen symbol sets as well as unseen but similar grammars. The neural network is shown to have the ability to transfer grammatical knowledge to both new symbol vocabularies and new grammars. Analysis of the state-space shows that the network learns generalized abstract structures of the input and is not simply memorizing the input strings. These representations are context sensitive, hierarchical, and based on the state variable of the finite-state machines that the neural network has learned. Generalization to new symbol sets or grammars arises from the spatial nature of the internal representations used by the network, allowing new symbol sets to be encoded close to symbol sets that have already been learned in the hidden unit space of the network. The results are counter to the arguments that learning algorithms based on weight adaptation after each exemplar presentation (such as the long term potentiation found in the mammalian nervous system) cannot in principle extract symbolic knowledge from positive examples as prescribed by prevailing human linguistic theory and evolutionary psychology.

关键词： Signs and symbols Nervous System Internal representations Emergence input string Evolutionary Psychology SETTING Rule Long-Term Potentiation learning algorithms syntax network learning Neural network State variable

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：