Praca doktorska
Licencja
Korzystanie z tego materiału możliwe jest zgodnie z właściwymi przepisami o dozwolonym użytku lub o innych wyjątkach przewidzianych w przepisach prawa. Korzystanie w szerszym zakresie wymaga uzyskania zgody uprawnionego.Uniformisation and Choice Questions for Regular Languages
| dc.abstract.en | A uniformisation of a binary relation R⊆X×Y assigns to each element x of the domain of R a particular y∈Y such that the pair〈x,y〉is in the relation. The regular-uniformisation problem asks if, in the context of words or trees, every regular relation admits a uniformisation that is also regular, idefinable in Monadic Second-Order Logic (MSO). It is already known that the answer to this question is positive in the context of finite and infinite words. In this thesis, we search for possible generalisations of these results. First, we study the possibility of uniformising relations of finite words in fragments of First-Order Logic (FO), the formalism where one can quantify over positions but not over sets of positions. We rely on algebraic characterisations of these fragments in order to emphasise their limitations in providing uniformisations. We also discuss the decidability of uniformising given regular relations in some of these fragments. Second, we highlight the strong connection between uniformisations and the expressive power of the considered formalisms. Namely, among varieties of regular languages, the assumption that the given formalism has uniformisation property, already guarantees the full power of all regular languages. The notion of a variety of languages is a standard concept which guarantees certain natural closure properties, such as closure under Boolean operations. Third, we study the possibility to uniformise regular relations of words defined over finitary domains: those are the domains that are infinite but admit a particular kind of finite representation. We show that, over these domains, the only obstacle to regular uniformisations is the existence of non-trivial automorphisms, meaning bijective functions that preserve the order and that are not the identity function. We also prove that, in this context of finitary domains, the regular-uniformisation problem is equivalent to being able to define in MSO natural objects over the domain, such as choice functions and well orders. All these results provide a broad perspective on the notion of uniformisation in the realm of subclasses and variants of regular languages. |
| dc.abstract.en | Uniformizacja relacji binarnej R⊆X×Y przypisuje, dla każdego elementu x z dziedziny R pewien unikalny element y∈Y w taki sposób by para〈x,y〉należała do relacji R. Problem regularnej uniformizacji pyta czy, w kontekście słów lub drzew, każda regularna relacja posiada uniformizację która również jest regularna, czyli definiowalna w monadycznej logice drugiego rzędu (MSO). Wiadomym jest, że odpowiedź na to pytanie jest pozytywna w przypadku skończonych i nie skończonych słów. W ramach tej rozprawy szukamy możliwych rozszerzeń tych wyników. Po pierwsze, studiujemy możliwość uniformizacji relacji słów skończonych we fragmentach logiki pierwszego rzędu (FO), formalizmu gdzie możliwa jest kwantyfikacja po pozycjach danej struktury, ale nie po zbiorach takich pozycji. Polegamy przy tym na algebraicznych charakteryzacjach rozważanych fragmentów by unaocznić ich ograniczenia w możliwości definiowania uniformizacji. Dodatkowo badamy problem rozstrzygania uniformizowalności danej regularnej relacji w niektórych rozważanych fragmentach. Po wtóre, podkreślamy silne związki pomiędzy uniformizacjami a siłą wyrazu rozważanych formalizmów. Dokładniej, wśród rozmaitości języków regularnych, założenie że danyformalizm posiada własność uniformizacji gwarantuje nam pełną siłę wyrazu wszystkich języków regularnych. Użyty tu koncept rozmaitości języków jest standardowym pojęciem gwarantującym pewne naturalne własności domknięcia, jak domknięcie ze względu na operacje boolowskie. Po trzecie, studiujemy możliwość uniformizacji relacji regularnych na słowach definiowanych nad dziedzinami finitarnymi: dziedzinami które są nieskończone, ale dopuszczają pewien szczególny rodzaj skończonej reprezentacji. Wykazujemy, że nad tymi dziedzinami, jedyną przeszkodą ku istnieniu regularnych unifomizacji jest istnienie nietrywialnych automorfizmów, czyli bijekcji które zachowują porządek, ale nie są identycznościowe. Dodatkowo wykazujemy, że w kontekście dziedzin finitarnych, problem regularnej uniformizowalności jest równoważny możliwości zdefiniowania z ramach MSO pewnych naturalnych obiektów nad daną dziedziną, jak funkcje wyboru, czy dobre porządki. Wszystkie te wyniki dostarczają szerokiej perspektywy na pojęcie uniformizacji w sferze podklas i wariantów języków regularnych. |
| dc.affiliation.department | Wydział Matematyki, Informatyki i Mechaniki |
| dc.contributor.author | Michielini, Vincent |
| dc.date.accessioned | 2022-07-21T07:56:47Z |
| dc.date.available | 2022-07-21T07:56:47Z |
| dc.date.defence | 2022-05-23 |
| dc.date.issued | 2022-07-21 |
| dc.description.additional | Link archiwalny https://depotuw.ceon.pl/handle/item/4271 |
| dc.description.promoter | Skrzypczak, Michał |
| dc.description.promoter | Lhote, Nathan (promotor pomocniczy) |
| dc.identifier.uri | https://repozytorium.uw.edu.pl//handle/item/4271 |
| dc.language.iso | en |
| dc.rights | FairUse |
| dc.subject.en | Algebraic Structures |
| dc.subject.en | Monadic Second-Order Logic |
| dc.subject.en | Choice |
| dc.subject.en | Uniformisation |
| dc.subject.en | Struktury Algebraiczne |
| dc.subject.en | Monadyczna Logika Drugiego Rzędu |
| dc.subject.en | Wybór |
| dc.subject.en | Uniformizacja |
| dc.title | Uniformisation and Choice Questions for Regular Languages |
| dc.title.alternative | Pytania o uniformizację i wybór dla języków regularnych |
| dc.type | DoctoralThesis |
| dspace.entity.type | Publication |