We introduce a framework for a graph-theoretic analysis of the semantic paradoxes. Similar frameworks have been recently developed for infinitary propositional languages by Cook and Rabern, Rabern, and Macauley. Our focus, however, will be on the language of first-order arithmetic augmented with a primitive truth predicate. Using Leitgeb’s notion of semantic dependence, we assign reference graphs (rfgs) to the sentences of this language and define a notion of paradoxicality in terms of acceptable decorations of rfgs with truth values. It (...) is shown that this notion of paradoxicality coincides with that of Kripke. In order to track down the structural components of an rfg that are responsible for paradoxicality, we show that any decoration can be obtained in a three-stage process: first, the rfg is unfolded into a tree, second, the tree is decorated with truth values (yielding a dependence tree in the sense of Yablo), and third, the decorated tree is re-collapsed onto the rfg. We show that paradoxicality enters the picture only at stage three. Due to this we can isolate two basic patterns necessary for paradoxicality. Moreover, we conjecture a solution to the characterization problem for dangerous rfgs that amounts to the claim that basically the Liar- and the Yablo graph are the only paradoxical rfgs. Furthermore, we develop signed rfgs that allow us to distinguish between ‘positive’ and ‘negative’ reference and obtain more fine-grained versions of our results for unsigned rfgs. (shrink)

Modeling mechanisms is central to the biological sciences – for purposes of explanation, prediction, extrapolation, and manipulation. A closer look at the philosophical literature reveals that mechanisms are predominantly modeled in a purely qualitative way. That is, mechanistic models are conceived of as representing how certain entities and activities are spatially and temporally organized so that they bring about the behavior of the mechanism in question. Although this adequately characterizes how mechanisms are represented in biology textbooks, contemporary biological research practice (...) shows the need for quantitative, probabilistic models of mechanisms, too. In this paper we argue that the formal framework of causal graph theory is well-suited to provide us with models of biological mechanisms that incorporate quantitative and probabilistic information. On the ba-sis of an example from contemporary biological practice, namely feedback regulation of fatty acid biosynthesis in Brassica napus, we show that causal graph theoretical models can account for feedback as well as for the multi-level character of mechanisms. However, we do not claim that causal graph theoretical representations of mechanisms are advantageous in all respects and should replace common qualitative models. Rather, we endorse the more balanced view that causal graph theoretical models of mechanisms are useful for some purposes, while being insufficient for others. (shrink)

I argue that Frege Problems in thought are best modeled using graph-theoretic machinery; and that these problems can arise even when subjects associate all the same qualitative properties to the object they’re thinking of twice. I compare the proposed treatment to similar ideas by Heck, Ninan, Recanati, Kamp and Asher, Fodor, and others.

The study of graph structure has advanced in recent years with great strides: finite graphs can be described algebraically, enabling them to be constructed out of more basic elements. Separately the properties of graphs can be studied in a logical language called monadic second-order logic. In this book, these two features of graph structure are brought together for the first time in a presentation that unifies and synthesizes research over the last 25 years. The author not only provides (...) a thorough description of the theory, but also details its applications, on the one hand to the construction of graph algorithms, and, on the other to the extension of formal language theory to finite graphs. Consequently the book will be of interest to graduate students and researchers in graph theory, finite model theory, formal language theory, and complexity theory. (shrink)

The paper is concerned with the existence of a universal graph at the successor of a strong limit singular μ of cofinality ℵ0. Starting from the assumption of the existence of a supercompact cardinal, a model is built in which for some such μ there are $\mu^{++}$ graphs on μ+ that taken jointly are universal for the graphs on μ+, while $2^{\mu^+} \gg \mu^{++}$ . The paper also addresses the general problem of obtaining a framework for consistency results (...) at the successor of a singular strong limit starting from the assumption that a supercompact cardinal κ exists. The result on the existence of universal graphs is obtained as a specific application of a more general method. (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)

