To the field of cryptography, quantum mechanics is a game changer. The exploitation of quantum mechanical properties through the manipulation of quantum information, the information encoded in the state of quantum systems, would allow many protocols in use today to be broken as well as lead to the expansion of cryptography to new protocols. In this thesis, quantum encryption, i.e. encryption schemes for quantum data, is defined, along with several definitions of security, broadly divisible into semantic security and ciphertext indistinguishability, which are proven equivalent, in analogy to the foundational result by Goldwasser and Micali. Private- and public-key quantum encryption schemes are also constructed from quantum-secure cryptographic primitives, and their security is proven. Most of the results are in the joint paper Computational Security of Quantum Encryption, to appear in the 9th International Conference on Information Theoretic Security (ICITS2016).

[EN] Nowadays, manufacturing systems meet different new global challenges and the existence of a collaborative manufacturing environment is essential to face with. Distributed manufacturing and assembly systems are two manufacturing systems which allow industries to deal with some of these challenges. This thesis studies a production problem in which both distributed manufacturing and assembly systems are considered. Although distributed manufacturing systems and assembly systems are well-known problems and have been extensively studied in the literature, to the best of our knowledge, considering these two systems together as in this thesis is the first effort in the literature. Due to the importance of scheduling optimization on production performance, some different ways to optimize the scheduling of the considered problem are discussed in this thesis. The studied scheduling setting consists of two stages: A production and an assembly stage. Various production centers make the first stage. Each of these centers consists of several machines which are dedicated to manufacture jobs. A single assembly machine is considered for the second stage. The produced jobs are assembled on the assembly machine to form final products through a defined assembly program. In this thesis, two different problems regarding two different production configurations for the production centers of the first stage are considered. The first configuration is a flowshop that results in what we refer to as the Distributed Assembly Permutation Flowshop Scheduling Problem (DAPFSP). The second problem is referred to as the Distributed Parallel Machine and Assembly Scheduling Problem (DPMASP), where unrelated parallel machines configure the production centers. Makespan minimization of the product on the assembly machine located in the assembly stage is considered as the objective function for all considered problems. In this thesis some extensions are considered for the studied problems so as to bring them as close as possible to the reality of production shops. In the DAPFSP, sequence dependent setup times are added for machines in both production and assembly stages. Similarly, in the DPMASP, due to technological constraints, some defined jobs can be processed only in certain factories. Mathematical models are presented as an exact solution for some of the presented problems and two state-of-art solvers, CPLEX and GUROBI are used to solve them. Since these solvers are not able to solve large sized problems, we design and develop heuristic methods to solve the problems. In addition to heuristics, some metaheuristics are also designed and proposed to improve the solutions obtained by heuristics. Finally, for each proposed problem, the performance of the proposed solution methods is compared through extensive computational and comprehensive ANOVA statistical analysis. / [ES] Los sistemas de producción se enfrentan a retos globales en los que el concepto de fabricación colaborativa es crucial para poder tener éxito en el entorno cambiante y complejo en el que nos encontramos. Una característica de los sistemas productivos que puede ayudar a lograr este objetivo consiste en disponer de una red de fabricación distribuida en la que los productos se fabriquen en localizaciones diferentes y se vayan ensamblando para obtener el producto final. En estos casos, disponer de modelos y herramientas para mejorar el rendimiento de sistemas de producción distribuidos con ensamblajes es una manera de asegurar la eficiencia de los mismos. En esta tesis doctoral se estudian los sistemas de fabricación distribuidos con operaciones de ensamblaje. Los sistemas distribuidos y los sistemas con operaciones de ensamblaje han sido estudiados por separado en la literatura. De hecho, no se han encontrado estudios de sistemas con ambas características consideradas de forma conjunta. Dada la complejidad de considerar conjuntamente ambos tipos de sistemas a la hora de realizar la programación de la producción en los mismos, se ha abordado su estudio considerando un modelo bietápico en la que en la primera etapa se consideran las operaciones de producción y en la segunda se plantean las operaciones de ensamblaje. Dependiendo de la configuración de la primera etapa se han estudiado dos variantes. En la primera variante se asume que la etapa de producción está compuesta por sendos sistemas tipo flowshop en los que se fabrican los componentes que se ensamblan en la segunda etapa (Distributed Assembly Permutation Flowshop Scheduling Problem o DAPFSP). En la segunda variante se considera un sistema de máquinas en paralelo no relacionadas (Distributed Parallel Machine and Assembly Scheduling Problem o DPMASP). En ambas variantes se optimiza la fecha de finalización del último trabajo secuenciado (Cmax) y se contempla la posibilidad que existan tiempos de cambio (setup) dependientes de la secuencia de trabajos fabricada. También, en el caso DPMASP se estudia la posibilidad de prohibir o no el uso de determinadas máquinas de la etapa de producción. Se han desarrollado modelos matemáticos para resolver algunas de las variantes anteriores. Estos modelos se han resuelto mediante los programas CPLEX y GUROBI en aquellos casos que ha sido posible. Para las instancias en los que el modelo matemático no ofrecía una solución al problema se han desarrollado heurísticas y metaheurísticas para ello. Todos los procedimientos anteriores han sido estudiados para determinar el rendimiento de los diferentes algoritmos planteados. Para ello se ha realizado un exhaustivo estudio computacional en el que se han aplicado técnicas ANOVA. Los resultados obtenidos en la tesis permiten avanzar en la comprensión del comportamiento de los sistemas productivos distribuidos con ensamblajes, definiendo algoritmos que permiten obtener buenas soluciones a este tipo de problemas tan complejos que aparecen tantas veces en la realidad industrial. / [CAT] Els sistemes de producció s'enfronten a reptes globals en què el concepte de fabricació col.laborativa és crucial per a poder tindre èxit en l'entorn canviant i complex en què ens trobem. Una característica dels sistemes productius que pot ajudar a aconseguir este objectiu consistix a disposar d'una xarxa de fabricació distribuïda en la que els productes es fabriquen en localitzacions diferents i es vagen acoblant per a obtindre el producte final. En estos casos, disposar de models i ferramentes per a millorar el rendiment de sistemes de producció distribuïts amb acoblaments és una manera d'assegurar l'eficiència dels mateixos. En esta tesi doctoral s'estudien els sistemes de fabricació distribuïts amb operacions d'acoblament. Els sistemes distribuïts i els sistemes amb operacions d'acoblament han sigut estudiats per separat en la literatura però, en allò que es coneix, no s'han trobat estudis de sistemes amb ambdós característiques conjuntament. Donada la complexitat de considerar conjuntament ambdós tipus de sistemes a l'hora de realitzar la programació de la producció en els mateixos, s'ha abordat el seu estudi considerant un model bietàpic en la que en la primera etapa es consideren les operacions de producció i en la segona es plantegen les operacions d'acoblament. Depenent de la configuració de la primera etapa s'han estudiat dos variants. En la primera variant s'assumix que l'etapa de producció està composta per sengles sistemes tipus flowshop en els que es fabriquen els components que s'acoblen en la segona etapa (Distributed Assembly Permutation Flowshop Scheduling Problem o DAPFSP). En la segona variant es considera un sistema de màquines en paral.lel no relacionades (Distributed Parallel Machine and Assembly Scheduling Problem o DPMASP). En ambdós variants s'optimitza la data de finalització de l'últim treball seqüenciat (Cmax) i es contempla la possibilitat que existisquen temps de canvi (setup) dependents de la seqüència de treballs fabricada. També, en el cas DPMASP s'estudia la possibilitat de prohibir o no l'ús de determinades màquines de l'etapa de producció. S'han desenvolupat models matemàtics per a resoldre algunes de les variants anteriors. Estos models s'han resolt per mitjà dels programes CPLEX i GUROBI en aquells casos que ha sigut possible. Per a les instàncies en què el model matemàtic no oferia una solució al problema s'han desenrotllat heurístiques i metaheurísticas per a això. Tots els procediments anteriors han sigut estudiats per a determinar el rendiment dels diferents algoritmes plantejats. Per a això s'ha realitzat un exhaustiu estudi computacional en què s'han aplicat tècniques ANOVA. Els resultats obtinguts en la tesi permeten avançar en la comprensió del comportament dels sistemes productius distribuïts amb acoblaments, definint algoritmes que permeten obtindre bones solucions a este tipus de problemes tan complexos que apareixen tantes vegades en la realitat industrial. / Hatami, S. (2016). The Distributed and Assembly Scheduling Problem [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/64072 / TESIS

The present Ph.D. thesis, primarily conceived to support and reinforce the relation between academic and industrial worlds, was developed in collaboration with Shell Global Solutions (Amsterdam, The Netherlands) in the endeavour of applying and possibly extending well-established latent variable-based approaches (i.e. Principal Component Analysis - PCA - Partial Least Squares regression - PLS - or Partial Least Squares Discriminant Analysis - PLSDA) for complex problem solving not only in the fields of manufacturing troubleshooting and optimisation, but also in the wider environment of multivariate data analysis. To this end, novel efficient algorithmic solutions are proposed throughout all chapters to address very disparate tasks, from calibration transfer in spectroscopy to real-time modelling of streaming flows of data. The manuscript is divided into the following six parts, focused on various topics of interest: Part I - Preface, where an overview of this research work, its main aims and justification is given together with a brief introduction on PCA, PLS and PLSDA; Part II - On kernel-based extensions of PCA, PLS and PLSDA, where the potential of kernel techniques, possibly coupled to specific variants of the recently rediscovered pseudo-sample projection, formulated by the English statistician John C. Gower, is explored and their performance compared to that of more classical methodologies in four different applications scenarios: segmentation of Red-Green-Blue (RGB) images, discrimination of on-/off-specification batch runs, monitoring of batch processes and analysis of mixture designs of experiments; Part III - On the selection of the number of factors in PCA by permutation testing, where an extensive guideline on how to accomplish the selection of PCA components by permutation testing is provided through the comprehensive illustration of an original algorithmic procedure implemented for such a purpose; Part IV - On modelling common and distinctive sources of variability in multi-set data analysis, where several practical aspects of two-block common and distinctive component analysis (carried out by methods like Simultaneous Component Analysis - SCA - DIStinctive and COmmon Simultaneous Component Analysis - DISCO-SCA - Adapted Generalised Singular Value Decomposition - Adapted GSVD - ECO-POWER, Canonical Correlation Analysis - CCA - and 2-block Orthogonal Projections to Latent Structures - O2PLS) are discussed, a new computational strategy for determining the number of common factors underlying two data matrices sharing the same row- or column-dimension is described, and two innovative approaches for calibration transfer between near-infrared spectrometers are presented; Part V - On the on-the-fly processing and modelling of continuous high-dimensional data streams, where a novel software system for rational handling of multi-channel measurements recorded in real time, the On-The-Fly Processing (OTFP) tool, is designed; Part VI - Epilogue, where final conclusions are drawn, future perspectives are delineated, and annexes are included. / La presente tesis doctoral, concebida principalmente para apoyar y reforzar la relación entre la academia y la industria, se desarrolló en colaboración con Shell Global Solutions (Amsterdam, Países Bajos) en el esfuerzo de aplicar y posiblemente extender los enfoques ya consolidados basados en variables latentes (es decir, Análisis de Componentes Principales - PCA - Regresión en Mínimos Cuadrados Parciales - PLS - o PLS discriminante - PLSDA) para la resolución de problemas complejos no sólo en los campos de mejora y optimización de procesos, sino también en el entorno más amplio del análisis de datos multivariados. Con este fin, en todos los capítulos proponemos nuevas soluciones algorítmicas eficientes para abordar tareas dispares, desde la transferencia de calibración en espectroscopia hasta el modelado en tiempo real de flujos de datos. El manuscrito se divide en las seis partes siguientes, centradas en diversos temas de interés: Parte I - Prefacio, donde presentamos un resumen de este trabajo de investigación, damos sus principales objetivos y justificaciones junto con una breve introducción sobre PCA, PLS y PLSDA; Parte II - Sobre las extensiones basadas en kernels de PCA, PLS y PLSDA, donde presentamos el potencial de las técnicas de kernel, eventualmente acopladas a variantes específicas de la recién redescubierta proyección de pseudo-muestras, formulada por el estadista inglés John C. Gower, y comparamos su rendimiento respecto a metodologías más clásicas en cuatro aplicaciones a escenarios diferentes: segmentación de imágenes Rojo-Verde-Azul (RGB), discriminación y monitorización de procesos por lotes y análisis de diseños de experimentos de mezclas; Parte III - Sobre la selección del número de factores en el PCA por pruebas de permutación, donde aportamos una guía extensa sobre cómo conseguir la selección de componentes de PCA mediante pruebas de permutación y una ilustración completa de un procedimiento algorítmico original implementado para tal fin; Parte IV - Sobre la modelización de fuentes de variabilidad común y distintiva en el análisis de datos multi-conjunto, donde discutimos varios aspectos prácticos del análisis de componentes comunes y distintivos de dos bloques de datos (realizado por métodos como el Análisis Simultáneo de Componentes - SCA - Análisis Simultáneo de Componentes Distintivos y Comunes - DISCO-SCA - Descomposición Adaptada Generalizada de Valores Singulares - Adapted GSVD - ECO-POWER, Análisis de Correlaciones Canónicas - CCA - y Proyecciones Ortogonales de 2 conjuntos a Estructuras Latentes - O2PLS). Presentamos a su vez una nueva estrategia computacional para determinar el número de factores comunes subyacentes a dos matrices de datos que comparten la misma dimensión de fila o columna y dos planteamientos novedosos para la transferencia de calibración entre espectrómetros de infrarrojo cercano; Parte V - Sobre el procesamiento y la modelización en tiempo real de flujos de datos de alta dimensión, donde diseñamos la herramienta de Procesamiento en Tiempo Real (OTFP), un nuevo sistema de manejo racional de mediciones multi-canal registradas en tiempo real; Parte VI - Epílogo, donde presentamos las conclusiones finales, delimitamos las perspectivas futuras, e incluimos los anexos. / La present tesi doctoral, concebuda principalment per a recolzar i reforçar la relació entre l'acadèmia i la indústria, es va desenvolupar en col·laboració amb Shell Global Solutions (Amsterdam, Països Baixos) amb l'esforç d'aplicar i possiblement estendre els enfocaments ja consolidats basats en variables latents (és a dir, Anàlisi de Components Principals - PCA - Regressió en Mínims Quadrats Parcials - PLS - o PLS discriminant - PLSDA) per a la resolució de problemes complexos no solament en els camps de la millora i optimització de processos, sinó també en l'entorn més ampli de l'anàlisi de dades multivariades. A aquest efecte, en tots els capítols proposem noves solucions algorítmiques eficients per a abordar tasques dispars, des de la transferència de calibratge en espectroscopia fins al modelatge en temps real de fluxos de dades. El manuscrit es divideix en les sis parts següents, centrades en diversos temes d'interès: Part I - Prefaci, on presentem un resum d'aquest treball de recerca, es donen els seus principals objectius i justificacions juntament amb una breu introducció sobre PCA, PLS i PLSDA; Part II - Sobre les extensions basades en kernels de PCA, PLS i PLSDA, on presentem el potencial de les tècniques de kernel, eventualment acoblades a variants específiques de la recentment redescoberta projecció de pseudo-mostres, formulada per l'estadista anglés John C. Gower, i comparem el seu rendiment respecte a metodologies més clàssiques en quatre aplicacions a escenaris diferents: segmentació d'imatges Roig-Verd-Blau (RGB), discriminació i monitorització de processos per lots i anàlisi de dissenys d'experiments de mescles; Part III - Sobre la selecció del nombre de factors en el PCA per proves de permutació, on aportem una guia extensa sobre com aconseguir la selecció de components de PCA a través de proves de permutació i una il·lustració completa d'un procediment algorítmic original implementat per a la finalitat esmentada; Part IV - Sobre la modelització de fonts de variabilitat comuna i distintiva en l'anàlisi de dades multi-conjunt, on discutim diversos aspectes pràctics de l'anàlisis de components comuns i distintius de dos blocs de dades (realitzat per mètodes com l'Anàlisi Simultània de Components - SCA - Anàlisi Simultània de Components Distintius i Comuns - DISCO-SCA - Descomposició Adaptada Generalitzada en Valors Singulars - Adapted GSVD - ECO-POWER, Anàlisi de Correlacions Canòniques - CCA - i Projeccions Ortogonals de 2 blocs a Estructures Latents - O2PLS). Presentem al mateix temps una nova estratègia computacional per a determinar el nombre de factors comuns subjacents a dues matrius de dades que comparteixen la mateixa dimensió de fila o columna, i dos plantejaments nous per a la transferència de calibratge entre espectròmetres d'infraroig proper; Part V - Sobre el processament i la modelització en temps real de fluxos de dades d'alta dimensió, on dissenyem l'eina de Processament en Temps Real (OTFP), un nou sistema de tractament racional de mesures multi-canal registrades en temps real; Part VI - Epíleg, on presentem les conclusions finals, delimitem les perspectives futures, i incloem annexos. / Vitale, R. (2017). Novel chemometric proposals for advanced multivariate data analysis, processing and interpretation [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/90442 / TESIS

The master's thesis provides a comprehensive overview of resampling methods for testing the correctness topology of the phylogenetic trees which estimate the process of phylogeny on the bases of biological sequences similarity. We focused on the possibility of errors creation in this estimate and the possibility of their removal and detection. These methods were implemented in Matlab for Bootstrapping, jackknifing, OTU jackknifing and PTP test (Permutation tail probability). The work aims to test their applicability to various biological sequences and also to assess the impact of the choice of input analysis parameters on the results of these statistical tests.

Få studier om ljudsymbolik, d.v.s. kopplingen mellan ords form och betydelse, har baserats på statistisk analys. I denna studie använder vi random forests med måttet permutation variable importance för att utforska vilka fonem (språkljud) som är prevalenta i engelska ord som beskriver hårdhet eller mjukhet. Denna icke-parametriska maskininlärningsmetod har funnits vara användbar för identifiering av ett fåtal inflytelserika förklaringsvariabler i situationer där n < p eller interkorrelationer förekommer. Vårt material och val av metod grundar sig på en tidigare studie, som fann att r-ljud hade starkt samband med betydelsen ‘strävhet’, men som inte kontrollerade för betydelsen ‘hårdhet’ trots att dessa korrelerar med varandra. Vi kontrollerar för dimensionen strävhet-lenhet genom att utföra random forest-analysen på två delmängder: ord som används för att beskriva hårdhet eller mjukhet (n = 81), samt den delmängd av dessa ord som inte beskriver strävhet eller lenhet (n  = 40). Samtliga regressorer är binära variabler, som anger förekomsten eller avsaknaden av varsitt fonem; vi utförde separata analyser på respektive datamängd för att se vilka fonem som hade störst effekt, då man betraktade specifika stavelsekomponenter. Vi fann att r-ljuden hade starkt samband med betydelsen ‘hårdhet’ både före och efter kontrollen för ‘strävhet’. Vi fann även att ljudet med symbolen i (t.ex. sista vokalen i fluffy) hade starkt samband med betydelsen ‘mjukhet’ före och efter kontroll, men vi misstänker att detta egentligen reflekterar sambandet mellan ‘mjukhet’ och exkluderade bakgrundsvariabler. / Few studies about sound symbolism, i.e. the association between the shape and meaning of words, have been based on statistical analysis. In this study, we use random forests and the permutation variable importance measure to explore which phonemes (language sounds) are prevalent in English descriptors of hardness or softness. This non-parametric machine learning method has been found useful for identification of a few influential predictors in situations where n < p or intercorrelations are present. Our materials and choice of method are based on an earlier study, in which a strong association was found between r-sounds and ‘roughness’, but which did not control for the meaning ‘hardness’ despite the correlation between them. We control for the dimension ‘roughness-smoothness’ by performing the random forest-analysis on two subsets of data: descriptors of hardness or softness (n = 81), and descriptors of hardness or softness which are not used to describe roughness or smoothness (n = 40). All regressors are binary variables indicating the presence or absence of a phoneme. Separate analyses were conducted on each subset to see which phonemes had the largest effect when specific syllable compontents were considered. We found that r-sounds had a strong association with ‘hardness’ both before and after controlling for ‘roughness’. We also found that the sound here symbolized by i (e.g. the last vowel of fluffy) had a strong association with ‘softness’ before and after control, but we suspect that this might instead reflect an association between ‘softness’ and excluded variables.

