Centralized Versions of Jumping Finite Automata

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Centralized Versions of Jumping Finite Automata

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Centralized Versions of Jumping Finite Automata

Popis výsledku anglicky

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.

Druh

C - Kapitola v odborné knize

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2025

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název knihy nebo sborníku

Languages of Cooperation and Communication: Erzsébeth Csuhaj-Varjú Festschrift

ISBN

978-3-031-97274-4

Počet stran výsledku

16

Strana od-do

69-84

Počet stran knihy

279

Název nakladatele

Springer Nature Switzerland AG

Místo vydání

Cham

Kód UT WoS kapitoly

—