Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
One head machines from a symbolic approach
Gajardo A., Mazoyer J. Theoretical Computer Science370 (1-3):34-47,2007.Type:Article
Date Reviewed: Jun 1 2007

This paper proposes a new computing machine model, a modified Turing machine, and studies properties of the proposed model. The major modification the authors propose is to allow for a tape in the form of a Cayley graph. In other words, their new model would build a dynamic symbol system using mathematical structures such as Turing machines, Abelian groups, pushdown automata, and Cayley graphs.

The paper consists of seven sections. Section 1 provides a brief introduction. The second section supplies background information and defines terms such as word, language, topological dynamical system, pushdown automaton, and subshift. Section 3 presents the basics of Cayley graphs. The section includes an example of a Cayley graph for two different groups. The fourth section begins by defining subshift and related terms with respect to a Turing machine; relevant properties are presented in the form of two remarks. Sections 5 and 6 present the major part of the work. They contain proofs of several major propositions describing properties of the proposed model. Section 7 concludes the paper.

The paper is highly theoretical with some examples for explanation. It is assumed that readers will have a strong background in theoretical computer science and discrete mathematics. The authors attempt to open new possibilities of research. However, they avoid showing any other applications of the work.

Reviewer:  Maulik A. Dave Review #: CR134348 (0805-0491)
Bookmark and Share
  Featured Reviewer  
 
Bounded-Action Devices (F.1.1 ... )
 
 
Algebraic Language Theory (F.4.3 ... )
 
 
Graph Algorithms (G.2.2 ... )
 
 
Formal Languages (F.4.3 )
 
 
Graph Theory (G.2.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Bounded-Action Devices": Date
Fairness and conspiracies
Best E. Information Processing Letters 18(4): 215-220, 1984. Type: Article
May 1 1985
Separating the eraser Turing machine classes Le, NLe, co-NLe and Pe
Krause M., Meinel C., Waack S. Theoretical Computer Science 86(2): 267-275, 1991. Type: Article
Jul 1 1992
Two nonlinear lower bounds for on-line computations
Dūris P., Galil Z., Paul W. (ed), Reischuk R. Information and Control 60(1-3): 1-11, 1984. Type: Article
Aug 1 1985
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy