Detail publikace

Centralized Versions of Jumping Finite Automata

MEDUNA Alexander a FOLTýN Zdeněk. Centralized Versions of Jumping Finite Automata. Lecture Notes in Computer Science, 2025, s. 69-84. ISBN 978-3-031-97274-4. ISSN 0302-9743. Dostupné z: https://link.springer.com/book/10.1007/978-3-031-97274-4
Název česky
Centralizované verze skákajících konečných automatů
Typ
kapitola v knize
Jazyk
angličtina
Autoři
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT)
Foltýn Zdeněk (FIT VUT)
URL
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, DE
DOI
10.1007/978-3-031-97274-4_5
EID Scopus
2-s2.0-105010613405
BibTeX 
@INBOOK{FITPUB13550,
   author = "Alexander Meduna and Zden\v{e}k Folt\'{y}n",
   title = "Centralized Versions of Jumping Finite Automata",
   pages = "69--84",
   booktitle = "Languages of Cooperation and Communication: Erzs\'{e}beth Csuhaj-Varj\'{u} Festschrift",
   series = "Lecture Notes in Computer Science",
   journal = "Lecture Notes in Computer Science",
   year = 2025,
   location = "Cham, DE",
   publisher = "Springer Nature Switzerland AG",
   ISBN = "978-3-031-97274-4",
   ISSN = "0302-9743",
   doi = "10.1007/978-3-031-97274-4\_5",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/13550"
}
Nahoru