Strong Connectivity in Directed Hypergraphs and its Application to the Atomic Decomposition of Ontologies

Los hipergrafos dirigidos se han empleado en problemas relacionados con lógica proposicional, bases de datos relacionales, linguística computacional y aprendizaje automático. Los hipergrafos dirigidos han sido también utilizados como alternativa a los grafos (bipartitos) dirigidos para facilitar el estudio de las interacciones entre componentes de sistemas complejos que no pueden ser fácilmente modelados usando exclusivamente relaciones binarias. En este contexto, este tipo de representación es conocida como hiper-redes. Un hipergrafo dirigido es una generalización de un grafo dirigido especialmente adecuado para la representación de relaciones de muchos a muchos. Mientras que una arista en un grafo dirigido define una relación entre dos de sus nodos, una hiperarista en un hipergrafo dirigido define una relación entre dos conjuntos de sus nodos. La conexión fuerte es una relación de equivalencia que divide el conjunto de nodos de un hipergrafo dirigido en particiones y cada partición define una clase de equivalencia conocida como componente fuertemente conexo. El estudio de los componentes fuertemente conexos de un hipergrafo dirigido puede ayudar a conseguir una mejor comprensión de la estructura de este tipo de hipergrafos cuando su tamaño es considerable. En el caso de grafo dirigidos, existen algoritmos muy eficientes para el cálculo de los componentes fuertemente conexos en grafos de gran tamaño. Gracias a estos algoritmos, se ha podido averiguar que la estructura de la WWW tiene forma de “pajarita”, donde más del 70% del los nodos están distribuidos en tres grandes conjuntos y uno de ellos es un componente fuertemente conexo. Este tipo de estructura ha sido también observada en redes complejas en otras áreas como la biología. Estudios de naturaleza similar no han podido ser realizados en hipergrafos dirigidos porque no existe algoritmos capaces de calcular los componentes fuertemente conexos de este tipo de hipergrafos. En esta tesis doctoral, hemos investigado como calcular los componentes fuertemente conexos de un hipergrafo dirigido. En concreto, hemos desarrollado dos algoritmos para este problema y hemos determinado que son correctos y cuál es su complejidad computacional. Ambos algoritmos han sido evaluados empíricamente para comparar sus tiempos de ejecución. Para la evaluación, hemos producido una selección de hipergrafos dirigidos generados de forma aleatoria inspirados en modelos muy conocidos de grafos aleatorios como Erdos-Renyi, Newman-Watts-Strogatz and Barabasi-Albert. Varias optimizaciones para ambos algoritmos han sido implementadas y analizadas en la tesis. En concreto, colapsar los componentes fuertemente conexos del grafo dirigido que se puede construir eliminando ciertas hiperaristas complejas del hipergrafo dirigido original, mejora notablemente los tiempos de ejecucion de los algoritmos para varios de los hipergrafos utilizados en la evaluación. Aparte de los ejemplos de aplicación mencionados anteriormente, los hipergrafos dirigidos han sido también empleados en el área de representación de conocimiento. En concreto, este tipo de hipergrafos se han usado para el cálculo de módulos de ontologías. Una ontología puede ser definida como un conjunto de axiomas que especifican formalmente un conjunto de símbolos y sus relaciones, mientras que un modulo puede ser entendido como un subconjunto de axiomas de la ontología que recoge todo el conocimiento que almacena la ontología sobre un conjunto especifico de símbolos y sus relaciones. En la tesis nos hemos centrado solamente en módulos que han sido calculados usando la técnica de localidad sintáctica. Debido a que las ontologías pueden ser muy grandes, el cálculo de módulos puede facilitar las tareas de re-utilización y mantenimiento de dichas ontologías. Sin embargo, analizar todos los posibles módulos de una ontología es, en general, muy costoso porque el numero de módulos crece de forma exponencial con respecto al número de símbolos y de axiomas de la ontología. Afortunadamente, los axiomas de una ontología pueden ser divididos en particiones conocidas como átomos. Cada átomo representa un conjunto máximo de axiomas que siempre aparecen juntos en un modulo. La decomposición atómica de una ontología es definida como un grafo dirigido de tal forma que cada nodo del grafo corresponde con un átomo y cada arista define una dependencia entre una pareja de átomos. En esta tesis introducimos el concepto de“axiom dependency hypergraph” que generaliza el concepto de descomposición atómica de una ontología. Un modulo en una ontología correspondería con un componente conexo en este tipo de hipergrafos y un átomo de una ontología con un componente fuertemente conexo. Hemos adaptado la implementación de nuestros algoritmos para que funcionen también con axiom dependency hypergraphs y poder de esa forma calcular los átomos de una ontología. Para demostrar la viabilidad de esta idea, hemos incorporado nuestros algoritmos en una aplicación que hemos desarrollado para la extracción de módulos y la descomposición atómica de ontologías. A la aplicación la hemos llamado HyS y hemos estudiado sus tiempos de ejecución usando una selección de ontologías muy conocidas del área biomédica, la mayoría disponibles en el portal de Internet NCBO. Los resultados de la evaluación muestran que los tiempos de ejecución de HyS son mucho mejores que las aplicaciones más rápidas conocidas. ABSTRACT Directed hypergraphs are an intuitive modelling formalism that have been used in problems related to propositional logic, relational databases, computational linguistic and machine learning. Directed hypergraphs are also presented as an alternative to directed (bipartite) graphs to facilitate the study of the interactions between components of complex systems that cannot naturally be modelled as binary relations. In this context, they are known as hyper-networks. A directed hypergraph is a generalization of a directed graph suitable for representing many-to-many relationships. While an edge in a directed graph defines a relation between two nodes of the graph, a hyperedge in a directed hypergraph defines a relation between two sets of nodes. Strong-connectivity is an equivalence relation that induces a partition of the set of nodes of a directed hypergraph into strongly-connected components. These components can be collapsed into single nodes. As result, the size of the original hypergraph can significantly be reduced if the strongly-connected components have many nodes. This approach might contribute to better understand how the nodes of a hypergraph are connected, in particular when the hypergraphs are large. In the case of directed graphs, there are efficient algorithms that can be used to compute the strongly-connected components of large graphs. For instance, it has been shown that the macroscopic structure of the World Wide Web can be represented as a “bow-tie” diagram where more than 70% of the nodes are distributed into three large sets and one of these sets is a large strongly-connected component. This particular structure has been also observed in complex networks in other fields such as, e.g., biology. Similar studies cannot be conducted in a directed hypergraph because there does not exist any algorithm for computing the strongly-connected components of the hypergraph. In this thesis, we investigate ways to compute the strongly-connected components of directed hypergraphs. We present two new algorithms and we show their correctness and computational complexity. One of these algorithms is inspired by Tarjan’s algorithm for directed graphs. The second algorithm follows a simple approach to compute the stronglyconnected components. This approach is based on the fact that two nodes of a graph that are strongly-connected can also reach the same nodes. In other words, the connected component of each node is the same. Both algorithms are empirically evaluated to compare their performances. To this end, we have produced a selection of random directed hypergraphs inspired by existent and well-known random graphs models like Erd˝os-Renyi and Newman-Watts-Strogatz. Besides the application examples that we mentioned earlier, directed hypergraphs have also been employed in the field of knowledge representation. In particular, they have been used to compute the modules of an ontology. An ontology is defined as a collection of axioms that provides a formal specification of a set of terms and their relationships; and a module is a subset of an ontology that completely captures the meaning of certain terms as defined in the ontology. In particular, we focus on the modules computed using the notion of syntactic locality. As ontologies can be very large, the computation of modules facilitates the reuse and maintenance of these ontologies. Analysing all modules of an ontology, however, is in general not feasible as the number of modules grows exponentially in the number of terms and axioms of the ontology. Nevertheless, the modules can succinctly be represented using the Atomic Decomposition of an ontology. Using this representation, an ontology can be partitioned into atoms, which are maximal sets of axioms that co-occur in every module. The Atomic Decomposition is then defined as a directed graph such that each node correspond to an atom and each edge represents a dependency relation between two atoms. In this thesis, we introduce the notion of an axiom dependency hypergraph which is a generalization of the atomic decomposition of an ontology. A module in the ontology corresponds to a connected component in the hypergraph, and the atoms of the ontology to the strongly-connected components. We apply our algorithms for directed hypergraphs to axiom dependency hypergraphs and in this manner, we compute the atoms of an ontology. To demonstrate the viability of this approach, we have implemented the algorithms in the application HyS which computes the modules of ontologies and calculate their atomic decomposition. In the thesis, we provide an experimental evaluation of HyS with a selection of large and prominent biomedical ontologies, most of which are available in the NCBO Bioportal. HyS outperforms state-of-the-art implementations in the tasks of extracting modules and computing the atomic decomposition of these ontologies.

The decomposition of peroxynitrite does not yield nitroxyl anion and singlet oxygen

In a recent article [Khan, A. U., Kovacic, D., Kolbanovsky, A., Desai, M., Frenkel, K. & Geacintov, N. E. (2000) Proc. Natl. Acad. Sci. USA 97, 2984–2989], the authors claimed that ONOO−, after protonation to ONOOH, decomposes into 1HNO and 1O2 according to a spin-conserved unimolecular mechanism. This claim was based partially on their observation that nitrosylhemoglobin is formed via the reaction of peroxynitrite with methemoglobin at neutral pH. However, thermochemical considerations show that the yields of 1O2 and 1HNO are about 23 orders of magnitude lower than those of ⋅NO2 and ⋅OH, which are formed via the homolysis of ONOOH. We also show that methemoglobin does not form with peroxynitrite any spectrally detectable product, but with contaminations of nitrite and H2O2 present in the peroxynitrite sample. Thus, there is no need to modify the present view of the mechanism of ONOOH decomposition, according to which initial homolysis into a radical pair, [ONO⋅ ⋅OH]cage, is followed by the diffusion of about 30% of the radicals out of the cage, while the rest recombines to nitric acid in the solvent cage.

Rates of decomposition of ribose and other sugars: implications for chemical evolution.

The existence of the RNA world, in which RNA acted as a catalyst as well as an informational macromolecule, assumes a large prebiotic source of ribose or the existence of pre-RNA molecules with backbones different from ribose-phosphate. The generally accepted prebiotic synthesis of ribose, the formose reaction, yields numerous sugars without any selectivity. Even if there were a selective synthesis of ribose, there is still the problem of stability. Sugars are known to be unstable in strong acid or base, but there are few data for neutral solutions. Therefore, we have measured the rate of decomposition of ribose between pH 4 and pH 8 from 40 degrees C to 120 degrees C. The ribose half-lives are very short (73 min at pH 7.0 and 100 degrees C and 44 years at pH 7.0 and 0 degrees C). The other aldopentoses and aldohexoses have half-lives within an order of magnitude of these values, as do 2-deoxyribose, ribose 5-phosphate, and ribose 2,4-bisphosphate. These results suggest that the backbone of the first genetic material could not have contained ribose or other sugars because of their instability.

Assessment and Promotion of Partner Support: A Prevention-Focused Intervention for Perinatal Depression in Primary Care

Perinatal depression significantly impacts the mother, her partner, the unborn fetus, and the infant/child after delivery. A review of the literature supports the need for preventive intervention methods as research has shown that even with successful treatment, disruptions in attachment, temperament, and cognitive development often remain. Primary care settings are ideal targets for prevention given that they can reach a number of people at low-cost without the stigma associated with seeking help in a mental health facility. This paper purposes a preventive intervention method for perinatal depression that can be implemented in primary care settings in both Western and non-Western countries. The intervention targets two of the primary risk factors for perinatal depression; partner support and relationship quality. The intervention is structured around key target periods in gestational development and during the early weeks after delivery. Suggestions for each target visit are based on prior research that has demonstrated how psychoeducation about the transition to parenthood, as well as increased communication, can positively affect partner support and relationship quality. The ultimate goal of the intervention is not only to prevent perinatal depression but also to improve the mental health and wellbeing of the entire family system.

Decomposition of human behavior using model of competencies: application to robotic control system

