Bibliograph. Daten | Petersen, Holger: A Census Technique for Simple Computing Devices. Universität Stuttgart, Fakultät Informatik, Fakultätsbericht Nr. 1997/07. 11 Seiten, englisch.
|
CR-Klassif. | F.1.1 (Models of Computation) F.1.3 (Complexity Classes) F.4.3 (Formal Languages)
|
Kurzfassung | 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.
|
Volltext und andere Links | HTML (aus PostScript generiert)
|
Abteilung(en) | Universität Stuttgart, Institut für Informatik, Theoretische Informatik
|
Eingabedatum | 30. Juni 1997 |
---|