With multicore processors bringing parallel computing to the masses, there is an urgent need to make...
Lecture Series on Programming Languages by Dr.S.Arun Kumar, Department of Computer Science & Enginee...
Keine Beschreibung verfügbar
Lecture Series on Programming Languages by Dr.S.Arun Kumar, Department of Computer Science & Enginee...
Keine Beschreibung verfügbar
citeseer |
(0) (0 Votes)
|
Views: (1163) Date: (08-04-09) Pages: () |
Abstract: The central claim of the paper is that NL stringsets are regular. Three independent arguments are offered in favor of this position: one based on parsimony considerations, one employing the McCullogh-Pitts (1943) model of neurons, and a purely linguistic one. It is possible to derive explicit upper bounds for the number of (live) states in NL acceptors: the results show that finite state NL parsers can be implemented on presentday computers. The position of NL stringsets within the regular family is also investigated: it is proved that NLs are counter-free, but not locally testable. 0