Találati lista | Tudóstér

001-es BibID:	BIBFORM012353
Első szerző:	Leupold, Peter
Cím:	5'->3' Watson-Crick automata with several runs / Peter Leupold, Benedek Nagy
Dátum:	2010
Megjegyzések:	5'->3' WK-automata are Watson-Crick automata whose two heads start on opposite ends of the input word and always run in opposite directions. One full reading in both directions is called a run. We prove that these automata's power increases with every additional run that they can make, both for deterministic and non-deterministic machines. This defines two incomparable infinite hierarchies of language classes between the regular and the context-sensitive languages. These hierarchies are complemented with classes defined by several restricted variants of 5'->3' WK-automata like stateless automata. Finally we show that several standard problems are undecidable for languages accepted by 5'->3'· WK-automata in only one run, for example the emptiness and the finiteness problems.
Tárgyszavak:	Természettudományok Matematika- és számítástudományok idegen nyelvű folyóiratközlemény külföldi lapban
Megjelenés:	Fundamenta Informaticae. - 21 (2010), p. 1001-1021. -
További szerzők:	Nagy Benedek (1973-) (informatikus, matematikus)
Internet cím:	Intézményi repozitóriumban (DEA) tárolt változat
Borító:
Saját polcon:

001-es BibID:	BIBFORM020794
Első szerző:	Nagy Benedek (informatikus, matematikus)
Cím:	Hierarchies of Stateless Multicounter 5· -> 3· Watson-Crick Automata Languages / Benedek Nagy, László Hegedüs, Ömer Eğecioğlu
Dátum:	2011
ISSN:	0169-2968
Megjegyzések:	We consider stateless counter machines which mix the features of one-head counter machines and a special type of two-head Watson-Crick automata (WK-automata). Our Watson-Crick counter machines are biologically motivated. They have two heads that read the input starting from the two extremes. The reading process is finished when there are no more symbols between the heads, i.e., every letter of the input is processed by either head. Depending on whether the heads are required to advance at each move, we distinguish between realtime and non-realtime machines. If every counter makes at most k alternations between nondecreasing and decreasing modes in every computation, then the machine is k-reversal. It is reversal bounded if it is k-reversal for some k. In this paper we concentrate on the properties of both deterministic and nondeterministic stateless WK-automata with reversal bounded counters.
Tárgyszavak:	Természettudományok Matematika- és számítástudományok idegen nyelvű folyóiratközlemény külföldi lapban Fizikai-, Számítás- és Anyagtudomány
Megjelenés:	Fundamenta Informaticae. - 110 (2011), p. 1-13. -
További szerzők:	Hegedüs László (1987-) (informatikus, matematikus) Eǧecioǧlu, Ömer
Pályázati támogatás:	TÁMOP-4.2.1/B-09/1/KONV-2010-0007 TÁMOP Kriptográfia algoritmusok és protokollok
Internet cím:	Intézményi repozitóriumban (DEA) tárolt változat DOI
Borító:
Saját polcon: