Equivalence problem of transductions: algorithms based on commutative algebra

Głównym celem tej pracy jest zastosowanie Metody Hilberta do znalezienia procedur decyzyjnych rozstrzygaja˛cych problem równoważności dla różnych klas transformacji obiektów kombinatorycznych, takich jak słowa, drzewa bądź grafy. Metoda Hilberta, w zarysie, polega na znalezieniu modelu transduktora rejestrowego, który jest w stanie wyrazić daną klasę transformacji, oraz zakodowaniu obiektów kombinatorycznych używanych przez ten model za pomocą liczb całkowitych w taki sposób, że podstawowe operacje kombinatoryczne (jak, na przykład, konkatenacja słów) mogą być symulowane z użyciem operacji algebraicznych dodawania i mnożenia. W trakcie pracy rozszerzamy Metodę Hilberta dowodząc następujących lematów: (1) obiekty kombinatoryczne mogą być zakodowane w dowolnym obliczalnym pierścieniu zredukowanym, (2) jeżeli obiekty kombinatoryczne są zakodowane w ciele (zauważmy, że każde ciało jest pierścieniem zredukowanym), to również operacja dzielenia może być użyta do symulowania operacji kombinatorycznych, (3) jeżeli obiekty kombinatoryczne sa˛ zakodowane w pierścieniu wielomianów (zauważmy, że można go zanurzyć w ciało funkcji wymiernych), to również operacja podstawienia może być, z ograniczeniami, użyta do symulowania operacji kombinatorycznych. W rozdziale pierwszym, przedstawiamy informacje wstępne dotyczące pierścieni, ideałów oraz baz Gröbnera. W rozdziale drugim, przedstawiamy Metodę Hilberta oraz dowodzimy rozstrzygalności równoważności transduktorów rejestrowych, których algebra wyjściowa jest wariantem nieuporządkowanym wolnej algebry lasów wprowadzonej przez Bojańczyka i Walukiewicza. W rozdziale trzecim, wskazujemy model transduktora rejestrowego, który jest w stanie wyrazić MSO2 transdukcje grafów o ograniczonej szerokości drzewiastej, oraz dowodzimy rozstrzygalności (bardzo) ograniczonej wersji jego problemu równoważności. W rozdziale czwartym, badamy trzeci ze sposobów rozszerzania Metody Hilberta, znajdując spore ograniczenia tego podejścia, a także otrzymując dwa pozytywne wyniki z jego użyciem, dotyczące transduktorów rejestrowych o wyjściu w monoidzie wolnym rozszerzonym o operację podstawienia. W rozdziale piątym, proponujemy schemat dowodzenia rozstrzygalności równowżności dla transduktorów rejestrowych, których algebra wyjściowa jest skończenie prezentowanym monoidem, oraz otrzymujemy kryterium na równaniową Noetherowskość monoidu (zwaną również własnością zwartości).

The main goal of this thesis is to apply the Hilbert Method in order to find decision procedures for the equivalence problem for various classes of transformations of combinatorial objects, like words, trees, or graphs. The Hilbert Method, roughly speaking, amounts to finding a register transducer model that captures the desired class of transformations, and encoding combinatorial objects used by this model into integers, in a way that the basic combi natorial operations (like, for example, word concatenation) can be simulated with the use of algebraic operations of addition and multiplication. While proving our main results, we extend the Hilbert Method by prov ing the following lemmas: (1) the combinatorial objects may be encoded into any computable reduced ring, (2) if the combinatorial objects are encoded into a field (note that any field is a reduced ring), then also the division operation can be used to simulate the combinatorial operations, (3) if the combinatorial objects are encoded into a ring of polynomials (note that it can be embedded into a field of rational functions), then also the substitution operation can be used, with restrictions, to simulate the combinatorial operations. In Chapter 1 we give preliminaries about rings, polynomial ideals, and Gröbner bases. In Chapter 2 we give a self-contained presentation of the Hilbert Method, and prove decidability of equivalence of register transducers with output in an unordered variant of the free forest algebra introduced by Bojańczyk and Walukiewicz. In Chapter 3 we obtain a register transducer model that captures MSO2 transductions of graphs of bounded treewidth, and prove decidability of a (very) restricted variant of their equivalence problem. In Chapter 4 we investigate the third of our ways of extending the Hilbert Method, finding a strong limitation of this approach, and obtaining two positive results about register transducers with output in a free monoid enriched with the substitution operation. In Chapter 5 we propose a proof scheme for showing decidability of equiv alence of register transducers with output in a given finitely presented monoid, and obtain a criterion for equational Noetherianity of a monoid (which is also called compactness property).