No description available.

No description available.

Cette thèse porte sur trois problèmes en combinatoire algébrique effective et algorithmique.Les premières parties proposent une approche alternative aux bases de Gröbner pour le calcul des invariants secondaires des groupes de permutations, par évaluation en des points choisis de manière appropriée. Cette méthode permet de tirer parti des symétries du problème pour confiner les calculs dans un quotient de petite dimension, et ainsi d'obtenir un meilleur contrôle de la complexité algorithmique, en particulier pour les groupes de grande taille. L'étude théorique est illustrée par de nombreux bancs d'essais utilisant une implantation fine des algorithmes. Un prérequis important est la génération efficace de vecteurs d'entiers modulo l'action d'un groupe de permutation, dont l'algorithmique fait l'objet d'une partie préliminaire.La quatrième partie cherche à déterminer, pour un certain quotient naturel d'une algèbre de Hecke affine, quelles spécialisations des paramètres aux racines de l'unité donne un comportement non générique.Finalement, la dernière partie présente une conjecture sur la structure d'une certaine $q$-déformation des polynômes harmoniques diagonaux en plusieurs paquets de variables pour la famille infinie de groupes de réflexions complexes.Tous ces chapitres s'appuient fortement sur l'exploration informatique, et font l'objet de multiples contributions au logiciel Sage. / This thesis concerns algorithmic approaches to three challenging problems in computational algebraic combinatorics.The firsts parts propose a Gröbner basis free approach for calculating the secondary invariants of a finite permutation group, proceeding by using evaluation at appropriately chosen points. This approach allows for exploiting the symmetries to confine the calculations into a smaller quotient space, which gives a tighter control on the algorithmic complexity, especially for large groups. The theoretical study is illustrated by extensive benchmarks using a fine implementation of algorithms. An important prerequisite is the generation of integer vectors modulo the action of a permutation group, whose algorithmic constitute a preliminary part of the thesis.The fourth part of this thesis is determining for a certain interesting quotient of an affine Hecke algebra exactly which root-of-unity specialization of its parameter lead to non-generic behavior.Finally, the last part presents a conjecture on the structure of certain q-deformed diagonal harmonics in many sets of variables for the infinite family of complex reflection groups.All chapters proceed widely by computer exploration, and most of established algorithms constitute contributions of the software Sage.

