On the Cubicity of AT-Free Graphs and Circular-Arc Graphs

A unit cube in k dimensions (k-cube) is defined as the Cartesian product R-1 x R-2 x ... x R-k where R-i (for 1 <= i <= k) is a closed interval of the form [a(i), a(i) + 1] on the real line. A graph G on n nodes is said to be representable as the intersection of k-cubes (cube representation in k dimensions) if each vertex of C can be mapped to a k-cube such that two vertices are adjacent in G if and only if their corresponding k-cubes have a non-empty intersection. The cubicity of G denoted as cub(G) is the minimum k for which G can be represented as the intersection of k-cubes. An interesting aspect about cubicity is that many problems known to be NP-complete for general graphs have polynomial time deterministic algorithms or have good approximation ratios in graphs of low cubicity. In most of these algorithms, computing a low dimensional cube representation of the given graph is usually the first step. We give an O(bw . n) algorithm to compute the cube representation of a general graph G in bw + 1 dimensions given a bandwidth ordering of the vertices of G, where bw is the bandwidth of G. As a consequence, we get O(Delta) upper bounds on the cubicity of many well-known graph classes such as AT-free graphs, circular-arc graphs and cocomparability graphs which have O(Delta) bandwidth. Thus we have: 1. cub(G) <= 3 Delta - 1, if G is an AT-free graph. 2. cub(G) <= 2 Delta + 1, if G is a circular-arc graph. 3. cub(G) <= 2 Delta, if G is a cocomparability graph. Also for these graph classes, there axe constant factor approximation algorithms for bandwidth computation that generate orderings of vertices with O(Delta) width. We can thus generate the cube representation of such graphs in O(Delta) dimensions in polynomial time.

Cluster based core vector machine

Core Vector Machine(CVM) is suitable for efficient large-scale pattern classification. In this paper, a method for improving the performance of CVM with Gaussian kernel function irrespective of the orderings of patterns belonging to different classes within the data set is proposed. This method employs a selective sampling based training of CVM using a novel kernel based scalable hierarchical clustering algorithm. Empirical studies made on synthetic and real world data sets show that the proposed strategy performs well on large data sets.

Bicriterion differential games with qualitative outcomes

Combat games are studied as bicriterion differential games with qualitative outcomes determined by threshold values on the criterion functions. Survival and capture strategies of the players are defined using the notion of security levels. Closest approach survival strategies (CASS) and minimum risk capture strategies (MRCS) are important strategies for the players identified as solutions to four optimization problems involving security levels. These are used, in combination with the preference orderings of the qualitative outcomes by the players, to delineate the win regions and the secured draw and mutual kill regions for the players. It is shown that the secured draw regions and the secured mutual kill regions for the two players are not necessarily the same. Simple illustrative examples are given.

FinnWordNet - WordNet på finska via översättning

FinnWordNet is a WordNet for Finnish that conforms to the framework given in Fellbaum (1998) and Vossen (ed.) (1998). FinnWordNet is open source and currently contains 117,000 synsets. A classic WordNet consists of synsets, or sets of partial synonyms whose shared meaning is described and exemplified by a gloss, a common part of speech and a hyperonym. Synsets in a WordNet are arranged in hierarchical partial orderings according to semantic relations like hyponymy/hyperonymy. Together the gloss, part of speech and hyperonym fix the meaning of a word and constrain the possible translations of a word in a given synset. The Finnish group has opted for translating Princeton WordNet 3.0 synsets wholesale into Finnish by professional translators, because the translation process can be controlled with regard to quality, coverage, cost and speed of translation. The project was financed by FIN-CLARIN at the University of Helsinki. According to our preliminary evaluation, the translation process was diligent and the quality is on a par with the original Princeton WordNet.

O sistema internacional pós-crise de 2008 e as relações China- Estados Unidos: uma análise em três frentes

