Enhancing symbolic model checking by AI techniques
Buccafurri, Francesco ;
Eiter, Thomas ;
Gottlob, Georg ;
Leone, Nicola
Zum Volltext im pdf-Format:
Dokument 1.pdf (603 KB)
Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:hebis:26-opus-236
URL: http://geb.uni-giessen.de/geb/volltexte/1998/23/
Universität
Justus-Liebig-Universität Gießen
Institut:
Institut für Informatik
Fachgebiet:
Informatik
DDC-Sachgruppe:
Informatik
Dokumentart:
ResearchPaper
Zeitschrift, Serie:
IFIG Research Report
; 9701 / 1997
Sprache:
Englisch
Erstellungsjahr:
1997
Publikationsdatum:
23.06.1998
Kurzfassung auf Englisch:
Comparisons of different cellular devices and the investigation of their computing power can be made in terms of their capabilities to timeÂconstruct and timeÂcompute functions. TimeÂconstruction means that a distinguished cell has to enter distinguished states exactly at the time steps f(1); f(2); : : :, whereas timeÂcomputation requires the distinguished cell to enter a distinguished state firstly at time step f(n), where n is the length of the input. Here the family of functions which are timeÂconstructible by a twoÂway unbounded cellular space (F(CS)) is characterized in terms of functions which are timeÂcomputable by one of the simplest cellular devices, a oneÂway bounded cellular automaton (C (OCA)). Conceptually, timeÂconstructible functions have to be strictly increasing. Regarding that restriction the reverse characterization is shown, too. Some results concerning the structure of F(CS) and C(OCA) and their relation to formal language recognition are established.
Lizenz:
Veröffentlichungsvertrag für Publikationen ohne Print on Demand