Diese Arbeit leistet Beiträge im Bereich der deskriptiven Komplexitätstheorie. Zunächst beschäftigen wir uns mit der ungelösten Frage, ob es eine Logik gibt, welche die Klasse der Polynomialzeit-Eigenschaften (PTIME) charakterisiert. Wir betrachten Graphklassen, die unter induzierten Teilgraphen abgeschlossen sind. Auf solchen Graphklassen lässt sich die 1976 von Gallai eingeführte modulare Zerlegung anwenden. Graphen, die durch modulare Zerlegung nicht zerlegbar sind, heißen prim. Wir stellen ein neues Werkzeug vor: das Modulare Zerlegungstheorem. Es reduziert (definierbare) Kanonisierung einer Graphklasse C auf (definierbare) Kanonisierung der Klasse aller primen Graphen aus C, die mit binären Relationen auf einer linear geordneten Menge gefärbt sind. Mit Hilfe des Modularen Zerlegungstheorems zeigen wir, dass Fixpunktlogik mit Zählen (FP+C) PTIME auf der Klasse aller Permutationsgraphen und auf der Klasse aller chordalen Komparabilitätsgraphen charakterisiert. Wir beweisen zudem, dass modulare Zerlegungsbäume in Symmetrisch-Transitive-Hüllen-Logik mit Zählen (STC+C) definierbar und damit in logarithmischem Platz berechenbar sind. Weiterhin definieren wir eine neue Logik für die Komplexitätsklasse Logarithmischer Platz (LOGSPACE). Wir erweitern die Logik erster Stufe mit Zählen um einen Operator, der eine in logarithmischem Platz berechenbare Form der Rekursion erlaubt. Die resultierende Logik LREC ist ausdrucksstärker als die Deterministisch-Transitive-Hüllen-Logik mit Zählen (DTC+C) und echt in FP+C enthalten. Wir zeigen, dass LREC LOGSPACE auf gerichteten Bäumen charakterisiert. Zudem betrachten wir eine Erweiterung LREC= von LREC, die sich gegenüber LREC durch bessere Abschlusseigenschaften auszeichnet und im Gegensatz zu LREC ausdrucksstärker als die Symmetrisch-Transitive-Hüllen-Logik (STC) ist. Wir beweisen, dass LREC= LOGSPACE sowohl auf der Klasse der Intervallgraphen als auch auf der Klasse der chordalen klauenfreien Graphen charakterisiert. / This theses is making contributions to the field of descriptive complexity theory. First, we look at the main open problem in this area: the question of whether there exists a logic that captures polynomial time (PTIME). We consider classes of graphs that are closed under taking induced subgraphs. For such graph classes, an effective graph decomposition, called modular decomposition, was introduced by Gallai in 1976. The graphs that are non-decomposable with respect to modular decomposition are called prime. We present a tool, the Modular Decomposition Theorem, that reduces (definable) canonization of a graph class C to (definable) canonization of the class of prime graphs of C that are colored with binary relations on a linearly ordered set. By an application of the Modular Decomposition Theorem, we show that fixed-point logic with counting (FP+C) captures PTIME on the class of permutation graphs and the class of chordal comparability graphs. We also prove that the modular decomposition tree is definable in symmetric transitive closure logic with counting (STC+C), and therefore, computable in logarithmic space. Further, we introduce a new logic for the complexity class logarithmic space (LOGSPACE). We extend first-order logic with counting by a new operator that allows it to formalize a limited form of recursion which can be evaluated in logarithmic space. We prove that the resulting logic LREC is strictly more expressive than deterministic transitive closure logic with counting (DTC+C) and that it is strictly contained in FP+C. We show that LREC captures LOGSPACE on the class of directed trees. We also study an extension LREC= of LREC that has nicer closure properties and that, unlike LREC, is more expressive than symmetric transitive closure logic (STC). We prove that LREC= captures LOGSPACE on the class of interval graphs and on the class of chordal claw-free graphs.

