Search Results: 1 - 10 of 100 matches for " "
All listed articles are free for downloading (OA Articles)
Page 1 /100
Display every page Item
Selected Operations, Algorithms, and Applications of n-Tape Weighted Finite-State Machines  [PDF]
André Kempe
Computer Science , 2011,
Abstract: A weighted finite-state machine with n tapes (n-WFSM) defines a rational relation on n strings. It is a generalization of weighted acceptors (one tape) and transducers (two tapes). After recalling some basic definitions about n-ary weighted rational relations and n-WFSMs, we summarize some central operations on these relations and machines, such as join and auto-intersection. Unfortunately, due to Post's Correspondence Problem, a fully general join or auto-intersection algorithm cannot exist. We recall a restricted algorithm for a class of n-WFSMs. Through a series of practical applications, we finally investigate the augmented descriptive power of n-WFSMs and their join, compared to classical transducers and their composition. Some applications are not feasible with the latter. The series includes: the morphological analysis of Semitic languages, the preservation of intermediate results in transducer cascades, the induction of morphological rules from corpora, the alignment of lexicon entries, the automatic extraction of acronyms and their meaning from corpora, and the search for cognates in a bilingual lexicon. All described operations and applications have been implemented with Xerox's WFSC tool.
Computability of the entropy of one-tape Turing Machines  [PDF]
Emmanuel Jeandel
Computer Science , 2013,
Abstract: We prove that the maximum speed and the entropy of a one-tape Turing machine are computable, in the sense that we can approximate them to any given precision $\epsilon$. This is contrary to popular belief, as all dynamical properties are usually undecidable for Turing machines. The result is quite specific to one-tape Turing machines, as it is not true anymore for two-tape Turing machines by the results of Blondel et al., and uses the approach of crossing sequences introduced by Hennie.
Theory of One Tape Linear Time Turing Machines  [PDF]
Kohtaro Tadaki,Tomoyuki Yamakami,Jack C. H. Lin
Computer Science , 2003,
Abstract: A theory of one-tape (one-head) linear-time Turing machines is essentially different from its polynomial-time counterpart since these machines are closely related to finite state automata. This paper discusses structural-complexity issues of one-tape Turing machines of various types (deterministic, nondeterministic, reversible, alternating, probabilistic, counting, and quantum Turing machines) that halt in linear time, where the running time of a machine is defined as the length of any longest computation path. We explore structural properties of one-tape linear-time Turing machines and clarify how the machines' resources affect their computational patterns and power.
Infinite time Turing machines with only one tape  [PDF]
Joel David Hamkins,Daniel Evan Seabold
Mathematics , 1999,
Abstract: Infinite time Turing machines with only one tape are in many respects fully as powerful as their multi-tape cousins. In particular, the two models of machine give rise to the same class of decidable sets, the same degree structure and, at least for functions f:R-->N, the same class of computable functions. Nevertheless, there are infinite time computable functions f:R-->R that are not one-tape computable, and so the two models of supertask computation are not equivalent. Surprisingly, the class of one-tape computable functions is not closed under composition; but closing it under composition yields the full class of all infinite time computable functions. Finally, every ordinal which is clockable by an infinite time Turing machine is clockable by a one-tape machine, except certain isolated ordinals that end gaps in the clockable ordinals.
Template-directed biopolymerization: tape-copying Turing machines  [PDF]
Ajeet K. Sharma,Debashish Chowdhury
Physics , 2012, DOI: 10.1142/S1793048012300083
Abstract: DNA, RNA and proteins are among the most important macromolecules in a living cell. These molecules are polymerized by molecular machines. These natural nano-machines polymerize such macromolecules, adding one monomer at a time, using another linear polymer as the corresponding template. The machine utilizes input chemical energy to move along the template which also serves as a track for the movements of the machine. In the Alan Turing year 2012, it is worth pointing out that these machines are "tape-copying Turing machines". We review the operational mechanisms of the polymerizer machines and their collective behavior from the perspective of statistical physics, emphasizing their common features in spite of the crucial differences in their biological functions. We also draw attention of the physics community to another class of modular machines that carry out a different type of template-directed polymerization. We hope this review will inspire new kinetic models for these modular machines.
Single-tape and Multi-tape Turing machines through the lens of the Grossone methodology  [PDF]
Yaroslav D. Sergeyev,Alfredo Garro
Computer Science , 2013,
Abstract: The paper investigates how the mathematical languages used to describe and to observe automatic computations influence the accuracy of the obtained results. In particular, we focus our attention on Single and Multi-tape Turing machines which are described and observed through the lens of a new mathematical language which is strongly based on three methodological ideas borrowed from Physics and applied to Mathematics, namely: the distinction between the object (we speak here about a mathematical object) of an observation and the instrument used for this observation; interrelations holding between the object and the tool used for the observation; the accuracy of the observation determined by the tool. Results of the observation executed by the traditional and new languages are compared and discussed.
The Roles of Advice to One-Tape Linear-Time Turing Machines and Finite Automata  [PDF]
Tomoyuki Yamakami
Computer Science , 2010,
Abstract: We discuss the power and limitation of various "advice," when it is given particularly to weak computational models of one-tape linear-time Turing machines and one-way finite (state) automata. Of various advice types, we consider deterministically-chosen advice (not necessarily algorithmically determined) and randomly-chosen advice (according to certain probability distributions). In particular, we show that certain weak machines can be significantly enhanced in computational power when randomized advice is provided in place of deterministic advice.
Verifying whether One-Tape Non-Deterministic Turing Machines Run in Time $Cn+D$  [PDF]
David Gajser
Computer Science , 2013,
Abstract: We discuss the following family of problems, parameterized by integers $C\geq 2$ and $D\geq 1$: Does a given one-tape non-deterministic $q$-state Turing machine make at most $Cn+D$ steps on all computations on all inputs of length $n$, for all $n$? Assuming a fixed tape and input alphabet, we show that these problems are co-NP-complete and we provide good non-deterministic and co-non-deterministic lower bounds. Specifically, these problems can not be solved in $o(q^{(C-1)/4})$ non-deterministic time by multi-tape Turing machines. We also show that the complements of these problems can be solved in $O(q^{C+2})$ non-deterministic time and not in $o(q^{(C-1)/2})$ non-deterministic time by multi-tape Turing machines.
Nondeterministic one-tape off-line Turing machines and their time complexity  [PDF]
Giovanni Pighizzini
Computer Science , 2009,
Abstract: In this paper we consider the time and the crossing sequence complexities of one-tape off-line Turing machines. We show that the running time of each nondeterministic machine accepting a nonregular language must grow at least as n\log n, in the case all accepting computations are considered (accept measure). We also prove that the maximal length of the crossing sequences used in accepting computations must grow at least as \log n. On the other hand, it is known that if the time is measured considering, for each accepted string, only the faster accepting computation (weak measure), then there exist nonregular languages accepted in linear time. We prove that under this measure, each accepting computation should exhibit a crossing sequence of length at least \log\log n. We also present efficient implementations of algorithms accepting some unary nonregular languages.
Managing the Acronym/Expansion Identi cation Process for Text-Mining Applications

Mathieu Roche,Violaine Prince,

软件学报 , 2008,
Abstract: This paper deals with an acronym/de nition extraction approach from textual data (corpora) and the disambiguation of these de nitions (or expansions). Both steps of our global process of acquisition and management of acronyms are precisely described. The first step consists in using markers such as brackets to identify expansion candidates. The alignment of the letters allows to select the acronym/de nition couples. The second step is to de ne the relevant expansion of an acronym in a given context. Our method is based on statistical measurements (Mutual Information, Cubic Mutual Information, Dice Measure) and the results provided by search engines. This paper presents an evaluation of the global process from real data (general and specialized domains).
Page 1 /100
Display every page Item

Copyright © 2008-2017 Open Access Library. All rights reserved.