Given a graph G, we say that a subset D of the vertex set V is a dominating set if it is near all the vertices, in that every vertex outside of D is adjacent to a vertex in D. A domatic k-partition of G is a partition of V into k dominating sets. In this paper, we will consider issues of computability related to domatic partitions of computable graphs. Our investigation will center on answering two types of (...) questions for the case when k = 3. First, if domatic 3-partitions exist in a computable graph, how complicated can they be? Second, a decision problem: given a graph, how difficult is it to decide whether it has a domatic 3-partition? We will completely classify this decision problem for highly computable graphs, locally finite computable graphs, and computable graphs in general. Specifically, we show the decision problems for these kinds of graphs to be ${\Pi^{0}_{1}}$ -, ${\Pi^{0}_{2}}$ -, and ${\Sigma^{1}_{1}}$ -complete, respectively. (shrink)

Fried and Kollár constructed a fully faithful functor from the category of graphs to the category of fields. We give a new construction of such a functor and use it to resolve a longstanding open problem in computable model theory, by showing that for every nontrivial countable structure${\cal S}$, there exists a countable field${\cal F}$of arbitrary characteristic with the same essential computable-model-theoretic properties as${\cal S}$. Along the way, we develop a new “computable category theory”, and prove that (...) our functor and its partially defined inverse are computable functors. (shrink)

Several results about the game of cops and robbers on infinite graphs are analyzed from the perspective of computability theory. Computable robber-win graphs are constructed with the property that no computable robber strategy is a winning strategy, and such that for an arbitrary computable ordinal \, any winning strategy has complexity at least \}\). Symmetrically, computable cop-win graphs are constructed with the property that no computable cop strategy is a winning strategy. Locally finite infinite trees (...) and graphs are explored. The Turing computability of a binary relation used to classify cop-win graphs is studied, and the computational difficulty of determining the winner for locally finite computable graphs is discussed. (shrink)

We consider topological pairs,, which have computable type, which means that they have the following property: if X is a computable topological space and a topological imbedding such that and are semicomputable sets in X, then is a computable set in X. It is known, e.g., that has computable type if M is a compact manifold with boundary. In this paper we examine topological spaces called graphs and we show that we can in a natural way (...) associate to each graph G a discrete subspace E so that has computable type. Furthermore, we use this result to conclude that certain noncompact semicomputable graphs in computable metric spaces are computable. (shrink)

The scattering number and isolated scattering number of a graph have been introduced in relation to Hamiltonian properties and network vulnerability, and the isolated scattering number plays an important role in characterizing graphs with a fractional 1-factor. Here we investigate the computational complexity of one variant, namely, the weighted isolated scattering number. We give a polynomial time algorithm to compute this parameter of interval graphs, an important subclass of perfect graphs.

A function is diagonally non-computable if it diagonalizes against the universal partial computable function. D.n.c. functions play a central role in algorithmic randomness and reverse mathematics. Flood and Towsner asked for which functions h, the principle stating the existence of an h-bounded d.n.c. function implies Ramsey-type weak König’s lemma. In this paper, we prove that for every computable order h, there exists an ω\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\omega}$$\end{document} -model of h-DNR which is (...) not a not model of the Ramsey-type graph coloring principle for two colors and therefore not a model of RWKL. The proof combines bushy tree forcing and a technique introduced by Lerman, Solomon and Towsner to transform a computable non-reducibility into a separation over ω\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\omega}$$\end{document} -models. (shrink)

Let G = V G, E G be a molecular graph, where V G and E G are the sets of vertices and edges. A topological index of a molecular graph is a numerical quantity which helps to predict the chemical/physical properties of the molecules. The Wiener, Wiener polarity, and the terminal Wiener indices are the distance-based topological indices. In this paper, we described a linear time algorithm that computes the Wiener index for acyclic graphs and extended this (...) algorithm for unicyclic graphs. The same algorithms are modified to compute the terminal Wiener index and the Wiener polarity index. All these algorithms compute the indices in time O n. (shrink)