For many years, humans and machines have shared the same physical space. To facilitate their interaction with humans, their social integration and for more rational behavior has been sought that the robots demonstrate human-like behavior. For this it is necessary to understand how human behavior is generated, discuss what tasks are performed and how relate to themselves, for subsequent implementation in robots. In this paper, we propose a model of competencies based on human neuroregulator system for analysis and decomposition of behavior into functional modules. Using this model allow separate and locate the tasks to be implemented in a robot that displays human-like behavior. As an example, we show the application of model to the autonomous movement behavior on unfamiliar environments and its implementation in various simulated and real robots with different physical configurations and physical devices of different nature. The main result of this work has been to build a model of competencies that is being used to build robotic systems capable of displaying behaviors similar to humans and consider the specific characteristics of robots.

Study of the thermal decomposition of petrochemical sludge in a pilot plant reactor

The pyrolysis of a sludge produced in the waste water treatment plant of an oil refinery was studied in a pilot plant reactor provided with a system for condensation of semivolatile matter. The study comprises experiments at 350, 400, 470 and 530 °C in nitrogen atmosphere. Analysis of all the products obtained (gases, liquids and chars) are presented, with a thermogravimetric study of the char produced and analysis of main components of the liquid. In the temperature range studied, the composition of the gas fraction does not appreciably vary. In the liquids, the light hidrocarbon yield increases with increasing temperature, whereas the aromatic compounds diminish. The decomposition of the solid fraction has been analysed, finding a material that reacts rapidly with oxygen regardless of the conditions it is formed.

Motzkin decomposition of closed convex sets via truncation

A nonempty set F is called Motzkin decomposable when it can be expressed as the Minkowski sum of a compact convex set C with a closed convex cone D. In that case, the sets C and D are called compact and conic components of F. This paper provides new characterizations of the Motzkin decomposable sets involving truncations of F (i.e., intersections of FF with closed halfspaces), when F contains no lines, and truncations of the intersection F̂ of F with the orthogonal complement of the lineality of F, otherwise. In particular, it is shown that a nonempty closed convex set F is Motzkin decomposable if and only if there exists a hyperplane H parallel to the lineality of F such that one of the truncations of F̂ induced by H is compact whereas the other one is a union of closed halflines emanating from H. Thus, any Motzkin decomposable set F can be expressed as F=C+D, where the compact component C is a truncation of F̂. These Motzkin decompositions are said to be of type T when F contains no lines, i.e., when C is a truncation of F. The minimality of this type of decompositions is also discussed.

Model of Competencies for Decomposition of Human Behavior: Application to Control System of Robots

Humans and machines have shared the same physical space for many years. To share the same space, we want the robots to behave like human beings. This will facilitate their social integration, their interaction with humans and create an intelligent behavior. To achieve this goal, we need to understand how human behavior is generated, analyze tasks running our nerves and how they relate to them. Then and only then can we implement these mechanisms in robotic beings. In this study, we propose a model of competencies based on human neuroregulator system for analysis and decomposition of behavior into functional modules. Using this model allow separate and locate the tasks to be implemented in a robot that displays human-like behavior. As an example, we show the application of model to the autonomous movement behavior on unfamiliar environments and its implementation in various simulated and real robots with different physical configurations and physical devices of different nature. The main result of this study has been to build a model of competencies that is being used to build robotic systems capable of displaying behaviors similar to humans and consider the specific characteristics of robots.

Microwave-assisted catalysis by iron oxide nanoparticles on MCM-41: Effect of the support morphology

Catalytically active heterogeneous catalysts have been prepared via microwave deposition of iron oxide nanoparticles (0.5–1.2 wt%) on MCM-41 type silica materials with different morphologies (particles, helical and spheres). This methodology leads to iron oxide nanoparticles composed by a mixture of FeO and Fe2O3 species, being the Fe(II)/Fe(III) peak ratio near to 1.11 by XPS. DRUV spectroscopy indicates the presence of tetrahedral coordinated Fe3+ in the silica framework of the three catalysts as well as some extraframework iron species in the catalysts with particle and sphere-like morphologies. The loading of the nanoparticles does neither affect the mesopore arrangement nor the textural properties of the silica supports, as indicated by SAXS and nitrogen adsorption/desorption isotherms. A detailed investigation of the morphology of the supports in various microwave-assisted catalyzed processes shows that helical mesostructures provide optimum catalytic activities and improved reusabilities in the microwave-assisted redox (selective oxidation of benzyl alcohol) catalyzed process probably due to a combination of lower particle size and higher acidity in comparison with the supports with particle and sphere morphology.

