Sorting under partial information (without the ellipsoid algorithm)

We revisit the well-known problem of sorting under partial information: sort a finite set given the outcomes of comparisons between some pairs of elements. The input is a partially ordered set P, and solving the problem amounts to discovering an unknown linear extension of P, using pairwise comparisons. The information-theoretic lower bound on the number of comparisons needed in the worst case is log e(P), the binary logarithm of the number of linear extensions of P. In a breakthrough paper, Jeff Kahn and Jeong Han Kim (STOC 1992) showed that there exists a polynomial-time algorithm for the problem achieving this bound up to a constant factor. Their algorithm invokes the ellipsoid algorithm at each iteration for determining the next comparison, making it impractical. We develop efficient algorithms for sorting under partial information. Like Kahn and Kim, our approach relies on graph entropy. However, our algorithms differ in essential ways from theirs. Rather than resorting to convex programming for computing the entropy, we approximate the entropy, or make sure it is computed only once in a restricted class of graphs, permitting the use of a simpler algorithm. Specifically, we present: an O(n2) algorithm performing O(log n·log e(P)) comparisons; an O(n2.5) algorithm performing at most (1+ε) log e(P) + Oε(n) comparisons; an O(n2.5) algorithm performing O(log e(P)) comparisons. All our algorithms are simple to implement. © 2010 ACM.

A toolset for the analysis of et-lotos specifications

info:eu-repo/semantics/published

A simulator of real-time systems specified in et-lotos

info:eu-repo/semantics/published

Platinum nuclei: Concealed configuration mixing and shape coexistence

The role of configuration mixing in the Pt region is investigated. For this chain of isotopes, the nature of the ground state changes smoothly, being spherical around mass A~174 and A~192 and deformed around the midshell N=104 region. This has a dramatic effect on the systematics of the energy spectra as compared to the systematics in the Pb and Hg nuclei. Interacting boson model with configuration mixing calculations are presented for gyromagnetic factors, α-decay hindrance factors, and isotope shifts. The necessity of incorporating intruder configurations to obtain an accurate description of the latter properties becomes evident. © 2011 American Physical Society.

Cannibal Animal Games: A new variant of Tic-Tac-Toe

This paper presents a new partial two-player game, called the cannibal animal game, which is a variant of Tic-Tac-Toe. The game is played on the infinite grid, where in each round a player chooses and occupies free cells. The first player Alice can occupy a cell in each turn and wins if she occupies a set of cells, the union of a subset of which is a translated, reflected and/or rotated copy of a previously agreed upon polyomino P (called an animal). The objective of the second player Bob is to prevent Alice from creating her animal by occupying in each round a translated, reflected and/or rotated copy of P. An animal is a cannibal if Bob has a winning strategy, and a non-cannibal otherwise. This paper presents some new tools, such as the bounding strategy and the punching lemma, to classify animals into cannibals or non-cannibals. We also show that the pairing strategy works for this problem.

Traitement de données issues d'un corpus écrit multilingue. Approche agile pour l'analyse du discours eurorégional

L'article présente quelques éléments de la procédure mise en place pour traiter un corpus écrit comportant 617 textes (près de 500 000 mots) relatifs aux eurorégions. Complexe et hétérogène à plusieurs titres (technique, linguistique, éditorial, générique, énonciatif), le corpus pose la difficulté majeure de l’appréhension de données multilingues (français, italien, espagnol, anglais, allemand, néerlandais). Sa manipulation a nécessité une réflexion adaptée et une démarche de modélisation que nous qualifions d’« agile » en raison de son caractère souple et itératif. La plateforme d’analyse élaborée permet de disposer de résultats utiles à l’analyse qualitative ultérieure du discours eurorégional. Elle articule un logiciel d'analyse morphosyntaxique éprouvé (TreeTagger) à des programmes (Perl) et à une base de données (SQLite) développés pour optimiser les requêtes multilingues simultanées et l’exportation automatique des résultats. Les fonctionnalités liées à la localisation contextualisée de mots- pivots, au recueil de dénominations et à la détection de segments répétés nous servent ici de guides pour exprimer les besoins de la recherche, les problèmes rencontrés et les solutions proposées. L'analyse d'observables récurrents, à savoir les notions de décision et de responsabilité, illustre le propos.

Discussion of "On families of distributions with shape parameters", by M.C. Jones

SCOPUS: ar.j

Efficient energy distribution in a smart grid using multi-player games

info:eu-repo/semantics/submittedForPublication

Hopf hypersurfaces in pseudo-Riemannian complex and para-complex space forms

The study of real hypersurfaces in pseudo-Riemannian complex space forms and para-complex space forms, which are the pseudo-Riemannian generalizations of the complex space forms, is addressed. It is proved that there are no umbilic hypersurfaces, nor real hypersurfaces with parallel shape operator in such spaces. Denoting by J be the complex or para-complex structure of a pseudo-complex or para-complex space form respectively, a non-degenerate hypersurface of such space with unit normal vector field N is said to be Hopf if the tangent vector field JN is a principal direction. It is proved that if a hypersurface is Hopf, then the corresponding principal curvature (the Hopf curvature) is constant. It is also observed that in some cases a Hopf hypersurface must be, locally, a tube over a complex (or para-complex) submanifold, thus generalizing previous results of Cecil, Ryan and Montiel.

Comments on: Static and dynamic source locations in undirected networks

SCOPUS: ed.j

Asymmetric polygons with maximum area

We say that a polygon inscribed in the circle is asymmetric if it contains no two antipodal points being the endpoints of a diameter. Given n diameters of a circle and a positive integer k < n, this paper addresses the problem of computing a maximum area asymmetric k-gon having as vertices k < n endpoints of the given diameters. The study of this type of polygons is motivated by ethnomusiciological applications.

Classic Nintendo games are (computationally) hard

We prove NP-hardness results for five of Nintendo's largest video game franchises: Mario, Donkey Kong, Legend of Zelda, Metroid, and Pokémon. Our results apply to generalized versions of Super Mario Bros.1-3, The Lost Levels, and Super Mario World; Donkey Kong Country 1-3; all Legend of Zelda games; all Metroid games; and all Pokémon role-playing games. In addition, we prove PSPACE-completeness of the Donkey Kong Country games and several Legend of Zelda games.

Hamiltonian derivation of higher-spin charges

info:eu-repo/semantics/nonPublished