Community detection is a major issue in network analysis. This paper combines a socio-historical approach with an experimental reconstruction of programs to investigate the early automation of clique detection algorithms, which remains one of the unsolved NP-complete problems today. The research led by the archaeologist Jean-Claude Gardin from the 1950s on non-numerical information and graph analysis is retraced to demonstrate the early contributions of social sciences and humanities. The limited recognition and reception of Gardin's innovative computer application to the (...) humanities are addressed through two factors, in addition to the effects of historiography and bibliographies on the recording, discoverability, and reuse of scientific productions: (1) funding policies, evidenced by the transfer of research effort on graph applications from temporary interdisciplinary spaces to disciplinary organizations related to the then-emerging field of computer science; and (2) the erratic careers of algorithms, in which efficiency, flaws, corrections, and authors’ status, were determining factors. (shrink)

A computable graph is constructed which is not computably isomorphic to any polynomial-time graph with a standard universe . Conditions are given under which a computable graph is computably isomorphic to a polynomial-time graph with a standard universe — for example, if every vertex has finite degree. Two special types of graphs are studied. It is shown that any computable tree is recursively isomorphic to a p-time tree with standard universe and that any (...) computable equivalence relation is computably isomorphic to a p-time equivalence relation with standard universe. (shrink)

We define a model for computing probabilities of right-nested conditionals in terms of graphs representing Markov chains. This is an extension of the model for simple conditionals from Wójtowicz and Wójtowicz. The model makes it possible to give a formal yet simple description of different interpretations of right-nested conditionals and to compute their probabilities in a mathematically rigorous way. In this study we focus on the problem of the probabilities of conditionals; we do not discuss questions concerning logical and metalogical (...) issues such as setting up an axiomatic framework, inference rules, defining semantics, proving completeness, soundness etc. Our theory is motivated by the possible-worlds approach ; however, our model is generally more flexible. In the paper we focus on right-nested conditionals, discussing them in detail. The graph model makes it possible to account in a unified way for both shallow and deep interpretations of right-nested conditionals. In particular, we discuss the status of the Import-Export Principle and PCCP. We briefly discuss some methodological constraints on admissible models and analyze our model with respect to them. The study also illustrates the general problem of finding formal explications of philosophically important notions and applying mathematical methods in analyzing philosophical issues. (shrink)

The graph edit distance (GED) measures the dissimilarity between two graphs as the minimal cost of a sequence of elementary operations transforming one graph into another. This measure is fundamental in many areas such as structural pattern recognition or classification. However, exactly computing GED is NP-hard. Among different classes of heuristic algorithms that were proposed to compute approximate solutions, local search based algorithms provide the tightest upper bounds for GED. In this paper, we present K-REFINE and RANDPOST. K-REFINE (...) generalizes and improves an existing local search algorithm and performs particularly well on small graphs. RANDPOST is a general warm start framework that stochastically generates promising initial solutions to be used by any local search based GED algorithm. It is particularly efficient on large graphs. An extensive empirical evaluation demonstrates that both K-REFINE and RANDPOST perform excellently in practice. (shrink)

We performed an EEG graph analysis on data from 31 typical readers and 24 dyslexics, recorded while they were engaged in an audiovisual task and during resting-state. The task simulates reading acquisition as participants learned new letter-sound mappings via feedback. EEG data was filtered for the delta, theta, alpha, and beta bands. We computed the Phase Lag Index to provide an estimate of the functional connectivity between all pairs of electrodes per band. Then, networks were constructed using a Minimum (...) Spanning Tree, a unique sub-graph connecting all nodes without loops, aimed at minimizing bias in between groups and conditions comparisons. Both groups showed a comparable accuracy increase during task blocks, indicating that they correctly learned the new associations. The EEG results revealed lower task-specific theta connectivity, and lower theta degree correlation over both rest and task recordings, indicating less network integration in dyslexics compared to typical readers. This pattern suggests a role of theta oscillations in dyslexia and may reflect differences in task engagement between the groups, although robust correlations between MST metrics and performance indices were lacking. (shrink)

A graph-theoretic account of logics is explored based on the general notion of m-graph (that is, a graph where each edge can have a finite sequence of nodes as source). Signatures, interpretation structures and deduction systems are seen as m-graphs. After defining a category freely generated by a m-graph, formulas and expressions in general can be seen as morphisms. Moreover, derivations involving rule instantiation are also morphisms. Soundness and completeness theorems are proved. As a consequence of (...) the generality of the approach our results apply to very different logics encompassing, among others, substructural logics as well as logics with nondeterministic semantics, and subsume all logics endowed with an algebraic semantics. (shrink)

