Planning is a central research area in artificial intelligence, and a lot of effort has gone into constructing more and more efficient planning algorithms. In real-world examples, many problem instances do not have a solution. Hence, there is an obvious need for methods that are capable of identifying unsolvable instances efficiently. It is not possible to efficiently identify all unsolvable instances due to the inherent high complexity of planning, but many unsolvable instances can be identified in polynomial time. We present a number of novel methods for doing this. We adapt the notion of k-consistency (a well-studied concept from constraint satisfaction) for testing unsolvability of planning instances. The idea is to decompose a given problem instance into a number of smaller instances which can be solved in polynomial time. If any of the smaller instances are unsolvable, then the original instance is unsolvable. If all the smaller instances are solvable, then it is possible to extract information which can be used to guide the search. For instance, we introduce the notion of forbidden state patterns that are partial states that must be avoided by any solution to the problem instance. This can be viewed as the opposite of pattern databases which give information about states which can lead to a solution.  We also introduce the notion of critical sets and show how to identify them. Critical sets describe operators or values which must be used or achieved in any solution. It is a variation on the landmark concept, i.e., operators or values which must be used in every solution. With the help of critical sets we can identify superfluous operators and values. These operators and values can be removed by preprocessing the problem instance to decrease planning time.

We have two main results. Our first main result is a sharp bound for the number of vertices in a minimal forbidden subgraph for the graphs having minimum rank at most 3 over the finite field of order 2. We also list all 62 such minimal forbidden subgraphs and show that many of these are minimal forbidden subgraphs for any field. Our second main result is a structural characterization of all graphs having minimum rank at most k for any k over any finite field. This characterization leads to a very strong connection to projective geometry and we apply projective geometry results to the minimum rank problem.

In structural graph theory, connectivity is an important notation with a lot of applications. Tutte, in 1961, showed that a simple graph is 3-connected if and only if it can be generated from a wheel graph by repeatedly adding edges between nonadjacent vertices and applying vertex splitting. In 1971, Halin constructed a class of edge-minimal 3-connected planar graphs, which are a generalization of wheel graphs and later were named “Halin graphs” by Lovasz and Plummer. A Halin graph is obtained from a plane embedding of a tree with no stems having degree 2 by adding a cycle through its leaves in the natural order determined according to the embedding. Since Halin graphs were introduced, many useful properties, such as Hamiltonian, hamiltonian-connected and pancyclic, have been discovered. Hence, it will reveal many properties of a graph if we know the graph contains a spanning Halin subgraph. But unfortunately, until now, there is no positive result showing under which conditions a graph contains a spanning Halin subgraph. In this thesis, we characterize all forbidden pairs implying graphs containing spanning Halin subgraphs. Consequently, we provide a complete proof conjecture of Chen et al. Our proofs are based on Chudnovsky and Seymour’s decomposition theorem of claw-free graphs, which were published recently in a series of papers.

Morální principy v současném šíitském islámu, zvl. Íránu a Iráku Moral Princips In contemporey Shi'a islam (esp. In Iran and Iraq) Šárka Ambrosio In this body of work we look at the moral principles of the Shiite Muslims faith and their reasons for fundamentalism in the second half of the 20th century. The morality of the Shiite faith is a delicate balanced between religion and politics. If the political and the religious institutions do not work in harmony, the typical results are society and economical disruption. Even in a secular state, non-believing citizens who have a basic moral value to live a peaceful co- existences can be disarrayed by conflicts within government and church. What then comes into question is the role the state takes in compliance with certain laws that effect the populous. The answer often defaults to the moral beliefs people have about their understanding of their Creator. There is the claim that morality has no authority. Thus, peoples faith in God and the knowledge of His law ensures a harmony in a social structure. It is no co-incidence that a growing Western pressure in the second half of the 20th century has equated to a growth in Eastern Islam fundamentalist. There is a cause and effect. The solution is not simple but peace can only be founded if the Eastern...