As relações sino-americanas passaram a desempenhar um papel ordenador fundamental na condução dos assuntos internacionais neste século XXI, ao ponto de alguns analistas criarem o termo G-2. A crise financeira de 2008, por representar um golpe profundo nos países desenvolvidos e nos direcionamentos de valores do estágio atual de desenvolvimento do sistema, levou a relação China-Estados Unidos a um outro patamar. Ao passo que os norte-americanos tiveram de se preocupar em resolver as turbulências causadas na economia doméstica, o país asiático passou a desempenhar um papel crucial no processo de recuperação da economia global. O presente trabalho tem o objetivo, então, de analisar de que forma a crise de 2008, também chamada de crise do subprime, impactou os ordenamentos centrais do Sistema Internacional neste período de recuperação e como as relações sino-americanas podem ser usadas para uma melhor compreensão deste fenômeno. Na busca por traçar respostas mais sólidas, a pesquisa delineia-se em três frentes principais de análise: as relações diretas entre China e Estados Unidos; as relações dos dois países com um terceiro ator, a saber, a África; e os posicionamentos adotados por ambas as partes nas instituições multilaterais. Para tal, primeiro buscou-se aliar análises qualitativas e quantitativas, baseadas em instrumentais matemáticos e também na Ciência Política, História e Economia Política Internacional, para alcançar os resultados definidos nos objetivos da pesquisa. A dissertação é dividida em cinco capítulos, onde os três primeiros tratam de introduzir o assunto estudado e as principais vertentes teóricas utilizadas ao longo do trabalho. Os últimos envolvem a aplicação prática dos conceitos interdisciplinares escolhidos como aliados do trabalho empírico e a apresentação dos resultados finais. Em linhas gerais, concluiu-se que a crise acentuou os aspectos de interdependência entre China e Estados Unidos em todas as frentes estudadas. Avaliando as relações sino-americanas e os rumos do sistema internacional pós-crise em três facetas, concluímos também que tal exercício analítico ofereceu recursos mais palpáveis no fornecimento das respostas procuradas pela dissertação.

Facilitation of learning induced by both random and gradual visuomotor task variation.

Motor task variation has been shown to be a key ingredient in skill transfer, retention, and structural learning. However, many studies only compare training of randomly varying tasks to either blocked or null training, and it is not clear how experiencing different nonrandom temporal orderings of tasks might affect the learning process. Here we study learning in human subjects who experience the same set of visuomotor rotations, evenly spaced between -60° and +60°, either in a random order or in an order in which the rotation angle changed gradually. We compared subsequent learning of three test blocks of +30°→-30°→+30° rotations. The groups that underwent either random or gradual training showed significant (P < 0.01) facilitation of learning in the test blocks compared with a control group who had not experienced any visuomotor rotations before. We also found that movement initiation times in the random group during the test blocks were significantly (P < 0.05) lower than for the gradual or the control group. When we fit a state-space model with fast and slow learning processes to our data, we found that the differences in performance in the test block were consistent with the gradual or random task variation changing the learning and retention rates of only the fast learning process. Such adaptation of learning rates may be a key feature of ongoing meta-learning processes. Our results therefore suggest that both gradual and random task variation can induce meta-learning and that random learning has an advantage in terms of shorter initiation times, suggesting less reliance on cognitive processes.

Electronic structures of wurtzite ZnO, BeO, MgO and p-type doping in Zn1-xYxO (Y = Mg, Be)

Using the density function theory within the generalized gradient approximation, the band structures of wurtzite ZnO, BeO and MgO have been calculated. The effective-mass parameters are fitted using the calculated eigenvalues. The Dresselhaus spin-orbit effect appears in the k[1 00] direction, and is zero in the high symmetry direction k[00 1]. The orderings of valence band split by the crystal-field and spin-orbit coupling in wurtzite ZnO, BeO and MgO are identified by analyzing the wave function characters calculated by projecting the wave functions onto p-state in the spherical harmonics. For wurtzite ZnO, the ordering of valence band is Still Gamma(7) > Gamma(9) > Gamma(7) due to the negative spin-orbit coupling splitting energy and the positive crystal-field splitting energy. Thus, the Thomas' conclusion is confirmed. For wurtzite BeO and MgO, although their orderings of valence bands are Gamma(7) > Gamma(9) > Gamma(7) too, the origins of their orderings are different from that of wurtzite ZnO. Zn1-x,YxO (Y = Mg, Be) doped with N and P atoms have been studied using first-principles method. The calculated results show that N atom doped in Zn1-x BexO has more shallow acceptor energy level with increasing the concentration of Be atom. (C) 2008 Elsevier B.V. All rights reserved.

Electronic and magnetic properties of the monoclinic phase BiCrO3 from first-principles studies

Based on density functional theory, we systematically studied the electronic and magnetic properties of the real experimental structural phase BiCrO3 with the space group C2/c. It is found that the ground state is a moderately correlated Mott-Hubbard insulator with G-type antiferromagnetic structure, which is in agreement with the experimental observations. The magnetism can be qualitatively understood in terms of the superexchange mechanism via Cr1(t(2g))-O 2p-Cr-2(t(2g)). Moreover, the total energies calculated for various magnetic orderings lead to an estimate of the magnetic interaction constants.

Influence of Mn-O-Mn bond angle on the magnetic and electronic properties in YBaMn2O5

The influence of the Mn-O-Mn bond angle on the magnetic and electronic properties of YBaMn2O5 was studied by density functional theory, which was implemented in the CASTEP code. In practical calculation, both G- and A-type antiferromagnetic (AFM) orderings were considered. The calculated results indicated that G-type is more stable than A-type, in agreement with both experiment and previous theoretical study. It is also interesting to note that a transition from G-type to A-type at an Mn-O-Mn angle of ca. 170 degrees was found upon increasing Mn-O-Mn angle. Therefore, the calculation suggested that what is essential to stabilize the G-type AFM state is the reduction of the Mn-O-Mn bond angle. For both magnetic orderings, the compound changes from semiconductor to metal with the increase of Mn-O-Mn angle.

Fuzzy ART

Adaptive Resonance Theory (ART) models are real-time neural networks for category learning, pattern recognition, and prediction. Unsupervised fuzzy ART and supervised fuzzy ARTMAP synthesize fuzzy logic and ART networks by exploiting the formal similarity between the computations of fuzzy subsethood and the dynamics of ART category choice, search, and learning. Fuzzy ART self-organizes stable recognition categories in response to arbitrary sequences of analog or binary input patterns. It generalizes the binary ART 1 model, replacing the set-theoretic: intersection (∩) with the fuzzy intersection (∧), or component-wise minimum. A normalization procedure called complement coding leads to a symmetric: theory in which the fuzzy inter:>ec:tion and the fuzzy union (∨), or component-wise maximum, play complementary roles. Complement coding preserves individual feature amplitudes while normalizing the input vector, and prevents a potential category proliferation problem. Adaptive weights :otart equal to one and can only decrease in time. A geometric interpretation of fuzzy AHT represents each category as a box that increases in size as weights decrease. A matching criterion controls search, determining how close an input and a learned representation must be for a category to accept the input as a new exemplar. A vigilance parameter (p) sets the matching criterion and determines how finely or coarsely an ART system will partition inputs. High vigilance creates fine categories, represented by small boxes. Learning stops when boxes cover the input space. With fast learning, fixed vigilance, and an arbitrary input set, learning stabilizes after just one presentation of each input. A fast-commit slow-recode option allows rapid learning of rare events yet buffers memories against recoding by noisy inputs. Fuzzy ARTMAP unites two fuzzy ART networks to solve supervised learning and prediction problems. A Minimax Learning Rule controls ARTMAP category structure, conjointly minimizing predictive error and maximizing code compression. Low vigilance maximizes compression but may therefore cause very different inputs to make the same prediction. When this coarse grouping strategy causes a predictive error, an internal match tracking control process increases vigilance just enough to correct the error. ARTMAP automatically constructs a minimal number of recognition categories, or "hidden units," to meet accuracy criteria. An ARTMAP voting strategy improves prediction by training the system several times using different orderings of the input set. Voting assigns confidence estimates to competing predictions given small, noisy, or incomplete training sets. ARPA benchmark simulations illustrate fuzzy ARTMAP dynamics. The chapter also compares fuzzy ARTMAP to Salzberg's Nested Generalized Exemplar (NGE) and to Simpson's Fuzzy Min-Max Classifier (FMMC); and concludes with a summary of ART and ARTMAP applications.

Fuzzy ARTMAP: A Neural Network Architecture for Incremental Supervised Learning of Analog Multidimensional Maps

A new neural network architecture is introduced for incremental supervised learning of recognition categories and multidimensional maps in response to arbitrary sequences of analog or binary input vectors. The architecture, called Fuzzy ARTMAP, achieves a synthesis of fuzzy logic and Adaptive Resonance Theory (ART) neural networks by exploiting a close formal similarity between the computations of fuzzy subsethood and ART category choice, resonance, and learning. Fuzzy ARTMAP also realizes a new Minimax Learning Rule that conjointly minimizes predictive error and maximizes code compression, or generalization. This is achieved by a match tracking process that increases the ART vigilance parameter by the minimum amount needed to correct a predictive error. As a result, the system automatically learns a minimal number of recognition categories, or "hidden units", to met accuracy criteria. Category proliferation is prevented by normalizing input vectors at a preprocessing stage. A normalization procedure called complement coding leads to a symmetric theory in which the MIN operator (Λ) and the MAX operator (v) of fuzzy logic play complementary roles. Complement coding uses on-cells and off-cells to represent the input pattern, and preserves individual feature amplitudes while normalizing the total on-cell/off-cell vector. Learning is stable because all adaptive weights can only decrease in time. Decreasing weights correspond to increasing sizes of category "boxes". Smaller vigilance values lead to larger category boxes. Improved prediction is achieved by training the system several times using different orderings of the input set. This voting strategy can also be used to assign probability estimates to competing predictions given small, noisy, or incomplete training sets. Four classes of simulations illustrate Fuzzy ARTMAP performance as compared to benchmark back propagation and genetic algorithm systems. These simulations include (i) finding points inside vs. outside a circle; (ii) learning to tell two spirals apart; (iii) incremental approximation of a piecewise continuous function; and (iv) a letter recognition database. The Fuzzy ARTMAP system is also compared to Salzberg's NGE system and to Simpson's FMMC system.

Reasoning with sorted-pareto dominance and other qualitative and partially ordered preferences in soft constraints

In decision making problems where we need to choose a particular decision or alternative from a set of possible choices, we often have some preferences which determine if we prefer one decision over another. When these preferences give us an ordering on the decisions that is complete, then it is easy to choose the best or one of the best decisions. However it often occurs that the preferences relation is partially ordered, and we have no best decision. In this thesis, we look at what happens when we have such a partial order over a set of decisions, in particular when we have multiple orderings on a set of decisions, and we present a framework for qualitative decision making. We look at the different natural notions of optimal decision that occur in this framework, which gives us different optimality classes, and we examine the relationships between these classes. We then look in particular at a qualitative preference relation called Sorted-Pareto Dominance, which is an extension of Pareto Dominance, and we give a semantics for this relation as one that is compatible with any order-preserving mapping of an ordinal preference scale to a numerical one. We apply Sorted-Pareto dominance to a Soft Constraints setting, where we solve problems in which the soft constraints associate qualitative preferences to decisions in a decision problem. We also examine the Sorted-Pareto dominance relation in the context of our qualitative decision making framework, looking at the relevant optimality classes for the Sorted-Pareto case, which gives us classes of decisions that are necessarily optimal, and optimal for some choice of mapping of an ordinal scale to a quantitative one. We provide some empirical analysis of Sorted-Pareto constraints problems and examine the optimality classes that result.

Simple shade plots aid better long-term choices of data pre-treatment in multivariate assemblage studies

Shade plots, simple visual representations of abundance matrices from multivariate species assemblage studies, are shown to be an effective aid in choosing an overall transformation (or other pre-treatment) of quantitative data for long-term use, striking an appropriate balance between dominant and less abundant taxa in ensuing resemblance-based multivariate analyses. Though the exposition is entirely general and applicable to all community studies, detailed illustrations of the comparative power and interpretative possibilities of shade plots are given in the case of two estuarine assemblage studies in south-western Australia: (a) macrobenthos in the upper Swan Estuary over a two-year period covering a highly significant precipitation event for the Perth area; and (b) a wide-scale spatial study of the nearshore fish fauna from five divergent estuaries. The utility of transformations of intermediate severity is again demonstrated and, with greater novelty, the potential importance seen of further mild transformation of all data after differential down-weighting (dispersion weighting) of spatially clumped' or schooled' species. Among the new techniques utilized is a two-way form of the RELATE test, which demonstrates linking of assemblage structure (fish) to continuous environmental variables (water quality), having removed a categorical factor (estuary differences). Re-orderings of sample and species axes in the associated shade plots are seen to provide transparent explanations at the species level for such continuous multivariate patterns.

Technology and the architecture of markets: re-configuring the Canadian equity market

This paper examines the relation between technical possibilities, liberal logics, and the concrete reconfiguration of markets. It focuses on the enrolling of innovations in communication and information technologies into the markets traditionally dominated by stock exchanges. With the development of capacities to trade on-screen, the power of incumbent market makers has been challenged as a less stable array of competing quasi-public and private marketplaces emerges. Developing a case study of the Toronto Stock Exchange, I argue that narrative emphasis on the performative power of sociotechnical innovations, the deterritorialisation of financial relations, and the erosion of state capacities needs qualification. A case is made for the importance of developing an understanding of: the spaces of encounter between emerging social technologies and property rights, rules of exchange, and structures of governance; and the interplay of orderings of different institutional composition and spatial reach in the reconfiguration of market architectures. Only then can a better grasp be gained of the evolving dynamics between making markets, the regulatory powers of the state, and their delimitations.

Energy levels and radiative rates for transitions in Mg-like iron, cobalt and nickel

Energy levels and radiative rates for electric dipole (E1) transitions among the lowest 141 levels of the (IS2 2s(2) 2P(6)) 3l(2) , 3l3l', and 3l4l configurations of Fe XV, Co XVI, and Ni XVII are calculated through the CIV3 code using extensive configuration-interact ion (CI) wavefunctions. The important relativistic effects are included through the Breit-Pauli approximation. In order to keep the calculated energy splittings close to the experimental values, we have made small adjustments to the diagonal elements of the Hamiltonian matrices. The energy levels, including their orderings, are in excellent agreement with the available experimental results for all three ions. However, experimental energies are only available for a few levels. Since mixing among some levels is found to be very strong, it becomes difficult to identify these uniquely. Additionally, some discrepancies with other theoretical work (particularly for Ni XVII) are very large. Therefore, in order to confirm the level ordering as well as to assess the accuracy of energy levels and radiative rates, we have performed two other independent calculations using the GRASP and FAC codes. These codes are fully relativistic, but the CI in the calculations is limited to the basic (minimum) configurations only. This enables us to assess the importance of including elaborate Cl for moderately charged ions. Additionally, we report results for electric quadrupole (E2), magnetic dipole (MI), and magnetic quadrupole (M2) transitions, and list lifetimes for all levels. Comparisons are made with other available experimental and theoretical results, and the accuracy of the present results is assessed. (c) 2007 Elsevier Inc. All rights reserved.