Fast parallel language recognition by cellular automata

Oscar H. Ibarra; Michael A. Palis; Sam M. Kim

doi:https://doi.org/10.1016/0304-3975(85)90073-8

Fast parallel language recognition by cellular automata

Oscar H. Ibarra, Michael A. Palis, Sam M. Kim

Research output: Contribution to journal › Article › peer-review

Abstract

We look at linear cellular automata (CA's) which accept an input if and only if at some time during the computation all the processors in the array are in accepting states. We prove that there are noncontext-free languages that are accepted by CA's in O(log n) time. Moreover, this is the best possible since o(log n) time CA's can accept only regular sets. We show that one-way CA's operating in T(n) time can be simulated by CA's in 1 2(T(n) + 1) time. As a corollary, CA's can accept the linear, Dyck, and bracketed context-free languages in 1 2(n + 1) time, which is again optimal. We also study CA's with other modes of acceptance and derive results concerning speed-up, hierarchy, etcetera.

Original language	American English
Pages (from-to)	231-246
Number of pages	16
Journal	Theoretical Computer Science
Volume	41
Issue number	C
DOIs	https://doi.org/10.1016/0304-3975(85)90073-8
State	Published - 1985
Externally published	Yes

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Keywords

Cellular automaton
constant time
context-free language
log n time

Access to Document

https://doi.org/10.1016/0304-3975(85)90073-8

Cite this

@article{4986cc550b544436b2fd57a63edc757e,

title = "Fast parallel language recognition by cellular automata",

abstract = "We look at linear cellular automata (CA's) which accept an input if and only if at some time during the computation all the processors in the array are in accepting states. We prove that there are noncontext-free languages that are accepted by CA's in O(log n) time. Moreover, this is the best possible since o(log n) time CA's can accept only regular sets. We show that one-way CA's operating in T(n) time can be simulated by CA's in 1 2(T(n) + 1) time. As a corollary, CA's can accept the linear, Dyck, and bracketed context-free languages in 1 2(n + 1) time, which is again optimal. We also study CA's with other modes of acceptance and derive results concerning speed-up, hierarchy, etcetera.",

keywords = "Cellular automaton, constant time, context-free language, log n time",

author = "Ibarra, {Oscar H.} and Palis, {Michael A.} and Kim, {Sam M.}",

note = "Funding Information: *This research was supported in part by NSF Grant MCS 83-04756.",

year = "1985",

doi = "https://doi.org/10.1016/0304-3975(85)90073-8",

language = "American English",

volume = "41",

pages = "231--246",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

number = "C",

}

TY - JOUR

T1 - Fast parallel language recognition by cellular automata

AU - Ibarra, Oscar H.

AU - Palis, Michael A.

AU - Kim, Sam M.

N1 - Funding Information: *This research was supported in part by NSF Grant MCS 83-04756.

PY - 1985

Y1 - 1985

N2 - We look at linear cellular automata (CA's) which accept an input if and only if at some time during the computation all the processors in the array are in accepting states. We prove that there are noncontext-free languages that are accepted by CA's in O(log n) time. Moreover, this is the best possible since o(log n) time CA's can accept only regular sets. We show that one-way CA's operating in T(n) time can be simulated by CA's in 1 2(T(n) + 1) time. As a corollary, CA's can accept the linear, Dyck, and bracketed context-free languages in 1 2(n + 1) time, which is again optimal. We also study CA's with other modes of acceptance and derive results concerning speed-up, hierarchy, etcetera.

AB - We look at linear cellular automata (CA's) which accept an input if and only if at some time during the computation all the processors in the array are in accepting states. We prove that there are noncontext-free languages that are accepted by CA's in O(log n) time. Moreover, this is the best possible since o(log n) time CA's can accept only regular sets. We show that one-way CA's operating in T(n) time can be simulated by CA's in 1 2(T(n) + 1) time. As a corollary, CA's can accept the linear, Dyck, and bracketed context-free languages in 1 2(n + 1) time, which is again optimal. We also study CA's with other modes of acceptance and derive results concerning speed-up, hierarchy, etcetera.

KW - Cellular automaton

KW - constant time

KW - context-free language

KW - log n time

UR - http://www.scopus.com/inward/record.url?scp=0022313512&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0022313512&partnerID=8YFLogxK

U2 - https://doi.org/10.1016/0304-3975(85)90073-8

DO - https://doi.org/10.1016/0304-3975(85)90073-8

M3 - Article

SN - 0304-3975

VL - 41

SP - 231

EP - 246

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - C

ER -

Fast parallel language recognition by cellular automata

Abstract

ASJC Scopus subject areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this