3,233 research outputs found
Elimination distance to bounded degree on planar graphs
No full textWe study the graph parameter elimination distance to bounded degree, whichwas introduced by Bulian and Dawar in their study of the parameterizedcomplexity of the graph isomorphism problem. We prove that the problem isfixed-parameter tractable on planar graphs, that is, there exists an algorithmthat given a planar graph and integers and decides in time for a computable function~ and constant whether theelimination distance of to the class of degree graphs is at most .Comment: 12 pages, 1 figur
Editions Comp'Act : Champagny en Vanoise Un pays et des hommes.
No full textVigny Françoise. Editions Comp'Act : Champagny en Vanoise Un pays et des hommes.. In: Revue de géographie alpine, tome 90, n°1, 2002. Organisation et gestion des flux touristiques, sous la direction de Alexandre Mignotte et Jérôme Petit. p. 97
Recursive Backdoors for SAT
No full textA strong backdoor in a formula φ of propositional logic to a tractable class C of formulas is a set B of variables of φ such that every assignment of the variables in B results in a formula from C. Strong backdoors of small size or with a good structure, e.g. with small backdoor treewidth, lead to efficient solutions for the propositional satisfiability problem SAT.
In this paper we propose the new notion of recursive backdoors, which is inspired by the observation that in order to solve SAT we can independently recurse into the components that are created by partial assignments of variables. The quality of a recursive backdoor is measured by its recursive backdoor depth. Similar to the concept of backdoor treewidth, recursive backdoors of bounded depth include backdoors of unbounded size that have a certain treelike structure. However, the two concepts are incomparable and our results yield new tractability results for SAT
First-Order Logic with Connectivity Operators
No full textFirst-order logic (FO) can express many algorithmic problems on graphs, such as the independent set and dominating set problem parameterized by solution size. On the other hand, FO cannot express the very simple algorithmic question whether two vertices are connected. We enrich FO with connectivity predicates that are tailored to express algorithmic graph properties that are commonly studied in parameterized algorithmics. By adding the atomic predicates conn_k(x,y,z_1,…,z_k) that hold true in a graph if there exists a path between (the valuations of) x and y after (the valuations of) z_1,…,z_k have been deleted, we obtain separator logic FO+conn. We show that separator logic can express many interesting problems such as the feedback vertex set problem and elimination distance problems to first-order definable classes. Denote by FO+conn_k the fragment of separator logic that is restricted to connectivity predicates with at most k+2 variables (that is, at most k deletions). We show that FO+conn_{k+1} is strictly more expressive than FO+conn_k for all k ≥ 0. We then study the limitations of separator logic and prove that it cannot express planarity, and, in particular, not the disjoint paths problem. We obtain the stronger disjoint-paths logic FO+DP by adding the atomic predicates disjoint-paths_k[(x_1,y_1),…,(x_k,y_k)] that evaluate to true if there are internally vertex-disjoint paths between (the valuations of) x_i and y_i for all 1 ≤ i ≤ k. Disjoint-paths logic can express the disjoint paths problem, the problem of (topological) minor containment, the problem of hitting (topological) minors, and many more. Again we show that the fragments FO+DP_k that use predicates for at most k disjoint paths form a strict hierarchy of expressiveness. Finally, we compare the expressive power of the new logics with that of transitive-closure logics and monadic second-order logic
Elimination distance to bounded degree on planar graphs
No full textWe study the graph parameter elimination distance to bounded degree, which was introduced by Bulian and Dawar in their study of the parameterized complexity of the graph isomorphism problem. We prove that the problem is fixed-parameter tractable on planar graphs, that is, there exists an algorithm that given a planar graph and integers and decides in time for a computable function~ and constant whether the elimination distance of to the class of degree graphs is at most .12 pages, 1 figur
La filosofía del derecho de Alexandre Kojève
No full textThis article is a presentation of Alexandre Kojève’s philosophy of law, exposed in his Esquisse d’une phénoménologie du droit (1981). Little attention has been paid to this work. So there is a gap that has to be filled with a critical reflection of its strengths. Among them, undoubtedly, we count the fact that Kojève is introducing a conception of international justice that casts a singular light on current debates about cosmopolitanism and globalization. According to this author, citizenship is the key element of the process of global expansion of the juridical sphere. In sum, Kojève’s philosophy is useful to reflect upon the contrast between the juridical and the political, which is the basis for all philosophy of law, in order to achieve world peace and international justice.Este artículo es una presentación de la filosofía del derecho de Alexandre Kojève contenida en su Esquisse d’une phénoménologie du droit (1981). La poca atención que dicha obra ha recibido es un vacío que debiera llenarse con una reflexión crítica de sus puntos fuertes. Entre ellos destaca una concepción de la justicia internacional que proyecta una luz muy singular sobre los actuales debates en torno a la globalización y el cosmopolitismo. A ojos de este autor, la ciudadanía es el elemento clave para aquilatar la expansión global de lo jurídico. En suma, Kojève aparece como un valioso referente en la labor de pensar la contraposición entre lo jurídico y lo político que está en la base de toda filosofía del derecho, con la aspiración al logro de la justicia internacional y la paz mundial en el horizonte
Advances in Algorithmic Meta Theorems (Invited Paper)
No full textTractability results for the model checking problem of logics yield powerful algorithmic meta theorems of the form:
Every computational problem expressible in a logic ℒ can be solved efficiently on every class C of structures satisfying certain conditions.
The most prominent logics studied in the field are (counting) monadic second-order logic (C)MSO and first-order logic FO and its extensions. The complexity of CMSO model checking in general and of FO model checking on monotone graph classes is very well understood. In recent years there has been a rapid and exciting development of new algorithmic meta theorems. On the one hand there has been major progress for FO model checking on hereditary graph classes. This progress was driven by the development of a combinatorial structure theory for the logically defined monadically stable and monadically dependent graph classes, as well as by the advent of the new width measure twinwidth. On the other hand new algorithmic meta theorems for new logics with expressive power between FO and CMSO offer a new unifying view on methods like the irrelevant vertex technique and recursive understanding. In this paper we overview the recent advances in algorithmic meta theorems and provide rough sketches for the methods to prove them
Reconfiguração do consensualismo contratual: as ações tituladas nominativas e os limites à transmissão
No full textPartimos da evolução histórica do consensualismo contratual salientando os
principais carateres que, nos diversos momentos históricos, se foram evidenciando.
Numa segunda etapa exploramos os fundamentos dogmáticos do modelo de
transmissão contratual assumido pelo legislador e a sua viabilidade no sistema
jurídico global, em particular, no direito dos valores mobiliários. Constatamos a
crescente necessidade na prática mercantil e inevitabilidade no sistema jurídico
global da admissibilidade da existência de contratos de compra e venda de natureza
meramente obrigacional. Num terceiro momento desenvolvemos os principais
aspetos do regime jurídico aplicável às ações tituladas nominativas fora do mercado
regulado, em particular, os principais limites à transmissão, enquanto instrumentos/barreiras ao consensualismo contratual.We start from the historical evolution of contractual consensualism emphasizing the
main aspects that, in different historical moments, were showing up. In a second
stage we explore the dogmatic foundations of the transmission model contractual
assumed by the legislator and its viability in the global legal system, in particular, in
securities law. We note the growing need in commercial practice and inevitability in
the global legal system the admissibility of the existence of contracts of sale purely
obligatory. In the third stage we develop the main aspects of the legal regime
applicable to nominative titled actions outside the regulated market, in particular,
the main limits to the transmission, as instruments / barriers to contractual
consensualism
“Era por Alexandre tod’esto demostrado”: ¿pruebas verídicas y pruebas engañosas en el Libro de Alexandre?
No full textEl Libro de Alexandre es un texto de s. XIII, que se escribió en la España medieval. En este escrito, el autor pretende demostrar que, en el Alexandre, algunas de las situaciones que se ponen a prueba son aceptadas, pero eso no significa que el macedonio gane la prueba. El articulo esta dividido en tres apartados. En el primero, el autor da cuenta de la historia textual de la obra y también dedica ciertas líneas al Estado de la cuestión del texto; mientras que, en la segunda parte, nos guía a conceptos etimológicos de los términos prueba, evidencia y demás. En el tercer apartado se centra en algunas pruebas expuestas en el Libro de Alexandre.The Libro de Alexandre is a literary work, written during the medieval Spain. In this paper, the author tries to demonstrate that, carefully reading the L.A, some of the situations that are set as proves are accepted, but it does not mean that Alexander can be a victor. This paper is divided in three sections: firstly, the author tells the textual history of the L.A and, then, tries to update the State of art: on the other hand, in the second part, the author offers meanings about terms as: prueba and evidencia. Finally, the author focuses on certain passages contained in the Libro de Alexandre that can be taken as failed proves
Mixing the Immiscible: Improvisation within Fixed-Media Composition
No full textThis paper will explore ways in which mastered improvisation practice, with the studio as an instrument, is a proposed avenue to bridge the historical dichotomy between what Ted Gioia describe as ‘the aesthetics of perfection’ and ‘the aesthetics of imperfection’. It is proposed as a way to re-embody fixed music, as experimented by the author through the composition of his last fixed-media work. This will be put in the context of a wider trend observed amongst the current emerging generation of composers interested in the aesthesics of the work, by opposition to the previous generations that placed the value of the work in its poietics. The vital and primal importance of practice outcome as practice-based research’s main document will also be advocated for, as these trends are happening in the laboratory of live music
- …
