Spelling suggestions: "subject:"automorphisms"" "subject:"homomorphisms""
41 |
Abstract Numeration Systems: Recognizability, Decidability, Multidimensional S-Automatic Words, and Real NumbersCharlier, Emilie 07 December 2009 (has links)
In this doctoral dissertation, we studied and solved several questions regarding positional and abstract numeration systems. Each particular problem is the focus of a chapter. The first problem concerns the study of the preservation of recognizability under multiplication by a constant in abstract numeration systems built on polynomial regular languages. We obtained several results generalizing those from P. Lecomte and M. Rigo. The second problem we considered is a decidability problem, which was already studied, most notably, by J. Honkala and A. Muchnik. For our part, we studied this problem for two new cases: the linear positional numeration systems and the abstract numeration systems. Next, we focused on the extension to the multidimensional setting of a result of A. Maes and M.~Rigo regarding S-automatic infinite words. We obtained a characterization of multidimensional S-automatic words in terms of multidimensional (non-necessarily uniform) morphisms. This result can be viewed as the analogous of O. Salon's extension of a theorem of A. Cobham. Finally, generalizing results of P. Lecomte and M. Rigo, we proposed a formalism to represent real numbers in the general framework of abstract numeration systems built on languages that are not necessarily regular. This formalism encompasses in particular the rational base numeration systems, which have been recently introduced by S. Akiyama, Ch. Frougny, and J. Sakarovitch. Finally, we ended with a list of open questions in the continuation of this work./Dans cette dissertation, nous étudions et résolvons plusieurs questions autour des systèmes de numération abstraits. Chaque problème étudié fait l'objet d'un chapitre. Le premier concerne l'étude de la conservation de la reconnaissabilité par la multiplication par une constante dans des systèmes de numération abstraits construits sur des langages réguliers polynomiaux. Nous avons obtenus plusieurs résultats intéressants généralisant ceux de P. Lecomte et M. Rigo. Le deuxième problème auquel je me suis intéressée est un problème de décidabilité déjà étudié notamment par J. Honkala et A. Muchnik et ici décliné en deux nouvelles versions : les systèmes de numération de position linéaires et les systèmes de numération abstraits. Ensuite, nous nous penchons sur l'extension au cas multidimensionnel d'un résultat d'A. Maes et de M. Rigo à propos des mots infinis S-automatiques. Nous avons obtenu une caractérisation des mots S-automatiques multidimensionnels en termes de morphismes multidimensionnels (non nécessairement uniformes). Ce résultat peut être vu comme un analogue de l'extension obtenue par O. Salon d'un théorème de A. Cobham. Finalement, nous proposons un formalisme de la représentation des nombres réels dans le cadre général des systèmes de numération abstraits basés sur des langages qui ne sont pas nécessairement réguliers. Ce formalisme englobe notamment le cas des numérations en bases rationnelles introduits récemment par S. Akiyama, Ch. Frougny et J. Sakarovitch. Nous terminons par une liste de questions ouvertes dans la continuité de ce travail.
|
42 |
Kondenzacioni poredak, kondenzaciona ekvivalencija i reverzibilnost relacijskih struktura / Condensational order, condensational equivalenceand reversibility of relational structuresMorača Nenad 09 July 2018 (has links)
<p>Ako je<em> L </em>relacijski jezik, kondenzacioni pretporedak na skupu<em> Int</em><sub>L</sub> <em>(X)</em> svih <em>L-</em>interpretacija nad domenom <em>X,</em> dat je sa: ρ≼<sub>c</sub> <em>σ</em> ako postoji bijektivni homomorfizam (kondenzacija)<em> f:〈X,ρ</em>〉→<em>〈X,σ〉.</em> Odgovarajući antisimetrični količnik <em>〈Int<sub> L</sub></em> (X)/~<sub>c</sub>,≤<sub>c</sub>〉 ~naziva se kondenzacioni poredak. Za proizvoljnu<em> L-</em>interpretaciju ρ, klasa [ρ]~<sub>c</sub> je konveksno zatvorenje klase [ρ]_≅ u Booleovoj mreži 〈<em>IntL (X</em>),⊆〉. Za <em>L</em>-interpretaciju ρ reći ćemo da je jako reverzibilna (redom, reverzibilna, slabo reverzibilna) akko je klasa [ρ]_≅ (ili, ekvivalentno, klasa [ρ]~<sub>c </sub>)) singlton (redom, antilanac, konveksan skup) u Booleovoj mreži 〈<em>IntL (X)</em>,⊆〉. U cilju ispitivanja poseta 〈<em>Int(<sub>Lb</sub></em><sub> </sub>) (X)/~c,≤c〉, za ρ∈<em>Irrefl<sub>X</sub></em> uveden je skup D<sub>ρ</sub>:={[ρ∪Δ<sub>A</sub> ](~<sub>c</sub> ):<em>A⊆X</em>} i pokazano je kako je poduređenje 〈D<sub>ρ</sub>,≤<sub>c</sub> 〉 izomorfno određenom količniku partitivnog skupa<em> P(X)</em>. Fenomen reverzibilnosti relacijskih struktura igra istaknutu ulogu u istraživanju tog poduređenja.</p><p>U slučaju prebrojivog jezika <span id="cke_bm_1038S" style="display: none;"> </span><em>L</em><span id="cke_bm_1038E" style="display: none;"> </span> i prebrojivog domena <em>X</em>, pokazano je da su ~<sub>c</sub> i [ρ]~<sub>c </sub>analitički skupovi u poljskim prostorima, redom, <em>Int<sub>L </sub>(ω)×Int<sub>L </sub>(ω) i Int<sub>L</sub> (ω)</em>, i pomoću toga, pokazano ja da su, u slučaju prebrojivog jezika i domena, klase [ρ]≅ i [ρ]~<sub>c</sub> iste veličine, i da je to neki kardinal iz {1,ω,c}. Dalje je istražena hijerarhija između kondenzacione ekvivalencije, elementarne ekvivalencije, ekvimorfizma (bi-utopivosti) i drugih sličnosti <em>L-</em>struktura određenih nekim sličnostima njihovih monoida samoutapanja.</p><p>Naposletku, temeljno je istražen fenomen reverzibilnosti <em>L</em>-struktura. Data je karakterizacija jako reverzibilnih<em> L</em>-intepretacija kao onih čije su komponentne relacije definabilne formulama praznog jezika<em> L</em><sub>∅</sub>, bez kvantifikatora i parametara. Pokazano je kako su slabo reverzibilne interpretacije upravo one koje imaju svojstvo Cantor-Schrӧder-Bernstein (kraće, svojstvo CSB) za kondenzacije.</p><p>Poseban naglasak stavljen je na detektovanje relevantnih klasa reverzibilnih struktura. Pri tome, prvo su proučene strukture koje su ekstremni elementi L<sub>∞ω</sub>-definabilnih klasa interpretacija, pri određenim sintaktičkim ograničenjima, a zatim su istražene nepovezane<em> L</em><sub>b</sub>-strukture, gde je dato nekoliko karakterizacija njihove reverzibilnosti.</p> / <p>If <em>L</em> is a relational language, the condensational preorder on the set <em>Int<sub>L</sub> (X)</em> of all <em>L-</em>interpretations over the domain<em> X</em>, is given with: ρ≼_c σ iff there exists a bijective homomorphism (condensation) <em>f:〈X,ρ〉→〈X,σ〉. </em>The corresponding antisymmetric quotient 〈<em>Int<sub>L</sub> (X)/</em>~<sub><em>c</em></sub>,≤_<sub>c</sub>〉 will be called the condensational order. For any <em>L</em>-interpretation ρ, the class<em> [ρ]~<sub>c</sub> )</em> is the convex closure of the class [<em>ρ</em>]≅ in the Boolean lattice 〈<em>IntL (X</em>),⊆〉. An <em>L</em>-interpretation ρ is said to be strongly reversible (respectively, reversible, weakly reversible) iff the class <em>[ρ]</em>≅ (or, equivalently, the class<em> [ρ]~c )</em>) is a singleton (respectively, an antichain, a convex set) in the poset 〈 <em>IntL</em> <em>(X)</em>,⊆〉. In order to investigate the poset 〈<em>Int<sub>(Lb</sub> ) (X)/~c,≤_c</em>〉, for ρ∈<em> IrreflX</em> the following set is defined <em>D<sub>ρ</sub></em>:={[ρ∪Δ<sub>A</sub> ]_~c :A⊆X}. It is shown that the suborder 〈<em>D<sub>ρ</sub>,</em>≤<sub>c</sub> 〉 is isomorphic to a certain quotient of the power set <em>P(X)</em>. The phenomenon of reversibility plays prominent role in the investigation of that suborder.<br />In the case of a countable language<em> L</em> and a countable domain <em>X</em>, it is shown that ~c and [<em>ρ]_<sub>~c </sub></em>are analytic sets in the Polish spaces, respectively,<em> IntL (ω)× IntL (ω)</em> and <em>Int<sub>L</sub> (ω)</em>, and, using those results, in the case of a countable language and domain it is shown that the classes <em>[ρ]_</em>≅ and <em>[ρ]~<sub>c </sub></em>are of the same size, and that it is a cardinals from <sub>{1,ω,c}. N</sub>ext, the hierarchy between condensational equivalence, elementary equivalence, equimorphism (bi- embedability) and other similarities of <em>L</em>-structures, determined by some similarities of their self-embedding monoids, is investigated.<br />In the last part, the phenomenon of reversibility of<em> L</em>-structures is investigated. Strongly reversible <em>L</em>-intepretations are characterized as those whose component relations are definable by the formulae of the empty language<em> L<sub>∅</sub>, </em>without quantifiers and parameters. It is shown that weakly reversible interpretations are exactly those having the property Cantor-Schrӧder-Bernstein (shorter, the property CSB) for condensations.<br />Particular emphasis is put on detecting relevant classes of reversible structures. First, the structures that are extreme elements of<em> L</em><sub>∞ω</sub>-definable classes of interpretations, under certain syntactical restrictions, are investigated. Following that, disconnected Lb-structures are investigated, where several equivalents of their reversibility are proven.</p>
|
Page generated in 0.0306 seconds