Detail publikace

Centralized Versions of Jumping Finite Automata

MEDUNA, A.; FOLTÝN, Z. Centralized Versions of Jumping Finite Automata. In Languages of Cooperation and Communication: Erzsébeth Csuhaj-Varjú Festschrift. Lecture Notes in Computer Science. Lecture Notes in Computer Science. Cham: Springer Nature Switzerland AG, 2025. p. 69-84. ISBN: 978-3-031-97274-4. ISSN: 0302-9743.
Název česky
Centralizované verze skákajících konečných automatů
Typ
kapitola v knize
Jazyk
anglicky
Autoři
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
Foltýn Zdeněk
URL
Klíčová slova

Discontinuous computation, Jumping finite automata, Centralized versions, Linear
grammars and languages, Special cases, Identities between language families

Abstrakt

Publikace zavádí centralizované verze skákajících konečných automatů
a principiálně zdůvodňuje jejich zavedení z hlediska dnešních nespojitých
výpočtů. V podstatě tato centralizovaná verze, C, pracuje jako původní
necentralizovaná verze těchto automatů až na to, že  C obsahuje speciální
prostřední symbol, #, jehož jediný výskyt je vždy vložen doprostřed vstupního
slova, ww. C provádí skok tak, že nahradí podslovo obsahující # jediným symbolem
#. Pokud provedením posloupnosti  skoků tímto centralizovaným způsobem bude
vymazáno celé ww kromě jediného symbolu #, pak C přijímá ww; množina přijímaných
slov tvoří jazyk přijímaný pomocí C. Publikace ukazuje, že výsledná třída jazyků
centralizované verze skákajících automatů odpovídá lineárním jazykům. Dále
publikace definuje několik speciálních případů těchto centralizovaných
skákajících automatů a demonstruje jejich ekvivalenci se speciálními typy
lineárních jazyků jako jsou minimální a vyvážené lineární gramatiky. Nakonec
z pohledu teorie formálních jazyků jsou všechny verze centralizovaných
skákajících konečných autmoatů zkoumány jako automatové modely pro lineární
a podobné gramatiky. 

Rok
2025
Strany
69–84
Časopis
Lecture Notes in Computer Science, ISSN 0302-9743
Kniha
Languages of Cooperation and Communication: Erzsébeth Csuhaj-Varjú Festschrift
Řada
Lecture Notes in Computer Science
ISBN
978-3-031-97274-4
Vydavatel
Springer Nature Switzerland AG
Místo
Cham
DOI
10.1007/978-3-031-97274-4_5
EID Scopus
2-s2.0-105010613405
BibTeX 
@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"
}
Nahoru