A graph-theoretic account of fibring of logics is developed, capitalizing on the interleaving characteristics of fibring at the linguistic, semantic and proof levels. Fibring of two signatures is seen as a multi-graph (m-graph) where the nodes and the m-edges include the sorts and the constructors of the signatures at hand. Fibring of two models is a multi-graph (m-graph) where the nodes and the m-edges are the values and the operations in the models, respectively. Fibring of (...) two deductive systems is an m-graph whose nodes are language expressions and the m-edges represent the inference rules of the two original systems. The sobriety of the approach is confirmed by proving that all the fibring notions are universal constructions. This graph-theoretic view is general enough to accommodate very different fibrings of propositional based logics encompassing logics with non-deterministic semantics, logics with an algebraic semantics, logics with partial semantics and substructural logics, among others. Soundness and weak completeness are proved to be preserved under very general conditions. Strong completeness is also shown to be preserved under tighter conditions. In this setting, the collapsing problem appearing in several combinations of logic systems can be avoided. (shrink)

The non-well-founded set theories described by Aczel (1988) have received attention from category theorists and computer scientists, but have been largely ignored by philosophers. At the root of this neglect might lie the impression that these theories do not embody a conception of set, but are rather of mere technical interest. This paper attempts to dispel this impression. I present a conception of set which may be taken as lying behind a non-well-founded set theory. I argue that the axiom AFA (...) is justified on the conception, which provides, contra Rieger (Mind 109:241–253, 2000), a rationale for restricting attention to the system based on this axiom. By making use of formal and informal considerations, I then make a case that most of the other axioms of this system are also justified on the conception. I conclude by commenting on the significance of the conception for the debate about the justification of the Axiom of Foundation. (shrink)

This modern, advanced textbook reviews modal logic, a field which caught the attention of computer scientists in the late 1970's.

Language experience shapes the gradual maturation of speech production in both native and second languages. Structural aspects like the connectedness of spontaneous narratives reveal this maturation progress in L1 acquisition and, as it does not rely on semantics, it could also reveal structural pattern changes during L2 acquisition. The current study tested whether L2 lexical retrieval associated with vocabulary knowledge could impact the global connectedness of narratives during the initial stages of L2 acquisition. Specifically, the study evaluated the relationship between (...) graph structure and L2 learners’ oral production in the L2 and L1. Seventy-nine college-aged students who were native speakers of English and had received classroom instruction in either L2-Spanish or L2-Chinese participated in this study. Three tasks were used: semantic fluency, phonemic fluency and picture description. Measures were operationalized as the number of words per minute in the case of the semantic and phonemic fluency tasks. Graph analysis was carried out for the picture description task using the computational tool SpeechGraphs to calculate connectedness. Results revealed significant positive correlations between connectedness in the picture description task and measures of speech production in the phonemic and semantic fluency tasks. These correlations were only significant for the participants’ L2- Spanish and Chinese. Results indicate that producing low connectedness narratives in L2 may be a marker of the initial stages of L2 oral development. These findings are consistent with the pattern reported in the early stages of L1 literacy. Future studies should further explore the interactions between graph structure and second language production proficiency, including more advanced stages of L2 learning and considering the role of cognitive abilities in this process. (shrink)

We study human performance in two classical NP‐hard optimization problems: Set Cover and Maximum Coverage. We suggest that Set Cover and Max Coverage are related to means selection problems that arise in human problem‐solving and in pursuing multiple goals: The relationship between goals and means is expressed as a bipartite graph where edges between means and goals indicate which means can be used to achieve which goals. While these problems are believed to be computationally intractable in general, they become (...) more tractable when the structure of the network resembles a tree. Thus, our main prediction is that people should perform better with goal systems that are more tree‐like. We report three behavioral experiments which confirm this prediction. Our results suggest that combinatorial parameters that are instrumental to algorithm design can also be useful for understanding when and why people struggle to choose between multiple means to achieve multiple goals. (shrink)

The graphical presentation of experimental data in the physical sciences has several advantages which today are too familiar to require very detailed enumeration. Its greatest strength lies in the clarity and succinctness with which it displays the information contained in tabulated results: for the experimenter a graph provides a rough and immediate check on the accuracy and suitability of the methods he is using, and for the reader of a scientific report it may convey in a few seconds information (...) that could only be gleaned from a table of measurements by hours of close study. There are occasions whereonlythe analysis of experimental graphs will provide the information we require, but usually the actual analysis of results is carried out nowadays by computational methods. The use of graphs is therefore not so much a necessary part of scientific procedure as an extremely useful one, and one that is often taken very much for granted. (shrink)

