Bibliography | Petersen, Holger: A Census Technique for Simple Computing Devices. University of Stuttgart, Faculty of Computer Science, Technical Report No. 1997/07. 11 pages, english.
|
CR-Schema | F.1.1 (Models of Computation) F.1.3 (Complexity Classes) F.4.3 (Formal Languages)
|
Abstract | We develop a technique that uses pebbles in a very economical way for simulating a multi-counter automaton on a sequence of input strings and maintain a count of those strings accepted by the counter automaton. Based on this result we show the failure of a previously proposed method for constructing witness sets separating classes of languages accepted by pebble automata with an increasing number of pebbles. We also give a recognition algorithm for another family of languages suspected to separate the lower levels of the hierarchy.
|
Full text and other links | HTML (generated from PostScript)
|
Department(s) | University of Stuttgart, Institute of Computer Science, Theoretical Computer Science
|
Entry date | June 30, 1997 |
---|