Server problems and regular languages

Csaba Béla; Dányi Gábor: Server problems and regular languages. In: Acta cybernetica, (13) 1. pp. 23-39. (1997)

Előnézet

Cikk, tanulmány, mű cybernetica_013_numb_001_023-039.pdf Letöltés (907kB) | Előnézet

Absztrakt (kivonat)

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.

Mű típusa:	Cikk, tanulmány, mű
Befoglaló folyóirat/kiadvány címe:	Acta cybernetica
Dátum:	1997
Kötet:	13
Szám:	1
ISSN:	0324-721X
Oldalak:	pp. 23-39
Nyelv:	angol
Kiadás helye:	Szeged
Befoglaló mű URL:	http://acta.bibl.u-szeged.hu/38503/
Kulcsszavak:	Számítástechnika, Kibernetika
Megjegyzések:	Bibliogr.: p. 38-39. ; összefoglalás angol nyelven
Szakterület:	01. Természettudományok 01. Természettudományok > 01.02. Számítás- és információtudomány
Feltöltés dátuma:	2016. okt. 15. 12:26
Utolsó módosítás:	2022. jún. 13. 15:12
URI:	http://acta.bibl.u-szeged.hu/id/eprint/12576

Bővebben:

Tétel nézet