In this paper, we analyze and discuss Schopenhauer’s n-term diagrams for eristic dialectics from a graph-theoretical perspective. Unlike logic, eristic dialectics does not examine the validity of an isolated argument, but the progression and persuasiveness of an argument in the context of a dialogue or even controversy. To represent these dialogue situations, Schopenhauer created large maps with concepts and Euler-type diagrams, which from today’s perspective are a specific form of graphs. We first present the original method with Euler-type diagrams, (...) then give the most important graph-theoretical definitions, then discuss Schopenhauer’s diagrams graph-theoretically and finally give an example of how the graphs or diagrams can be used to analyze dialogues. (shrink)

Can you find an xy-equation that, when graphed, writes itself on the plane? This idea became internet-famous when a Wikipedia article on Tupper’s self-referential formula went viral in 2012. Under scrutiny, the question has two flaws: it is meaningless (it depends on fonts) and it is trivial. We fix these flaws by formalizing the problem.

Peirce considered the principal business of logic to be the analysis of reasoning. He argued that the diagrammatic system of Existential Graphs, which he had invented in 1896, carries the logical analysis of reasoning to the furthest point possible. The present paper investigates the analytic virtues of the Alpha part of the system, which corresponds to the sentential calculus. We examine Peirce’s proposal that the relation of illation is the primitive relation of logic and defend the view that this (...) idea constitutes the fundamental motive of philosophy of notation both in algebraic and graphical logic. We explain how in his algebras and graphs Peirce arrived at a unifying notation for logical constants that represent both truth-function and scope. Finally, we show that Shin’s argument for multiple readings of Alpha graphs is circular. (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)

We describe Peirce’s 1903 system of modal gamma graphs, its transformation rules of inference, and the interpretation of the broken-cut modal operator. We show that Peirce proposed the normality rule in his gamma system. We then show how various normal modal logics arise from Peirce’s assumptions concerning the broken-cut notation. By developing an algebraic semantics we establish the completeness of fifteen modal logics of gamma graphs. We show that, besides logical necessity and possibility, Peirce proposed an epistemic interpretation (...) of the broken-cut modality, and that he was led to analyze constructions of knowledge in the style of epistemic logic. (shrink)

The problem of when a recursive graph has a recursive k-coloring has been extensively studied by Bean, Schmerl, Kierstead, Remmel, and others. In this paper, we study the polynomial time analogue of that problem. We develop a number of negative and positive results about colorings of polynomial time graphs. For example, we show that for any recursive graph G and for any k, there is a polynomial time graph G′ whose vertex set is {0,1}* such that there is an (...) effective degree preserving correspondence between the set of k-colorings of G and the set of k-colorings of G′ and hence there are many examples of k-colorable polynomial time graphs with no recursive k-colorings. Moreover, even though every connected 2-colorable recursive graph is recursively 2-colorable, there are connected 2-colorable polynomial time graphs which have no primitive recursive 2-coloring. We also give some sufficient conditions which will guarantee that a polynomial time graph has a polynomial time or exponential time coloring. (shrink)

We show that there exist 2 ℵ 0 equational classes of Boolean algebras with operators that are not generated by the complex algebras of any first-order definable class of relational structures. Using a variant of this construction, we resolve a long-standing question of Fine, by exhibiting a bimodal logic that is valid in its canonical frames, but is not sound and complete for any first-order definable class of Kripke frames (a monomodal example can then be obtained using simulation results of (...) Thomason). The constructions use the result of Erd $\H{o}$ s that there are finite graphs with arbitrarily large chromatic number and girth. (shrink)

This paper introduces a class of graphical independence models that is closed under marginalization and conditioning but that contains all DAG independence models. This class of graphs, called maximal ancestral graphs, has two attractive features: there is at most one edge between each pair of vertices; every missing edge corresponds to an independence relation. These features lead to a simple parameterization of the corresponding set of distributions in the Gaussian case.

We argue that C. Darwin and more recently W. Hennig worked at times under the simplifying assumption of an eternal biosphere. So motivated, we explicitly consider the consequences which follow mathematically from this assumption, and the infinite graphs it leads to. This assumption admits certain clusters of organisms which have some ideal theoretical properties of species, shining some light onto the species problem. We prove a dualization of a law of T.A. Knight and C. Darwin, and sketch a decomposition (...) result involving the internodons of D. Kornet, J. Metz and H. Schellinx. A further goal of this paper is to respond to B. Sturmfels’ question, “Can biology lead to new theorems?”. (shrink)