Cases or examples can be often explained by the interplay of arguments in favour or against their outcomes. This paper addresses the problem of finding explanations for a collection of cases where an explanation is a labelled argumentation graph consistent with the cases, and a case is represented as a statement labelling. The focus is on semi-abstract argumentation graphs specifying attack and subargument relations between arguments, along with particular complete argument labellings taken from probabilistic argumentation where arguments can be (...) excluded. The framework and computational considerations lead to an iterated local iterative deepening depth-first search to collect ‘interesting’ semi-abstract argumentation graphs consistent with a collection of statement labellings. Finally, the framework is illustrated and evaluated with a proof-of-concept implementation. (shrink)

In the current paper we consider theories with vocabulary containing a number of binary and unary relation symbols. Binary relation symbols represent labeled edges of a graph and unary relations represent unique annotations of the graph's nodes. Such theories, which we call annotation theories^ can be used in many applications, including the formalization of argumentation, approximate reasoning, semantics of logic programs, graph coloring, etc. We address a number of problems related to annotation theories over finite models, including (...) satisfiability, querying problem, specification of preferred models and model checking problem. We show that most of considered problems are NPTime- or co-NPTime-complete. In order to reduce the complexity for particular theories, we use second-order quantifier elimination. To our best knowledge none of existing methods works in the case of annotation theories. We then provide a new second-order quantifier elimination method for stratified theories, which is successful in the considered cases. The new result subsumes many other results, including those of [2, 28, 21]. (shrink)

In this paper, we propose a new concept named the uniform single valued neutrosophic graph. An illustrative example and some properties are examined. Next, we develop an algorithmic approach for computing the complement of the single valued neutrosophic graph. A numerical example is demonstrated for computing the complement of single valued neutrosophic graphs and uniform single valued neutrosophic graph.

We study the position of the computable setting in the “common theory of locality” developed in [4, 5] for local problems on $\Delta $ -regular trees, $\Delta \in \omega $. We show that such a problem admits a computable solution on every highly computable $\Delta $ -regular forest if and only if it admits a Baire measurable solution on every Borel $\Delta $ -regular forest. We also show that if such a problem admits a computable solution (...) on every computable maximum degree $\Delta $ forest then it admits a continuous solution on every maximum degree $\Delta $ Borel graph with appropriate topological hypotheses, though the converse does not hold. (shrink)

There is a Turing computable embedding $\Phi $ of directed graphs $\mathcal {A}$ in undirected graphs. Moreover, there is a fixed tuple of formulas that give a uniform effective interpretation; i.e., for all directed graphs $\mathcal {A}$, these formulas interpret $\mathcal {A}$ in $\Phi $. It follows that $\mathcal {A}$ is Medvedev reducible to $\Phi $ uniformly; i.e., $\mathcal {A}\leq _s\Phi $ with a fixed Turing operator that serves for all $\mathcal {A}$. We observe that there is a (...) class='Hi'>graph G that is not Medvedev reducible to any linear ordering. Hence, G is not effectively interpreted in any linear ordering. Similarly, there is a graph that is not interpreted in any linear ordering using computable $\Sigma _2$ formulas. Any graph can be interpreted in a linear ordering using computable $\Sigma _3$ formulas. Friedman and Stanley [4] gave a Turing computable embedding L of directed graphs in linear orderings. We show that there is no fixed tuple of $L_{\omega _1\omega }$ -formulas that, for all G, interpret the input graph G in the output linear ordering $L$. Harrison-Trainor and Montalbán [7] have also shown this, by a quite different proof. (shrink)

Despite the public availability of legal documents, there is a need for finding specific information contained in them, such as paragraphs, clauses, items and so on. With such support, users could find more specific information than only finding whole legal documents. Some research efforts have been made in this area, but there is still a lot to be done to have legal information available more easily to be found. Thus, due to the large number of published legal documents and the (...) high degree of connectivity, simple access to the document is not enough. It is necessary to recover the related legal framework for a specific need. In other words, the retrieval of the set of legal documents and their parts related to a specific subject is necessary. Therefore, in this work, we present a proposal of a RDF-based graph to represent and search parts of legal documents, as the output of a set of terms that represents the pursued legal information. Such a proposal is well-grounded on an ontological view, which makes possible to describe the general structure of a legal system and the structure of legal documents, providing this way the grounds for the implementation of the proposed RDF graph in terms of the meaning of their parts and relationships. We posed several queries to retrieve parts of legal documents related to sets of words and the results were significant. (shrink)

A graph’s entropy is a functional one, based on both the graph itself and the distribution of probability on its vertex set. In the theory of information, graph entropy has its origins. Hex-derived networks have a variety of important applications in medication store, hardware, and system administration. In this article, we discuss hex-derived network of type 1 and 2, written as HDN 1 n and HDN 2 n, respectively of order n. We also compute some degree-based entropies (...) such as Randić, ABC, and G A entropy of HDN 1 n and HDN 2 n. (shrink)

We develop a combinatorial model to study the evolution of graphs underlying proofs during the process of cut elimination. Proofs are two-dimensional objects and differences in the behavior of their cut elimination can often be accounted for by differences in their two-dimensional structure. Our purpose is to determine geometrical conditions on the graphs of proofs to explain the expansion of the size of proofs after cut elimination. We will be concerned with exponential expansion and we give upper and lower bounds (...) which depend on the geometry of the graphs. The lower bound is computed passing through the notion of universal covering for directed graphs. In this paper we present ground material for the study of cut elimination and structure of proofs in purely combinatorial terms. We develop a theory of duplication for directed graphs and derive results on graphs of proofs as corollaries. (shrink)

This chapter provides an overview of the basic research strategies and analytic techniques deployed in computational cognitive neuroscience. On the one hand, “top-down” strategies are used to infer, from formal characterizations of behavior and cognition, the computational properties of underlying neural mechanisms. On the other hand, “bottom-up” research strategies are used to identify neural mechanisms and to reconstruct their computational capacities. Both of these strategies rely on experimental techniques familiar from other branches of neuroscience, including functional magnetic resonance imaging, single-cell (...) recording, and electroencephalography. What sets computational cognitive neuroscience apart, however, is the explanatory role of analytic techniques from disciplines as varied as computer science, statistics, machine learning, and mathematical physics. These techniques serve to describe neural mechanisms computationally, but also to drive the process of scientific discovery by influencing which kinds of mechanisms are most likely to be identified. For this reason, understanding the nature and unique appeal of computational cognitive neuroscience requires not just an understanding of the basic research strategies that are involved, but also of the formal methods and tools that are being deployed, including those of probability theory, dynamical systems theory, and graph theory. (shrink)

The computer’s effect on our understanding of causation has been enormous. By the mid‐1980s, philosophical and social‐scientific work on the topic had left us with (1) no reasonable reductive account of causation and (2) a class of statistical causal models tied to linear regression. At this time, computer scientists were attacking the problem of equipping robots with models of the external that included probabilistic portrayals of uncertainty. To solve the problem of efficiently storing such knowledge, they introduced Bayes Networks and (...) directed graphs. By attaching a causal interpretation to Bayes Networks, the philosophy of causation changed dramatically. We are now able to be extremely general about how causal structure connects to data, and systematic about when causal structures are empirically indistinguishable. In this essay I try to motivate and describe this synthesis. (shrink)

We investigate the definability in monadic ∑11 and monadic Π11 of the problems REGk, of whether there is a regular subgraph of degree k in some given graph, and XREGk, of whether, for a given rooted graph, there is a regular subgraph of degree k in which the root has degree k, and their restrictions to graphs in which every vertex has degree at most k, namely REGkk and XREGkk, respectively, for k ≥ 2 . Our motivation partly (...) stems from the fact that REGkk and XREGkk are logspace equivalent to CONN and REACH, respectively, for k ≥ 3, where CONN is the problem of whether a given graph is connected and REACH is the problem of whether a given graph has a path joining two given vertices. We use monadic first - order reductions, monadic ∑11 games and a recent technique due to Fagin, Stockmeyer and Vardi to almost completely classify whether these problems are definable in monadic ∑11 and monadic Π11, and we compare the definability of these problems. (shrink)

