Detail práce
New Parallel and Regulated Automata and Grammars
Tato práce zkoumá a zavádí čtyři nové jazykové modely se zaměřením na regulované a paralelní verze automatů a gramatik. První z modelů, stavově synchronizované systémy automatů, zavádí systémy složené z konečného počtu zásobníkových automatů jejichž činnost je řízena slovy z řídícího jazyka nad množinou stavů. Druhý model, neomezené hluboké zásobníkové automaty, je variantou hlubokých zásobníkových automatů z nichž bylo sejmuto omezení kladené na hloubku expanze na zásobníku. Třetí model, skákající čisté gramatiky, zavádí skákající gramatiky bez neterminálních symbolů. Poslední model, k#$-přepisující systémy, rozšiřuje #-přepisující systémy o přídavnou zásobníkovou paměť.
Text této práce je členěn do tří částí. První část uvádí motivaci k zavedení studovaných jazykových modelů a zasazuje je do kontextu souvisejících oblastí teorie formálních jazyků. Je zde také uveden přehled o celkové organizaci práce, základních pojmů teorie formálních jazyků a současných poznatků souvisejících s předmětem výzkumu. Druhá část tvoří jádro této práce. Jsou v ní formálně definovány všechny nově zavedené jazykové modely a studována jejich vyjadřovací síla. Poslední část uzavírá tuto práci souhrnem získaných teoretických výsledků společně se souvisejícími otevřenými problémy a nastiňuje cesty dalšího výzkumu spolu s výhledy na možná využití.
teorie formálních jazyků, 0L jazyky, čisté bezkontextové jazyky, rekurzivně vyčíslitelné jazyky, konečný index, nekonečná hierarchie, automaty, zásobník, zásobníkové automaty, systémy automatů, hluboké zásobníkové automaty, stavově-synchronizované systémy automatů, neomezené hluboké zásobníkové automaty, gramatiky, čisté gramatiky, skákající gramatiky, skákající čisté gramatiky, přepisování, paralelní přepisování, skákající přepisování, přepisující systémy, #-přepisující systémy, k#$-přepisující systémy
@phdthesis{FITPT692,
author = "Ji\v{r}\'{i} Ku\v{c}era",
type = "Diserta\v{c}n\'{i} pr\'{a}ce",
title = "New Parallel and Regulated Automata and Grammars",
school = "Vysok\'{e} u\v{c}en\'{i} technick\'{e} v Brn\v{e}, Fakulta informa\v{c}n\'{i}ch technologi\'{i}",
year = 2022,
location = "Brno, CZ",
language = "english",
url = "https://www.fit.vut.cz/study/phd-thesis/692/"
}