It is a widespread assumption in philosophy of science that data is what is explained by theory—that data itself is not explanatory. I draw on instances of representational and explanatory practice from mammalian chronobiology to suggest that this assumption is unsustainable. In many instances, biologists employ representations of data in explanatory ways that are not reducible to constraints on or evidence for representations of mechanisms. Data graphs are used to exemplify relationships between quantities in the mechanism, and often these (...) representations are necessary for explaining particular aspects of the phenomena under study. I argue that this kind of representation is distinct from representing laws or generalizations, and its primary purpose is to convey particular types or patterns of quantitative relationships. The benefit of the analysis is two-fold. First, it provides a more accurate account of explanatory practice in broadly mechanistic analysis in biology. Second, it suggests that there is not an explanatory “fundamental” type of representation in biology. Rather, the practice of explanation consists in the construction of different types of representations and their employment for distinct explanatory purposes. (shrink)

The mathematical field of graph theory has recently been used to provide counterexamples to the Principle of the Identity of Indiscernibles. In response to this, it has been argued that appeal to relations between graphs allows the Principle to survive the counterexamples. In this paper, I aim to show why that proposal does not succeed.

Peirce and Frege both distinguished between the propositional content of an assertion and the assertion of a propositional content, but with different notational means. We present a modification of Peirce’s graphical method of logic that can be used to reason about assertions in a manner similar to Peirce’s original method. We propose a new system of Assertive Graphs, which unlike the tradition that follows Frege involves no ad hoc sign of assertion. We show that axioms of intuitionistic logic can (...) be derived from AGs, and argue that AGs analyse and represent assertions and illocutionary content in a way which is motivated both by its logical properties and its historical connection with the ideas that led to the development of the graphical method. (shrink)

This paper examines the contemporary philosophical and cognitive relevance of Charles Peirce's diagrammatic logic of existential graphs (EGs), the ‘moving pictures of thought’. The first part brings to the fore some hitherto unknown details about the reception of EGs in the early 1900s that took place amidst the emergence of modern conceptions of symbolic logic. In the second part, philosophical aspects of EGs and their contributions to contemporary logical theory are pointed out, including the relationship between iconic logic and (...) images, the problem of the meaning of logical constants, the cognitive economy of iconic logic, the failure of the Frege–Russell thesis, and the failure of the Language of Thought hypothesis. (shrink)

We examine possible causal structures of experiments with entangled quantum objects. Previously, these structures have been obscured by assuming a misleading probabilistic analysis of quantum non locality as 'Outcome Dependence or Parameter Dependence' and by directly associating these correlations with influences. Here we try to overcome these shortcomings: we proceed from a recent stronger Bell argument, which provides an appropriate probabilistic description, and apply the rigorous methods of causal graph theory. Against the standard view that there is only an influence (...) between the measurement outcomes, we show that there must be an influence from one setting to its distant outcome: EPR correlations can only come about if one of the outcomes is a common effect of both settings. Our discussion makes explicit under which assumptions similar conclusions from information theoretic considerations can be interpreted causally. (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)

We investigate dependence of recursively enumerable graphs on the equality relation given by a specific r.e. equivalence relation on ω. In particular we compare r.e. equivalence relations in terms of graphs they permit to represent. This defines partially ordered sets that depend on classes of graphs under consideration. We investigate some algebraic properties of these partially ordered sets. For instance, we show that some of these partial ordered sets possess atoms, minimal and maximal elements. We also fully (...) describe the isomorphism types of some of these partial orders. (shrink)

Graphs are employed to define a variety of distance-based binary merging operators. We provide logical characterization results for each class of merging operators introduced and discuss the extension of this approach to the merging of sequences and multisets.

Improving a theorem of Gasarch and Hirst, we prove that if 2 ≤ k ≤ m < ω, then the following is equivalent to WKL0 over RCA0 Every locally k-colorable graph is m-colorable.

Nicholas Shackel (2011) has proposed a number of arguments to save the Dipert–Bird model of physical reality from the sorts of unpalatable consequence I identified in Oderberg 2011. Some consequences, he thinks, are only apparent; others are real but palatable. In neither case does he seem to me to have deflected the concerns I raised, leaving graph structuralism on Dipert–Bird lines as problematic as ever.

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)

It is shown that if ZF is consistent, then so is ZFC + GCH + "There is a graph with cardinality ℵ 2 and chromatic number ℵ 2 such that every subgraph of cardinality ≤ ℵ 1 has chromatic number ≤ ℵ 0 ". This partially answers a question of Erdos and Hajnal.

Studies to neutrosophic graphs happens to be not only innovative and interesting, but gives a new dimension to graph theory. The classic coloring of edge problem happens to give various results. Neutrosophic tree will certainly find lots of applications in data mining when certain levels of indeterminacy is involved in the problem. Several open problems are suggested.

Multi-Task Learning tries to improve the learning process of different tasks by solving them simultaneously. A popular Multi-Task Learning formulation for SVM is to combine common and task-specific parts. Other approaches rely on using a Graph Laplacian regularizer. Here we propose a combination of these two approaches that can be applied to L1, L2 and LS-SVMs. We also propose an algorithm to iteratively learn the graph adjacency matrix used in the Laplacian regularization. We test our proposal with synthetic and real (...) problems, both in regression and classification settings. When the task structure is present, we show that our model is able to detect it, which leads to better results, and we also show it to be competitive even when this structure is not present. (shrink)

We present a novel method, called graph sparse nonnegative matrix factorization, for dimensionality reduction. The affinity graph and sparse constraint are further taken into consideration in nonnegative matrix factorization and it is shown that the proposed matrix factorization method can respect the intrinsic graph structure and provide the sparse representation. Different from some existing traditional methods, the inertial neural network was developed, which can be used to optimize our proposed matrix factorization problem. By adopting one parameter in the neural network, (...) the global optimal solution can be searched. Finally, simulations on numerical examples and clustering in real-world data illustrate the effectiveness and performance of the proposed method. (shrink)

The semantic paradoxes are often associated with self-reference or referential circularity. Yablo (Analysis 53(4):251–252, 1993), however, has shown that there are infinitary versions of the paradoxes that do not involve this form of circularity. It remains an open question what relations of reference between collections of sentences afford the structure necessary for paradoxicality. In this essay, we lay the groundwork for a general investigation into the nature of reference structures that support the semantic paradoxes and the semantic hypodoxes. We develop (...) a functionally complete infinitary propositional language endowed with a denotation assignment and extract the reference structural information in terms of graph-theoretic properties. We introduce the new concepts of dangerous and precarious reference graphs, which allows us to rigorously define the task: classify the dangerous and precarious directed graphs purely in terms of their graph-theoretic properties. Ungroundedness will be shown to fully characterize the precarious reference graphs and fully characterize the dangerous finite graphs. We prove that an undirected graph has a dangerous orientation if and only if it contains a cycle, providing some support for the traditional idea that cyclic structure is required for paradoxicality. This leaves the task of classifying danger for infinite acyclic reference graphs. We provide some compactness results, which give further necessary conditions on danger in infinite graphs, which in conjunction with a notion of self-containment allows us to prove that dangerous acyclic graphs must have infinitely many vertices with infinite out-degree. But a full characterization of danger remains an open question. In the appendices we relate our results to the results given in Cook (J Symb Log 69(3):767–774, 2004) and Yablo (2006) with respect to more restricted sentences systems, which we call $\mathcal{F}$ -systems. (shrink)

The focus of this article is the view about fundamental natural properties known as dispositional monism. This is a holistic view about nature, according to which all properties are essentially interrelated. The general question to be addressed concerns what kinds of features relational structures of properties should be thought to have. I use Bird's graph-theoretic framework for representing dispositional structures as a starting point, before arguing that it is inadequate in certain important respects. I then propose a more parsimonious graph-theoretic (...) system, which, among other things, overhauls Bird's distinction between stimulus and manifestation relations. (shrink)

We compared the ability of three different contextual models of lexical semantic memory and of a simple associative model to predict the properties of semantic networks derived from word association norms. None of the semantic models were able to accurately predict all of the network properties. All three contextual models over-predicted clustering in the norms, whereas the associative model under-predicted clustering. Only a hybrid model that assumed that some of the responses were based on a contextual model and others on (...) an associative network successfully predicted all of the network properties and predicted a word's top five associates as well as or better than the better of the two constituent models. The results suggest that participants switch between a contextual representation and an associative network when generating free associations. We discuss the role that each of these representations may play in lexical semantic memory. Concordant with recent multicomponent theories of semantic memory, the associative network may encode coordinate relations between concepts, and contextual representations may be used to process information about more abstract concepts. (shrink)

May the same graph admit two different chromatic numbers in two different universes? How about infinitely many different values? and can this be achieved without changing the cardinals structure? In this paper, it is proved that in Gödel’s constructible universe, for every uncountable cardinal \ below the first fixed-point of the \-function, there exists a graph \ satisfying the following:\ has size and chromatic number \;for every infinite cardinal \, there exists a cofinality-preserving \-preserving forcing extension in which \=\kappa \).

From my ongoing "Metalogical Plato" project. The aim of the diagram is to make reasonably intuitive how the Socratic elenchos (the logic of refutation applied to candidate formulations of virtues or ruling knowledges) looks and works as a whole structure. This is my starting point in the project, in part because of its great familiarity and arguable claim to being the inauguration of western philosophy; getting this point less wrong would have broad and deep consequences, including for philosophy’s self-understanding. -/- (...) (i.) is the first pass at elenchos in which the Socratic interlocutor does not reflect on knowledge being the crux of the problem. (ii.) is the second, rarer, reflective pass in which they are, making the investigation explicitly about knowledge. Its centrality in the Charmides makes that neglected dialogue of superlative importance. This structure is also the gateway through which the discussion/dialectic crosses into the Agathology (discussion of the form of the good) at Republic 505. -/- The problem of elenchos, then, grasped as a whole structure, is that it seems that knowledge can neither satisfactorily be included in nor excluded from its own scope. The development of the ti esti (“what is ---?”) question leads to the introduction of knowledge into its own scope (i. implicitly, as goodness contrasted with blind rule-following ii. explicitly qua knowledge) while the development of the dual peri tinos (“----about what?) question leads to K’s elimination from its own scope. The introductions are motivated to avoid contradiction, but produce regress; the eliminations are motivated to avoid regress, but produce contradiction. In scholarship, and in the history of philosophy, the ti esti question is universally recognized, to the point of being identified with philosophy’s origin and essence; the peri tinos question is neglected textually and never recognized as the equal dual to the ti esti. This, I claim, has blocked the development of a nontrivial logical appreciation of what Plato's Socrates is up to. (One rather disastrous effect of this neglect is taking Aristotle as the beginning of the development of logic, rather than, correctly, for the beginning of logic’s fatal separation from mathematics and dialectic.) -/- Further, because of this monopticism of the ti esti, the function of consistency in the elenchos has not been understood, even with respect to the ti esti. The ti esti is actually in search of completeness, given a norm of consistency; the peri tinos is in search of consistency, given a norm of completeness. Only appreciating the two questions as dual allows space in the structure to clarify these different orientations relative to consistency. (And, dually, to completeness, whose function in the elenchos is generally entirely missed by scholars and relegated to discussions of eros; it's not out of place there, of course, but its significance is secured here.) Recognizing the duality of the ti esti and peri tinos questions is thus the royal road, in the Socratic-Platonic context, to catching sight of what we post-Cantorians can recognize as the metalogical duality of consistency and completeness. (The salutary disruptive effects of this Plato-Cantor proximity have, of course, been traced in complementary ways by Badiou.) -/- Note that the diagram is supposed to provide a relatively accessible orientation, not to stand on its own, and certainly not to be the last word on any subject. An important qualification (telegraphed in the previous paragraph) is that what elenchos shows is not finally circular or paradoxical, though the problem first presents as such (stubbornly, obdurately, as "difficult" Plato's Socrates always says with characteristic understatement). What is depicted here is meant, at a first pass, to be the shape of that first presentation, the form of the problem of elenchos, rather than of its solution. It's not an accident that this problem strongly resembles "Russell's paradox" (not Russell's not a paradox.) Problem is to solution as RP is to the diagonal theorems. (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 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)

In this book, the authors systematically define the new notion of linguistic graphs associated with a linguistic set of a linguistic variable. We can also define the notion of directed linguistic graphs and linguistic-weighted graphs. Chapter two discusses all types of linguistic graphs, linguistic dyads, linguistic triads, linguistic wheels, complete linguistic graphs, linguistic connected graphs, disconnected linguistic graphs, linguistic components of the graphs and so on. Further, we define the notion of linguistic (...) subgraphs of a linguistic graph. However, like usual graphs, we will not be able to arbitrarily connect any two linguistic words of a linguistic set associated with a linguistic variable. They can be related or adjacent depending on the linguistic variable associated with the linguistic set. This is an exceptional feature of a linguistic graph. (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)

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)

This paper deals primarily with countable, simple, connected graphs and the following two conditions which are trivially satisfied if the graphs are finite: (a) there is an edge-recognition algorithm, i.e., an effective procedure which enables us, given two distinct vertices, to decide whether they are adjacent, (b) there is a shortest path algorithm, i.e., an effective procedure which enables us, given two distinct vertices, to find a minimal path joining them. A graph $G = \langle\eta, \eta\rangle$ with η (...) as set of vertices and η as set of edges is an α-graph if it satisfies (a); it is an ω-graph if it satisfies (b). G is called r.e. (isolic) if the sets ν and η are r.e. (isolated). While every ω-graph is an α-graph, the converse is false, even if G is r.e. or isolic. Several basic properties of finite graphs do not generalize to ω-graphs. For example, an ω-tree with more than one vertex need not have two pendant vertices, but may have only one or none, since it may be a 1-way or 2-way infinite path. Nevertheless, some elementary propositions for finite graphs $G = \langle\nu, \eta\rangle$ with $n = \operatorname{card}(\nu), e = \operatorname{card}(\eta)$ , do generalize to isolic ω-graphs, e.g., n - 1 ≤ e ≤ n(n - 1)/2. Let N and E be the recursive equivalence types of ν and η respectively. Then we have for an isolic α-tree $G = \langle\nu, \eta\rangle: N = E + 1$ iff G is an ω-tree. The theorem that every finite graph has a spanning tree has a natural, effective analogue for ω-graphs. The structural difference between isolic α-graphs and isolic ω-graphs will be illustrated by: (i) every infinite graph is isomorphic to some isolic α-graph; (ii) there is an infinite graph which is not isomorphic to any isolic ω-graph. An isolic α-graph is also called a twilight graph. There are c such graphs, c denoting the cardinality of the continuum. (shrink)

Coreference resolution is a challenging natural language processing task, and it is difficult to identify the correct mentions of an entity that can be any noun or noun phrase. In this article, a semisupervised, two-stage pattern-based bootstrapping approach is proposed for the coreference resolution task. During Stage 1, the possible mentions are identified using word-based features, and during Stage 2, the correct mentions are identified by filtering the non-coreferents of an entity using statistical measures and graph-based features. Whereas the existing (...) approaches use morphosyntactic and number/gender agreement features, the proposed approach uses semantic graph-based context-level semantics and nested noun phrases in the correct mentions identification. Moreover, mentions without the number/gender information are identified, using the context-based features of the semantic graph. The evaluation performed for the coreference resolution shows significant improvements, when compared with the word association-based bootstrapping systems. (shrink)

This experiment investigated the effect of format (line vs. bar), viewers’ familiarity with variables, and viewers’ graphicacy (graphical literacy) skills on the comprehension of multivariate (three variable) data presented in graphs. Fifty-five undergraduates provided written descriptions of data for a set of 14 line or bar graphs, half of which depicted variables familiar to the population and half of which depicted variables unfamiliar to the population. Participants then took a test of graphicacy skills. As predicted, the format influenced (...) viewers’ interpretations of data. Specifically, viewers were more likely to describe x–y interactions when viewing line graphs than when viewing bar graphs, and they were more likely to describe main effects and “z–y” (the variable in the legend) interactions when viewing bar graphs than when viewing line graphs. Familiarity of data presented and individuals’ graphicacy skills interacted with the influence of graph format. Specifically, viewers were most likely to generate inferences only when they had high graphicacy skills, the data were familiar and thus the information inferred was expected, and the format supported those inferences. Implications for multivariate data display are discussed. (shrink)