Praca doktorska
Commutative Images of Languages Over Infinite Alphabets
| dc.abstract.en | Commutative images (Parikh images) are extensively studied for languages of finite automata and context-free grammars over finite alphabets. Parikh’s theorem is a well-known fundamental result stating that Parikh images of finite automata and context-free languages are equal, and coincide with semi-linear sets of vectors. In this thesis, we explore Parikh images for a widely studied extension of finite automata, non-deterministic register automata, which in contrast to a finite automata, input words over infinite alphabets. Our main objective is establishing to what extent Parikh’s theorem keeps holding true when one extends the setting from finite alphabets to infinite ones. As the first step, we demonstrate that semi-linear sets (suitably extended to infinite alpha bets) are not sufficient even for capturing Parikh images of one-register automata, and propose a larger class of rational sets (also suitably extended to infinite alphabets) in place thereof. This is motivated by the fact that in finite-alphabet case, semi-linear sets and rational sets of vec tors coincide. As our main result we obtain a version of Parikh’s theorem for non-deterministic one-register automata: Parikh images of their languages are always rational. Building on this result, we prove rationality of languages of hierarchical register automata, a syntactic subclass of non-deterministic register automata strictly extending one-register automata. Furthermore, also building on the main result, we show that the language of every one-register context-free grammar has rational Parikh image, and is therefore Parikh-equivalent to the language of some non-deterministic (and even hierarchical) register automaton. All the above-mentioned results may be seen as a partial confirmation of validity of Parikh’s theorem in the setting of infinite alphabets. Nevertheless, it still remains open if Parikh images of languages of all non-deterministic register automata are rational. Likewise, we do not know if the same property holds for languages of all context-free grammars. If this property holds, it would yield the full generalisation of Parikh’s theorem to infinite alphabets. |
| dc.abstract.en | Obrazy przemienne (obrazy Parikha) języków regularnych, językow bezkontekstowych i innych klas języków, są od zarania informatyki obiektem intensywnych badań. Szeroko znane i często stosowane twierdzenie Parikha to fundamentalny wynik o równości obrazów przemiennych jęyków bezkontekstowych i regularnych. Ponadto obrazy te są zawsze zbiorami semiliniowymi. W niniejszej rozprawie badamy własności obrazów przemienne języków rozpoznawanych przez au tomaty rejestrowe, stanowiące rozszerzenie automatów skończonych do alfabetów nieskończonych. Głównym celem rozprawy jest ustalenie, w jakim stopniu twierdzenie Parikha pozostaje prawdziwe dla alfabetów nieskończonych. Jako pierwszy krok pokazujemy, że zbiory semiliniowe (w wersji odpowiednio rozszerzonej do alfabetów nieskończonych) nie są wystarczające, mianowicie obrazy przemienne języków rozpoz nawanych przez automaty rejestrowe mogą nie być semiliniowe. W związku z tym proponu jemy inny formalizm, w przypadku alfabetów skończonych równoważny zbiorom semiliniowym, mianowicie zbiory regularne (ang. rational), czyli zbiory definiowalne za pomocą wyrażeń reg ularnych, znów w wersji odpowiednio rozszerzonej do alfabetów nieskończonych. Centralnym i najtrudniejszym wynikiem rozprawy jest wersja twierdzenia Parikha dla automatów z jednym rejestrem: obrazy przemienne języków rozpoznawanych przez te automaty są zawsze regularne. Opierając się na tym zaskakująco trudnym do uzyskania wyniku pokazujemy dodatkowo, że obrazy przemienne języków rozpoznawanych przez większą klasę automatów rejestrowych, mi anowicie przez tzw. hierarchiczne automaty rejestrowe, są również regularne. Ponadto, znów wykorzystując powyższy centralny wynik pokazujemy, że obrazy przemienne języków bezkon tekstowych z jednym rejestrem (języki generowane przez gramatyki bezkontekstowe z jednym rejestrem) są także regularne, a zatem przemiennie równoważne automatom rejestowym (a nawet hierarchicznym). Powyższe wyniki stanowią częściowe potwierdzenie prawdziwości twierdzenie Parikha dla alfabetów nieskończonych. Wciąż jednak nie wiemy, czy twierdzenie to jest prawdziwe dla au tomatów z dowolną liczbą rejestrów, które nie są hierarchiczne. Nie wiemy także, czy podobną własność mają języki bezkontekstowe z dowolną liczbą rejestrów. W rozprawa stawiamy hipotezę, że tak w rzeczywistości jest. |
| dc.affiliation.department | Wydział Matematyki, Informatyki i Mechaniki |
| dc.contributor.author | Pattathurajan, Mohnish |
| dc.date.accessioned | 2023-10-03T08:04:31Z |
| dc.date.available | 2023-10-03T08:04:31Z |
| dc.date.defence | 2023-10-13 |
| dc.date.issued | 2023-10-03 |
| dc.description.additional | Link archiwalny https://depotuw.ceon.pl/handle/item/4690 |
| dc.description.promoter | Lasota, Sławomir |
| dc.description.promoter | Hofman, Piotr |
| dc.identifier.uri | https://repozytorium.uw.edu.pl//handle/item/4690 |
| dc.language.iso | en |
| dc.rights | ClosedAccess |
| dc.subject.en | rational language |
| dc.subject.en | rational set |
| dc.subject.en | register context-free language |
| dc.subject.en | register automaton |
| dc.subject.en | commutative image |
| dc.subject.en | Parikh image |
| dc.subject.en | automaton |
| dc.subject.en | języki regularne |
| dc.subject.en | wyrażenia regularne |
| dc.subject.en | rejestrowa gramatyka bezkontekstowa |
| dc.subject.en | automat rejestrowy |
| dc.subject.en | obraz przemienny |
| dc.subject.en | obraz Parikha |
| dc.subject.en | automat skonczony |
| dc.title | Commutative Images of Languages Over Infinite Alphabets |
| dc.title.alternative | Obrazy przemienne języków nad alfabetami nieskończonymi |
| dc.type | DoctoralThesis |
| dspace.entity.type | Publication |