Centralized Versions of Jumping Finite Automata
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F26%3A0198411" target="_blank" >RIV/00216305:26230/26:0198411 - isvavai.cz</a>
Result on the web
<a href="https://link.springer.com/book/10.1007/978-3-031-97274-4" target="_blank" >https://link.springer.com/book/10.1007/978-3-031-97274-4</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-031-97274-4_5" target="_blank" >10.1007/978-3-031-97274-4_5</a>
Alternative languages
Result language
angličtina
Original language name
Centralized Versions of Jumping Finite Automata
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
C - Chapter in a specialist book
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
—
Continuities
S - Specificky vyzkum na vysokych skolach
Others
Publication year
2025
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Book/collection name
Languages of Cooperation and Communication: Erzsébeth Csuhaj-Varjú Festschrift
ISBN
978-3-031-97274-4
Number of pages of the result
16
Pages from-to
69-84
Number of pages of the book
279
Publisher name
Springer Nature Switzerland AG
Place of publication
Cham
UT code for WoS chapter
—