Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Parallel language recognition in constant time by cellular automata.
Sommerhalder R., van Westrhenen S. Acta Informatica19 (4):397-407,1983.Type:Article
Date Reviewed: Mar 1 1985

The language recognized by a cellular automaton is the set of the accepted initial configurations. For one-dimensional bounded cellular automata, the recognizable languages are the context-sensitive languages. This paper is focused on languages identified by one-dimensional cellular automata within a fixed number of steps. It is shown that such languages are precisely the finite unions of subword composable languages. L is subword composable if :9I It is shown that L is subword composable is decidable. Finally, it is shown that the languages acceptable in constant time by one dimensional nondeterministic c.a. are precisely the regular languages.

Reviewer:  W. Richard Stark Review #: CR109201
Bookmark and Share
 
Software Science (D.2.8 ... )
 
 
Bounded-Action Devices (F.1.1 ... )
 
 
Grammar Types (F.4.2 ... )
 
 
Grammars And Other Rewriting Systems (F.4.2 )
 
 
Models Of Computation (F.1.1 )
 
Would you recommend this review?
yes
no
Other reviews under "Software Science": Date
Some new observations about software science indicators for estimating software quality
Davcev D. Information Processing and Management: an International Journal 20(1-2): 245-247, 1984. Type: Article
Feb 1 1985
An empirical study of the effects of modularity on program modifiability
Korson T., Vaishnavi V. (ed)  Empirical studies of programmers (, Washington, DC,1861986. Type: Proceedings
Jul 1 1988
Identifying error-prone software--an empirical study
Shen V., Yu T., Thebaut S., Paulsen L. IEEE Transactions on Software Engineering SE-11(4): 317-324, 1985. Type: Article
Feb 1 1986
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