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: