Properties of right one-way jumping finite automata

dc.contributor.authorBeier, Simon
dc.contributor.authorHolzer, Markus
dc.date.accessioned2022-09-12T09:38:41Z
dc.date.available2018-04-24T06:45:55Z
dc.date.available2022-09-12T09:38:41Z
dc.date.issued2018
dc.description.abstractRight one-way jumping finite automata (ROWJFAs), were recently introduced in [H. Chigahara, S.Z. Fazekas, A. Yamamura: One-Way Jumping Finite Automata, Internat. J. Found. Comput. Sci., 27(3), 2016] and are jumping automata that process the input in a discontinuous way with the restriction that the input head reads deterministically from left-to-right starting from the leftmost letter in the input and when it reaches the end of the input word, it returns to the beginning and continues the computation. We solve most of the open problems of these devices. In particular, we characterize the family of permutation closed languages accepted by ROWJFAs in terms of Myhill-Nerode equivalence classes. Using this, we investigate closure and non-closure properties as well as inclusion relations to other language families. We also give more characterizations of languages accepted by ROWJFAs for some interesting cases.en
dc.identifier.urihttp://nbn-resolving.de/urn:nbn:de:hebis:26-opus-135162
dc.identifier.urihttps://jlupub.ub.uni-giessen.de//handle/jlupub/7551
dc.identifier.urihttp://dx.doi.org/10.22029/jlupub-6985
dc.language.isoende_DE
dc.relation.ispartofseriesIFIG Research Report; 1802
dc.rightsIn Copyright*
dc.rights.urihttp://rightsstatements.org/page/InC/1.0/*
dc.subjectjumping finite automataen
dc.subjectone-way restrictionen
dc.subjectcharacterizationsen
dc.subjectinclusion relationsen
dc.subjectclosure propertiesen
dc.subject.ddcddc:004de_DE
dc.titleProperties of right one-way jumping finite automataen
dc.typeworkingPaperde_DE
local.affiliationFB 07 - Mathematik und Informatik, Physik, Geographiede_DE
local.opus.fachgebietInformatikde_DE
local.opus.id13516
local.opus.instituteInstitut für Informatikde_DE

Dateien

Originalbündel
Gerade angezeigt 1 - 1 von 1
Lade...
Vorschaubild
Name:
Ifig_Report1802.pdf
Größe:
1.02 MB
Format:
Adobe Portable Document Format