I sistemi di valutazione genetica nel mondo sono in rapido sviluppo. Attualmente, i programmi di selezione “tradizionale” basati su fenotipi e rapporti di parentela tra gli animali vengono integrati, e nel futuro potrebbero essere sostituiti, dalle informazioni molecolari. In questo periodo di transizione, questa tesi riguarda ricerche su entrambi i tipi di valutazioni: dall’accertamento sull’accuratezza degli indici genetici internazionali (tradizionali), allo studio di metodi statistici utilizzati per integrare informazioni genomiche nella selezione (selezione genomica). Tre capitoli valutano gli approcci per stimare i valori genetici dai dati genomici riducendo il numero di variabili indipendenti. In modo particolare, la correzione di Bonferroni e il test di permutazioni con regressione a marcatori singoli (Capitolo III), analisi delle componenti principali con BLUP (Capitolo IV) e indice Fst tra razze con BayesA (Capitolo VI). Inoltre, il Capitolo V analizza l’accuratezza dei valori genomici con BLUP, BayesA e Bayesian LASSO includendo tutte le variabili disponibili. I risultati di questa tesi indicano che il progresso genetico atteso dall’analisi dei dati simulati può effettivamente essere ottenuto, anche se ulteriori ricerche sono necessarie per ottimizzare l’utilizzo delle informazioni molecolari in modo da ottimizzare i risultati per tutti i caratteri sotto selezione. / Genetic evaluation systems are in rapid development worldwide. In most countries, “traditional” breeding programs based on phenotypes and relationships between animals are currently being integrated and in the future might be replaced by the introduction of molecular information. This thesis stands in this transition period, therefore it covers research on both types of genetic evaluations: from the assessment of the accuracy of (traditional) international genetic evaluations to the study of statistical methods used to integrate genomic information into breeding (genomic selection). Three chapters investigate and evaluate approaches for the estimation of genetic values from genomic data reducing the number of independent variables. In particular, Bonferroni correction and Permutation test combined with single marker regression (Chapter III), principal component analysis combined with BLUP (Chapter IV) and Fst across breeds combined with BayesA (Chapter VI). In addition, Chapter V analyzes the accuracy of direct genomic values with BLUP, BayesA and Bayesian LASSO including all available variables. The results of this thesis indicate that the genetic gains expected from the analysis of simulated data can be obtained on real data. Still, further research is needed to optimize the use of genome-wide information and obtain the best possible estimates for all traits under selection.