Detail výsledku
Centralized Versions of Jumping Finite Automata
Foltýn Zdeněk, Bc.
The present paper introduces centralized versions of jumping finite automata and
gives the principal reason for their introduction in terms of today's
discontinuous computation in practice. In essence, a centralized version, C,
works just like the original uncentralized version of these automata except that
C contains a special central symbol, #, whose single occurrence is always
inserted into an input word, ww. C performs a jump in such a way that it replaces
a subword containing # with one #. If, by making a sequence of jumps in this
centralized way, it eventually wipes outall ww with # as the only symbol
unerased, C accepts ww; the set of all accepted words in this way is the language
of C. This paper shows that the language family resulting from these centralized
versions coincides with that of linear languages. In addition, this paper defines
several special cases of these centralized versions and demonstrates their
equivalences to special cases of linear grammars, such as minimal and even linear
grammars. Consequently, in terms of the language theory, all the variety of
centralized jumping finite automata can be seen as automaton-based counterparts
to linear grammars and their special cases.
Discontinuous computation, Jumping finite automata, Centralized versions, Linear
grammars and languages, Special cases, Identities between language families
@inbook{BUT198411,
author="Alexandr {Meduna} and Zdeněk {Foltýn}",
title="Centralized Versions of Jumping Finite Automata",
booktitle="Languages of Cooperation and Communication: Erzsébeth Csuhaj-Varjú Festschrift",
year="2025",
publisher="Springer Nature Switzerland AG",
address="Cham",
series="Lecture Notes in Computer Science",
pages="69--84",
doi="10.1007/978-3-031-97274-4\{_}5",
isbn="978-3-031-97274-4",
url="https://link.springer.com/book/10.1007/978-3-031-97274-4"
}