Le thème central à cette thèse est l'étude des propriétés des classes de graphes définies par sous-structures interdites et leurs applications.La première direction que nous suivons a trait aux beaux ordres. À l'aide de théorèmes de décomposition dans les classes de graphes interdisant une sous-structure, nous identifions celles qui sont bellement-ordonnées. Les ordres et sous-structures considérés sont ceux associés aux notions de contraction et mineur induit. Ensuite, toujours en considérant des classes de graphes définies par sous-structures interdites, nous obtenons des bornes sur des invariants comme le degré, la largeur arborescente, la tree-cut width et un nouvel invariant généralisant la maille.La troisième direction est l'étude des relations entre les invariants combinatoires liés aux problèmes de packing et de couverture de graphes. Dans cette direction, nous établissons de nouvelles relations entre ces invariants pour certaines classes de graphes. Nous présentons également des applications algorithmiques de ces résultats. / The central theme of this thesis is the study of the properties of the classes of graphs defined by forbidden substructures and their applications.The first direction that we follow concerns well-quasi-orders. Using decomposition theorems on graph classes forbidding one substructure, we identify those that are well-quasi-ordered. The orders and substructures that we consider are those related to the notions of contraction and induced minor.Then, still considering classes of graphs defined by forbidden substructures, we obtain bounds on invariants such as degree, treewidth, tree-cut width, and a new invariant generalizing the girth.The third direction is the study of the links between the combinatorial invariants related to problems of packing and covering of graphs. In this direction, we establish new connections between these invariants for some classes of graphs. We also present algorithmic applications of the results.

A criminalidade transnacional é um dos males da atualidade e tem seu crescimento associado à complexidade dos processos da globalização. Quão mais interligadas estão a economia, cultura e demais comunicações dos Estados, mais vulneráveis estão às ações criminosas. Diante desta constatação a comunidade internacional escolheu o Direito Penal Internacional como um dos instrumentos destinados a fazer frente a este problema contemporâneo. O DPI, como especialização do Direito Penal, atende às exigências da comunidade internacional, por ser constituído pelo binômio criminalização e instituições de repressão e por contemplar dois distintos referenciais, quais sejam o do observador nacional que vê a projeção de seu ordenamento jurídico para fora das fronteiras territoriais e a do observador internacional que vê a projeção das normas internacionais para dentro do território dos Estados. A importância do DPI para o combate ao crime se faz pela pluralidade de espécies de cooperação (administrativa e jurídica) e de formas, que vão desde as mais clássicas como a extradição, a carta rogatória e a homologação da sentença estrangeira às mais modernas como a transferência de presos e a assistência mútua. As formas mais clássicas da cooperação têm se mostrado pouco eficazes e muito burocráticas para alcançar os resultados pretendidos, principalmente pelas barreiras jurídicas impostas pelos Estados, A assistência mútua vai ao encontro das expectativas internacionais, por simplificar a tramitação dos pedidos, em razão da tramitação dos mesmos por Autoridades Centrais e não por vias diplomáticas, por reduzir as barreiras jurídicas, pois há a possibilidade de mitigação do princípio da identidade, a redução dos motivos de recusa e a desnecessidade de submeter ao crivo do Superior Tribunal de Justiça pedidos que notoriamente dispensam juízo de delibação. Embora a assistência mútua traga muitas vantagens para facilitar a persecução penal, o desprendimento às formalidades e às barreiras jurídicas não pode significar desapego às garantias materiais e processuais das pessoas que são os destinatários da ação estatal persecutória, em especial à garantia de não ter contra si aplicadas penas vedadas constitucionalmente (art. 5, XLVII da CF/88). Neste sentido torna-se necessário reconhecer a existência de uma obrigação de não fazer e não cooperar por parte dos Estados que possa ser invocada para obstar atos de cooperação que possam contribuir para a aplicação das penas vedadas. / The transnational criminality is one of the major problems of the present time and its growth is associated with the complexity in the processes of globalization. The more interconnect the economy, the culture and other means of communications of the State, more vulnerable they are to criminal actions. In face of this fact, the international community chose the International Criminal Law as one of the instruments developed to face this contemporary problem. The ICL, as a specialization of the Criminal Law, fulfills the demands of the international community because it is constituted by the binomial criminalization and repression institutions, and because it contemplates two different perspectives: that of the national observer who sees the projection of its own legal system to outside the territorial boundaries, and that of the international observer who see the projection of the international norms to the inside of the State territory. The importance of the ICL for the fight against crime is seen in a plurality of kinds of cooperation (administrative and judicial) and of methods which range from the most traditional ones, such as extradition, rogatory letters, recognition of foreign sentences, to the most modern ones, such as transfer of prisoners and mutual assistance. The most traditional methods of cooperation are proving themselves to be minimally efficient and excessively bureaucratic to achieve the expected result, specially due to the juridical barriers imposed by the States. The mutual assistance method, however, meets the international expectation because it simplifies the transaction of requests, since they are done by central authorities and not by diplomatic means, and also because it reduced the juridical barriers. The reduction in the juridical barriers happens because it is possible to mitigate the identity principle, to reduce the reasons for rejection and because it deems unnecessary to submit requests that notoriously bypass the approval of the brazilians Superior Court of Justice. Although the mutual assistance brings various advantages in facilitating the criminal persecution, in promoting formality detachment and in diminishing the juridical barriers, it cannot result in a dismissal of material and procedural warranties of those people who are the recipient of the persecutory state action, specially with respect to the warranty that prevents one to have a forbidden punishments applied against oneself (5 art., XLVII of the CF/88). Hence, the recognition of the existence of the obligation to not-do, and, from the side of the State, the existence of the obligation to not-cooperate are necessary, so that they can be invoked to prevent cooperation acts that can contribute to the application of forbidden punishments.

L’objectif de cette thèse est d’attribuer à chaque sommet x d’un graphe G à n sommets une étiquette L(x) de taille compacte O(log n) bits afin de pouvoir :1. construire, à partir des étiquettes d’un ensemble de sommets en panne X C V (G), une structure de donnée S(X)2. décider, à partir de S(X) et des étiquettes L(u) et L(v), si les sommets u et v sont connectés dans le graphe G n X.Nous proposons une solution à ce problème pour la famille des graphes 3-connexes de genre g (via plusieurs résultats intermédiaires).— Les étiquettes sont de taille O(g log n) bits— Le temps de construction de la structure de donnée S(X) est O(Sort([X]; n)).— Le temps de décision est O(log log n). Ce temps est optimal.Nous étendons ce résultat à la famille des graphes excluant un mineur H fixé. Les étiquettes sont ici de taille O(polylog n) bits. / We aim at assigning each vertex x of a n-vertices graph G a compact O(log n)-bit label L(x) in order to :1. construct, from the labels of the vertices of a forbidden set X C V (G), a datastructure S(X)2. decide, from S(X), L(u) and L(v), whether two vertices u and v are connected in G n X.We give a solution to this problem for the family of 3-connected graphs whith bounded genus.— We obtain O(g log n)-bit labels.— S(X) is computed in O(Sort([X]; n)) time.— Connection between vertices is decided in O(log log n) optimal time.We finally extend this result to H-minor-free graphs. This scheme requires O(polylog n)-bit labels.

The first explored area in this thesis is the proposed data hiding method, TCQ-IS. The method is based on Trellis Coded Quantization (TCQ), whose initial state selection is arbitrary. TCQ-IS exploits this fact to hide data. It is a practical multi-dimensional that eliminates the prohibitive task of designing high dimensional quantizers. The strength and weaknesses of the method are stated by various experiments. The second contribution is the proposed data hiding method, Forbidden Zone Data Hiding (FZDH), which relies on the concept of &ldquo / forbidden zone&rdquo / , where host signal is not altered. The main motive of FZDH is to introduce distortion as much as needed, while keeping a range of host signal intact depending on the desired level of robustness. FZDH is compared against Quantization Index Modulation (QIM) as well as DC-QIM and ST-QIM. FZDH outperforms QIM even in 1-D and DC-QIM in higher dimensions. Furthermore, FZDH is comparable with ST-QIM for certain operation regimes. The final contribution is the video data hiding framework that includes FZDH, selective embedding and Repeat Accumulate (RA) codes. De-synchronization due to selective embedding is handled with RA codes. By means of simple rules applied to the embedded frame markers, certain level of robustness against temporal attacks is introduced. Selected coefficients are used to embed message bits by employing multi-dimensional FZDH. The framework is tested with typical broadcast material against common video processing attacks. The results indicate that the framework can be utilized in real life applications.

La méthode des invariants est une des plus utilisées méthodes de synthèse pour les SED modélisés par des réseaux de Petri (RdP). Cependant, elle ne garantit pas en général une solution optimale dans la présence de l'incontrôlabilité. Dans ce travail nous proposons une solution à ce problème pour les RdP généralisés. Premièrement, nous proposons une solution d'identification des contraintes admissibles pour les RdP saufs non-conservatifs. La méthode repose sur une définition des contraintes contenant des marquages complémentés. Ceux-ci sont après éliminés en exploitant les composants conservatifs des RdP. Deuxièmement, nous avançons une technique de détermination des contraintes admissibles pour les RdP généralisés. La méthode est basée sur une vision spatiale de l'espace d'états du modèle. Les contraintes sont dérivées de l'équation d'hyperplan affin qui sépare les régions interdite- et autorisée- de cet espace. Nous proposons un algorithme pour le calcul du contrôleur optimal minimal. / The place-invariants method is one of the most popular controller synthesis approaches for Petri net (PN) modeled DES. Unfortunately, the observance of the constraints is not certain in the presence of uncontrollable transitions. This thesis offers a solution to this problem for ordinary and generalized PNs. We begin by studying safe non-conservative PNs, and devising a constraint-determination technique that will always provide a set of admissible constraints for this type of model. The approach stems from the general definition of forbidden states --- that of marking vectors. In the second part of our work, we present an admissible constraint-determination technique for generalized PNs. The method is based on a special view of the system's state space. The constraints are derived from the equation of the affine hyper-plane separating the authorized- and forbidden- regions of this space. We propose an algorithm that allows the identification of the minimal maximally permissive controller.

A criminalidade transnacional é um dos males da atualidade e tem seu crescimento associado à complexidade dos processos da globalização. Quão mais interligadas estão a economia, cultura e demais comunicações dos Estados, mais vulneráveis estão às ações criminosas. Diante desta constatação a comunidade internacional escolheu o Direito Penal Internacional como um dos instrumentos destinados a fazer frente a este problema contemporâneo. O DPI, como especialização do Direito Penal, atende às exigências da comunidade internacional, por ser constituído pelo binômio criminalização e instituições de repressão e por contemplar dois distintos referenciais, quais sejam o do observador nacional que vê a projeção de seu ordenamento jurídico para fora das fronteiras territoriais e a do observador internacional que vê a projeção das normas internacionais para dentro do território dos Estados. A importância do DPI para o combate ao crime se faz pela pluralidade de espécies de cooperação (administrativa e jurídica) e de formas, que vão desde as mais clássicas como a extradição, a carta rogatória e a homologação da sentença estrangeira às mais modernas como a transferência de presos e a assistência mútua. As formas mais clássicas da cooperação têm se mostrado pouco eficazes e muito burocráticas para alcançar os resultados pretendidos, principalmente pelas barreiras jurídicas impostas pelos Estados, A assistência mútua vai ao encontro das expectativas internacionais, por simplificar a tramitação dos pedidos, em razão da tramitação dos mesmos por Autoridades Centrais e não por vias diplomáticas, por reduzir as barreiras jurídicas, pois há a possibilidade de mitigação do princípio da identidade, a redução dos motivos de recusa e a desnecessidade de submeter ao crivo do Superior Tribunal de Justiça pedidos que notoriamente dispensam juízo de delibação. Embora a assistência mútua traga muitas vantagens para facilitar a persecução penal, o desprendimento às formalidades e às barreiras jurídicas não pode significar desapego às garantias materiais e processuais das pessoas que são os destinatários da ação estatal persecutória, em especial à garantia de não ter contra si aplicadas penas vedadas constitucionalmente (art. 5, XLVII da CF/88). Neste sentido torna-se necessário reconhecer a existência de uma obrigação de não fazer e não cooperar por parte dos Estados que possa ser invocada para obstar atos de cooperação que possam contribuir para a aplicação das penas vedadas. / The transnational criminality is one of the major problems of the present time and its growth is associated with the complexity in the processes of globalization. The more interconnect the economy, the culture and other means of communications of the State, more vulnerable they are to criminal actions. In face of this fact, the international community chose the International Criminal Law as one of the instruments developed to face this contemporary problem. The ICL, as a specialization of the Criminal Law, fulfills the demands of the international community because it is constituted by the binomial criminalization and repression institutions, and because it contemplates two different perspectives: that of the national observer who sees the projection of its own legal system to outside the territorial boundaries, and that of the international observer who see the projection of the international norms to the inside of the State territory. The importance of the ICL for the fight against crime is seen in a plurality of kinds of cooperation (administrative and judicial) and of methods which range from the most traditional ones, such as extradition, rogatory letters, recognition of foreign sentences, to the most modern ones, such as transfer of prisoners and mutual assistance. The most traditional methods of cooperation are proving themselves to be minimally efficient and excessively bureaucratic to achieve the expected result, specially due to the juridical barriers imposed by the States. The mutual assistance method, however, meets the international expectation because it simplifies the transaction of requests, since they are done by central authorities and not by diplomatic means, and also because it reduced the juridical barriers. The reduction in the juridical barriers happens because it is possible to mitigate the identity principle, to reduce the reasons for rejection and because it deems unnecessary to submit requests that notoriously bypass the approval of the brazilians Superior Court of Justice. Although the mutual assistance brings various advantages in facilitating the criminal persecution, in promoting formality detachment and in diminishing the juridical barriers, it cannot result in a dismissal of material and procedural warranties of those people who are the recipient of the persecutory state action, specially with respect to the warranty that prevents one to have a forbidden punishments applied against oneself (5 art., XLVII of the CF/88). Hence, the recognition of the existence of the obligation to not-do, and, from the side of the State, the existence of the obligation to not-cooperate are necessary, so that they can be invoked to prevent cooperation acts that can contribute to the application of forbidden punishments.