Plastisol foaming process. Decomposition of the foaming agent, polymer behavior in the corresponding temperature range and resulting foam properties

The decomposition of azodicarbonamide, used as foaming agent in PVC—plasticizer (1/1) plastisols was studied by DSC. Nineteen different plasticizers, all belonging to the ester family, two being polymeric (polyadipates), were compared. The temperature of maximum decomposition rate (in anisothermal regime at 5 K min−1 scanning rate), ranges between 434 and 452 K. The heat of decomposition ranges between 8.7 and 12.5 J g−1. Some trends of variation of these parameters appear significant and are discussed in terms of solvent (matrix) and viscosity effects on the decomposition reactions. The shear modulus at 1 Hz frequency was determined at the temperature of maximum rate of foaming agent decomposition, and differs significantly from a sample to another. The foam density was determined at ambient temperature and the volume fraction of bubbles was used as criterion to judge the efficiency of the foaming process. The results reveal the existence of an optimal shear modulus of the order of 2 kPa that corresponds roughly to plasticizer molar masses of the order of 450 ± 50 g mol−1. Heavier plasticizers, especially polymeric ones are too difficult to deform. Lighter plasticizers such as diethyl phthalate (DEP) deform too easily and presumably facilitate bubble collapse.

Pollutant Formation During the Thermal Decomposition of Electrical and Electronic Wastes

Paper submitted to the 7th International Symposium on Feedstock Recycling of Polymeric Materials (7th ISFR 2013), New Delhi, India, 23-26 October 2013.

Thermogravimetric Study of the Decomposition of Printed Circuit Boards from Mobile Phones

Paper submitted to the 19th International Symposium on Analytical & Applied Pyrolysis, Linz, Austria, 21-25 May 2012.

Carbon nanotube-supported Ni–CeO2 catalysts. Effect of the support on the catalytic performance in the low-temperature WGS reaction

The low temperature water-gas shift (WGS) reaction has been studied over two commercial multiwall carbon nanotubes-supported nickel catalysts promoted by ceria. For comparison purposes, activated carbon-supported catalysts have also been studied. The catalytic performance and the characterization by N2 adsorption analysis, powder X-ray diffraction (XRD), temperature-programmed reduction with H2 (TPR-H2), X-ray photoelectron spectroscopy (XPS) and transmission electron microscopy (TEM) analysis showed that the surface chemistry has an important effect on the dispersion of ceria. As a result, ceria was successfully dispersed over the carbon nanotubes (CNTs) with less graphitic character, and the catalyst afforded better activity in WGS than the catalyst prepared over massive ceria. Moreover, a 20 wt.% CeO2 loading over this support was more active than the analogous catalyst with a 40 wt.% loading. The ceria nanoparticles were smaller when the support was previously oxidized, however this resulted in a decrease of the activity.

The combined effect of plastics and food waste accelerates the thermal decomposition of refuse-derived fuels and fuel blends

Mechanical treatments such as shredding or extrusion are applied to municipal solid wastes (MSW) to produce refuse-derived fuels (RDF). In this way, a waste fraction (mainly composed by food waste) is removed and the quality of the fuel is improved. In this research, simultaneous thermal analysis (STA) was used to investigate how different mechanical treatments applied to MSW influence the composition and combustion behaviour of fuel blends produced by combining MSW or RDF with wood in different ratios. Shredding and screening resulted in a more efficient mechanical treatment than extrusion to reduce the chlorine content in a fuel, which would improve its quality. This study revealed that when plastics and food waste are combined in the fuel matrix, the thermal decomposition of the fuels are accelerated. The combination of MSW or RDF and woody materials in a fuel blend has a positive impact on its decomposition.