In graph theory, the concept of domination is essential in a variety of domains. It has broad applications in diverse fields such as coding theory, computer net work models, and school bus routing and facility lo cation problems. If a fuzzy graph fails to obtain acceptable results, neutrosophic sets and neutrosophic graphs can be used to model uncertainty correlated with indeterminate and inconsistent information in arbitrary real-world scenario. In this study, we consider the concept of domination as it (...) relates to single-valued neutrosophic incidence graphs (SVNIGs). Given the importance of domination and its utilization in numerous fields, we propose the application of dominating sets in SVNIG with valid edges. We present some relevant definitions such as those of valid edges, cardinality, and isolated vertices in SVNIG along with some examples. Furthermore, we also show a few significant sets connected to the dominating set in an SVNIG such as independent and irredundant sets. We also investigate a relationship between the concepts of dominating sets and domination numbers as well as irredundant and independence sets in SVNIGs. Finally, a real-life deployment of domination in SVNIGsis investigated in relation to COVID-19 vaccination locations as a practical application. (shrink)

Molecular models are typical topics of chemical research depending on the technical standards of observation, computation, and representation. Mathematically, molecular structures have been represented by means of graph theory, topology, differential equations, and numerical procedures. With the increasing capabilities of computer networks, computational models and computer-assisted visualization become an essential part of chemical research. Object-oriented programming languages create a virtual reality of chemical structures opening new avenues of exploration and collaboration in chemistry. From an epistemic point of view, virtual (...) reality is a new computer-assisted tool of human imagination and recognition. (shrink)

For [Formula: see text], the coarse similarity class of [Formula: see text], denoted by [Formula: see text], is the set of all [Formula: see text] such that the symmetric difference of [Formula: see text] and [Formula: see text] has asymptotic density [Formula: see text]. There is a natural metric [Formula: see text] on the space [Formula: see text] of coarse similarity classes defined by letting [Formula: see text] be the upper density of the symmetric difference of [Formula: see text] and (...) [Formula: see text]. We study the metric space of coarse similarity classes under this metric, and show in particular that between any two distinct points in this space there are continuum many geodesic paths. We also study subspaces of the form [Formula: see text] where [Formula: see text] is closed under Turing equivalence, and show that there is a tight connection between topological properties of such a space and computability-theoretic properties of [Formula: see text]. We then define a distance between Turing degrees based on Hausdorff distance in the metric space [Formula: see text]. We adapt a proof of Monin to show that the Hausdorff distances between Turing degrees that occur are exactly [Formula: see text], [Formula: see text], and [Formula: see text], and study which of these values occur most frequently in the senses of Lebesgue measure and Baire category. We define a degree [Formula: see text] to be attractive if the class of all degrees at distance [Formula: see text] from [Formula: see text] has measure [Formula: see text], and dispersive otherwise. In particular, we study the distribution of attractive and dispersive degrees. We also study some properties of the metric space of Turing degrees under this Hausdorff distance, in particular the question of which countable metric spaces are isometrically embeddable in it, giving a graph-theoretic sufficient condition for embeddability. Motivated by a couple of issues arising in the above work, we also study the computability-theoretic and reverse-mathematical aspects of a Ramsey-theoretic theorem due to Mycielski, which in particular implies that there is a perfect set whose elements are mutually [Formula: see text]-random, as well as a perfect set whose elements are mutually [Formula: see text]-generic. Finally, we study the completeness of [Formula: see text] from the perspectives of computability theory and reverse mathematics. (shrink)

Many collective decision making problems have a combinatorial structure: the agents involved must decide on multiple issues and their preferences over one issue may depend on the choices adopted for some of the others. Voting is an attractive method for making collective decisions, but conducting a multi-issue election is challenging. On the one hand, requiring agents to vote by expressing their preferences over all combinations of issues is computationally infeasible; on the other, decomposing the problem into several elections on smaller (...) sets of issues can lead to paradoxical outcomes. Any pragmatic method for running a multi-issue election will have to balance these two concerns. We identify and analyse the problem of generating an agenda for a given election, specifying which issues to vote on together in local elections and in which order to schedule those local elections. (shrink)

This paper investigates the mechanisms a program may use to learn conceptual structures that represent natural language meaning. A computer program named Moran is described that infers conceptual structures from pictorial input data. Moran is presented with “snapshots” of an environment and an English sentence describing the action that takes place between the snapshots. The learning task is to associate each root verb with a conceptual structure that represents the types of objects that participate in the action and the changes (...) the objects undergo during the action. Four learning mechanisms are shown to be adequate to accomplish this learning task. The learning mechanisms are described along with the conditions under which each is invoked and the effect each has on existing memory structures. The conceptual structure Moran inferred for one root verb is shown. (shrink)