Server problems and regular languages
The sequences of requests are considered as words over the alphabet of vertices. We assume that the server problem is restricted, meaning that the request words are chosen from a subset of all possible words, i.e. from a language. We define the class ONLINE consisting of the languages, for which the...
Saved in:
| Main Authors: | |
|---|---|
| Format: | Article |
| Published: |
1997
|
| Series: | Acta cybernetica
13 No. 1 |
| Kulcsszavak: | Számítástechnika, Kibernetika |
| Subjects: | |
| Online Access: | http://acta.bibl.u-szeged.hu/12576 |
| Summary: | The sequences of requests are considered as words over the alphabet of vertices. We assume that the server problem is restricted, meaning that the request words are chosen from a subset of all possible words, i.e. from a language. We define the class ONLINE consisting of the languages, for which there exists a 1-competitive satisfying on-line algorithm. Our main result is a sufficient condition for languages to be in ONLINE and a construction method of 1-competitive on-line algorithm for the ones, which satisfy that condition. We perform this by characterizing a subclass ONREGo of the class ONLINE fl REG, where REG is the class of regular languages. Moreover, we prove some results, which help to show the on-lineness of certain other (even nonregular) languages and we give sufficient conditions to prove that a language is not on-line. |
|---|---|
| Physical Description: | 23-39 |
| ISSN: | 0324-721X |