Traditional spatial enabled grammars lack flexibility in specifying the spatial semantics of graphs. This paper describes a new graph grammar formalism called the multigranularity Coordinate Graph Grammar (mgCGG) for spatial graphs. Based on the Coordinate Graph Grammar (CGG), the mgCGG divides coordinates into two categories, physical coordinates and grammatical coordinates, where physical coordinates are the common coordinates in the real world, and grammatical coordinates describe the restrictions on the spatial semantics. In the derivation and reduction of (...) the mgCGG, the spatial matching conditions between nodes are evaluated on the basis of the grammatical coordinates, which can be obtained by the specified granularities. By adjusting the granularities, both qualitative and quantitative analyses for spatial semantics can be obtained, including the transition states between them. In addition, a new redex searching algorithm with polynomial time complexity is designed for the mgCGG. A running example of drawing a flowchart is given to illustrate a practical application of the mgCGG. Through a detailed comparison with related spatial-enabled grammars, it is found that the mgCGG has good performance in four critical aspects—the semantics processing mechanism, fault-tolerance, redex searching algorithm, and practical application—providing a flexible yet uniform way to specify spatial graphs and building a bridge between nonspatial and spatial grammars. (shrink)

In this paper a logical interpretation of semantic nets and graph grammars is proposed for modelling natural language understanding and creating language understanding computer systems. An example of parsing a Finnish question by graph grammars and inferring the answer to it by a semantic net representation is provided.

Using the programming-language concept of continuations, we propose a new, multimodal analysis of quantification in Type Logical Grammar. Our approach provides a geometric view of in-situ quantification in terms of graphs, and motivates the limited use of empty antecedents in derivations. Just as continuations are the tool of choice for reasoning about evaluation order and side effects in programming languages, our system provides a principled, type-logical way to model evaluation order and side effects in natural language. We illustrate with an (...) improved account of quantificational binding, weak crossover, wh-questions, superiority, and polarity licensing. (shrink)

We introduce a set of biologically and computationally motivated design choices for modeling the learning of language, or of other types of sequential, hierarchically structured experience and behavior, and describe an implemented system that conforms to these choices and is capable of unsupervised learning from raw natural-language corpora. Given a stream of linguistic input, our model incrementally learns a grammar that captures its statistical patterns, which can then be used to parse or generate new data. The grammar constructed in this (...) manner takes the form of a directed weighted graph, whose nodes are recursively (hierarchically) defined patterns over the elements of the input stream. We evaluated the model in seventeen experiments, grouped into five studies, which examined, respectively, (a) the generative ability of grammar learned from a corpus of natural language, (b) the characteristics of the learned representation, (c) sequence segmentation and chunking, (d) artificial grammar learning, and (e) certain types of structure dependence. The model's performance largely vindicates our design choices, suggesting that progress in modeling language acquisition can be made on a broad front—ranging from issues of generativity to the replication of human experimental findings—by bringing biological and computational considerations, as well as lessons from prior efforts, to bear on the modeling approach. (shrink)

Second-order abstract categorial grammars (de Groote in Association for computational linguistics, 39th annual meeting and 10th conference of the European chapter, proceedings of the conference, pp. 148–155, 2001) and hyperedge replacement grammars (Bauderon and Courcelle in Math Syst Theory 20:83–127, 1987; Habel and Kreowski in STACS 87: 4th Annual symposium on theoretical aspects of computer science. Lecture notes in computer science, vol 247, Springer, Berlin, pp 207–219, 1987) are two natural ways of generalizing “context-free” grammar formalisms for string (...) and tree languages. It is known that the string generating power of both formalisms is equivalent to (non-erasing) multiple context-free grammars (Seki et al. in Theor Comput Sci 88:191–229, 1991) or linear context-free rewriting systems (Weir in Characterizing mildly context-sensitive grammar formalisms, University of Pennsylvania, 1988). In this paper, we give a simple, direct proof of the fact that second-order ACGs are simulated by hyperedge replacement grammars, which implies that the string and tree generating power of the former is included in that of the latter. The normal form for tree-generating hyperedge replacement grammars given by Engelfriet and Maneth (Graph transformation. Lecture notes in computer science, vol 1764. Springer, Berlin, pp 15–29, 2000) can then be used to show that the tree generating power of second-order ACGs is exactly the same as that of hyperedge replacement grammars. (shrink)

We introduce _Interleave-Disjunction-Lock parallel multiple context-free grammars_ (IDL-PMCFG), a novel grammar formalism designed to describe the syntax of free word order languages that allow for extensive interleaving of grammatical constituents. Though interleaved constituents, and especially the so-called hyperbaton, are common in several ancient (Classical Latin and Greek, Sanskrit...) and modern (Hungarian, Finnish...) languages, these syntactic structures are often difficult to express in existing formalisms. The IDL-PMCFG formalism combines Seki et al.’s parallel multiple context-free grammars (PMCFG) with Nederhof and Satta’s (...) IDL expressions. We define the semantics of IDL-PMCFGs and study their expressivity, proving that IDL-PMCFG extends both PMCFG and IDL-CFG (context-free grammars equipped with IDL expressions) and that IDL-PMCFG parsing is $\mathrm {NP}$ -hard. We then introduce COMPĀ, a programming language extending Ranta’s Grammatical Framework (GF) and built as a high-level front-end formalism to IDL-PMCFG for practical grammar development. We present a parsing algorithm for IDL-PMCFG inspired by earlier Earley-style PMCFG parsing algorithms and Nederhof and Satta’s IDL graphs and give a worst-case estimate of its complexity as a function of several metrics on IDL expressions, the size of the input and a new notion of the _G_-density of a language. (shrink)

Contemporary generative grammar assumes that syntactic structure is best described in terms of sets, and that locality conditions, as well as cross-linguistic variation, is determined at the level of designated functional heads. Syntactic operations (merge, MERGE, etc.) build a structure by deriving sets from lexical atoms and recursively (and monotonically) yielding sets of sets. Additional restrictions over the format of structural descriptions limit the number of elements involved in each operation to two at each derivational step, a head and a (...) non-head. In this paper, we will explore an alternative direction for minimalist inquiry based on previous work, e.g., Frank (2002, 2006), albeit under novel assumptions. We propose a view of syntactic structure as a specification of relations in graphs, which correspond to the extended projection of lexical heads; these are _elementary trees_ in Tree Adjoining Grammars. We present empirical motivation for a lexicalised approach to structure building, where the units of the grammar are elementary trees. Our proposal will be based on cross-linguistic evidence; we will consider the structure of elementary trees in Spanish, English and German. We will also explore the consequences of assuming that nodes in elementary trees are addresses for purposes of tree composition operations, substitution and adjunction. (shrink)

The Syllabus for Certain Topics of Logic is a long treatise that Peirce wrote in October and November to complement the material of his 1903 Lowell Lectures. The last of the eight lectures was on abduction, first entitled “How to Theorize” and then “Abduction.” Of abduction, the Syllabus states that its “conclusion is drawn in the interrogative mood ”.1 This is not the first time that Peirce associates abduction to interrogations,2 but the statement is significant because it is the first (...) time that the “interrogative mood” is ascribed to speculative grammar. At the same time, such... (shrink)

To Peirce scholars and other aficionados of logic, semiotics, and pragmatism, 2017 brought the great news of Bellucci’s Speculative Grammar book, providing the eye-opening first detailed chronological overview over Peirce’s career-length developing of his semiotics. Now, the first volume of Ahti Pietarinen’s long-awaited three-volume publication of the totality of Peirce’s writings on his mature logic representation system known as Existential Graphs not only gives us a plethora of hitherto unpublished Peirce papers but also a new and in many ways surprising (...) view into the origin and development of this important fruit of Peirce’s last, creative philosophical burst taking its beginning around 1896, famously to... (shrink)

Bipolar argument graphs represent the structure of complex pro and contra arguments for one or more standpoints. In this article, ampliative and exclusionary principles of evaluating argument strength in bipolar acyclic argumentation graphs are laid out and compared to each other. Argument chains, linked arguments, link attackers and supporters, and convergent arguments are discussed. The strength of conductive arguments is also addressed but it is argued that more work on this type of argument is needed to properly distinguish argument strength (...) from more general value-based components of such arguments. The overall conclusion of the article is that there is no justifiably unique solution to the problem of argument strength outside of a particular epistemological framework. (shrink)

We show that the spectrum of a sentence ϕ in Counting Monadic Second Order Logic (CMSOL) using one binary relation symbol and finitely many unary relation symbols, is ultimately periodic, provided all the models of ϕ are of clique width at most k, for some fixed k. We prove a similar statement for arbitrary finite relational vocabularies τ and a variant of clique width for τ-structures. This includes the cases where the models of ϕ are of tree width at most (...) k. For the case of bounded tree-width, the ultimate periodicity is even proved for Guarded Second Order Logic GSOL. We also generalize this result to many-sorted spectra, which can be viewed as an analogue of Parikh's Theorem on context-free languages, and its analogues for context-free graph grammars due to Habel and Courcelle. Our work was inspired by Gurevich and Shelah (2003), who showed ultimate periodicity of the spectrum for sentences of Monadic Second Order Logic where only finitely many unary predicates and one unary function are allowed. This restriction implies that the models are all of tree width at most 2, and hence it follows from our result. (shrink)

This 1994 book develops a way of representing the meanings of linguistic expressions which is independent of any particular language, allowing the expressions to be manipulated in accordance with rules related to their meanings which could be implemented on a computer. It begins with a survey of the contributions of linguistics, logic and computer science to the problem of representation, linking each with a particular type of formal grammar. A system of graphs is then presented, organized by scope relations in (...) which linguistic constituents are sub-graphs whose configuration is determined by their categories. In developing this system, the author extends the notion of scope and argues that anaphoric and relative pronouns are structural signs not linguistic constituents. Certain count nouns are made the basis of this system and an account of proper names relating the count nouns, is given. (shrink)

Lexical models diverge on the question of how to represent complex words. Under the morpheme-based approach, each morpheme is treated as a separate unit, while under the word-based approach, morphological structure is derived from complex words. In this paper, we propose a new computational model of morphology that is based on graph theory and is intended to elaborate the word-based network approach. Specifically, we use a key concept of network science, the notion of shortest path, to investigate how complex (...) words are learned, stored, and processed. The notion of shortest path refers to the task of finding the shortest or most optimal path connecting two non-adjacent nodes in a network. Building on this notion, the current study shows (i) that new complex words can be segmented into morphemes through the shortest path analysis; (ii) that attested English words tend to represent the shortest paths in the morphological network; and (iii) that novel (unattested) words receive higher acceptability ratings in experiments when they are formed along established optimal paths. The model's performance is tested in two experiments with human participants as well as against the behavioral data from the English Lexicon Project. We interpret our empirical results from the perspective of a usage-based model of grammar and argue that network science provides a powerful tool for analyzing language structure. (shrink)

The paper is the Part IV of the large research, dedicated to both revision of the system of basic logical categories and generalization of modern predicate logic to functional logic. The topic of the paper is consideration of graphs of functions and relations as a derivative and definable category of ultra-Fregean logistics. There are two types of function specification: an operational specification, in which a function is first applied to arguments and then the value of the function is entered as (...) the result of such application, and a grammar specification, in which an object is first entered and then represented as a value of the function on the given arguments. Since function specifications are relations themselves (which was shown in the previous article of the series), this means that each function forms two relations: the obverse (for an operational specification) and the reverse one (for a grammatical specification). Hence, the definitions introduce two types of graphs: the obverse graph of a function, or a graph of the obverse relation formed by this function, is a set of sequences of such objects, the last of which is a value of this function on the sequence of other of these objects as arguments of the same function. Similarly, the reverse graph of a function, or the graph of the reverse relation formed by this function, is called a set of sequences of such objects, the first of which is the value of this function on the sequence of other of these objects as arguments of the same function. In the limiting case of 0-ary functions, both graphs of any such function coincide. Gottlob Frege discovered obverse graphs of functions and called them function value-ranges. He fundamentally emphasized the non-identity of functions and their graphs. Unfortunately, in set theory under the influence of Giuseppe Peano, an alternative approach was adopted, according to which functions and relations are identical to their graphs and, ultimately, to each other. We show that this approach leads to two unacceptable and, at the same time, mutually contradictory conclusions, and must therefore be rejected. (shrink)

In Pninis grammar of Sanskrit one finds the ivastras, a table which defines the natural classes of phonological segments in Sanskrit by intervals. We present a formal argument which shows that, using his representation method, Pninis way of ordering the phonological segments to represent the natural classes is optimal. The argument is based on a strictly set-theoretical point of view depending only on the set of natural classes and does not explicitly take into account the phonological features of the segments, (...) which are, however, implicitly given in the way a language clusters its phonological inventory. The key idea is to link the graph of the Hasse-diagram of the set of natural classes closed under intersection to ivastra-style representations of the classes. Moreover, the argument is so general that it allows one to decide for each set of sets whether it can be represented with Pninis method. Actually, Pnini had to modify the set of natural classes to define it by the ivastras (the segment h plays a special role). We show that this modification was necessary and, in fact, the best possible modification. We discuss how every set of classes can be modified in such a way that it can be defined in a ivastra-style representation.1. (shrink)

Remarkable progress in the mathematics and computer science of probability has led to a revolution in the scope of probabilistic models. In particular, ‘sophisticated’ probabilistic methods apply to structured relational systems such as graphs and grammars, of immediate relevance to the cognitive sciences. This Special Issue outlines progress in this rapidly developing field, which provides a potentially unifying perspective across a wide range of domains and levels of explanation. Here, we introduce the historical and conceptual foundations of the approach, (...) explore how the approach relates to studies of explicit probabilistic reasoning, and give a brief overview of the field as it stands today. (shrink)

LAS is a program that acquires augmented transition network (ATN) grammars. It requires as data sentences of the language and semantic network representatives of their meaning. In acquiring the ATN grammars, it induces the word classes of the language, the rules of formation for sentences, and the rules mapping sentences onto meaning. The induced ATN grammar can be used both for sentence generation and sentence comprehension. Critical to the performance of the program are assumptions that it makes about (...) the relation between sentence structure and surface structure (the graph deformation condition), about when word classes may be formed and when ATN networks may be merged, and about the structure of noun phrases. These assumptions seem to be good heuristics which are largely true for natural languages although they would not be true for many nonnatural languages. Provided these assumptions are satisfied LAS seems capable of learning any context‐free language. (shrink)

continent. 1.2 (2011): 70-75. cartography of ghosts . . . And as a way to talk . . . of temporality the topography of imagination, this body whose dirty entry into the articulation of history as rapturous becoming & unbecoming, greeted with violence, i take permission to extend this grace —Akilah Oliver from “An Arriving Guard of Angels Thusly Coming To Greet” Our disappearance is already here. —Jacques Derrida, 117 I wrestled with death as a threshold, an aporia, a bandit, (...) a part of life. —Akilah Oliver Moraine in geological lingo is that which is left behind. Moraine- a euphemism for the de-stabilizing referent of the writer-ly body as a “troubled and troubling landscape marked by cultural and historical signifiers, the body as flesh memory [...] the body as transitory” (Oliver, Author Statement). Moraine— a geological metaphor of the poet as a holder of memory, as an accumulation of rocks and debris carried along the edge, terminal, dropped at the foot of language (in language). “Flesh Memory” according to Akilah Oliver is "that which my body recalls [...] everything has to do with the task of remembrance and its narrative reinvention [...] I was always translating an idea of the world as it presented itself at any given time. To write was a choice about how to be seen, how to enter the world as translator, actor, participant, in the dialogues that apparently made the real 'real'" (Levitsky). Flesh. Memory. The stuff some poems are made from. The stuff that gets abandoned, gleaned, and picked up by more flesh and memory. "My body, my life has always felt like a kaleidoscopic rip in the dominant fabric [...] has always been a dialogue with the impossible and the apparent” (Levitsky). The impossible-body or poet's body anticipates and performs (through language) an irretrievable death. IN APORIA I realized everything I must have been doing must have been Death. It was Christmas or Labor Day—a holiday—and every time you turned on the radio they said something like ‘four million’ or ‘going to die’.” — Andy Warhol I’m trying on egos, [a justification for the planet’s continuance]. Oh hello transgressor, you’ve come to collect utilitarian debts, humbling narrative space. Give me condition and wheatgrass, I his body disintegrating. I his body is ossification. Death my habit radius, yeah yeah. I his body can’t refuse this summons. I can’t get out this fucking room. Tell me something different about torture dear Trickster. Tell me about the lightness my mother told me to pick the one i love the best how it signals everything I ever wish to believe true just holy on my ship. I jump all over this house. this is it [what I thought is thought only, nothing more deceptive than]: I his body keeps thinking someone will come along, touch me. As like human or lima bean. I’m cradling you to my breast, you are looking out. A little wooden lion you & Peter carve on Bluff Street is quieting across your cheekbone. Not at all like the kind of terror found in sleep, on trembling grounds. It is yesterday now. I have not had a chance to dance in this century. Tonight I shall kill someone, a condition to remember Sunday morning. To think of lives as repetitions [rather than singular serial incarnations]. To understand your death is as exacerbating as trying to figure out why as schoolchildren in mid-nineteen-sixties Southern California we performed reflexive motions: cutting out lace snowflakes, reading Dick and Jane search for their missing mittens, imagining snow. Disintegrat ing . The -ing gerund catapults from the non-finite verb into past, present, future. The -ing as a tail pinned to death, a dog spinning to bite and never fully reaching itself, always shy of the end, circumreferential; a double copulative: deathing. Possessively AO calls it “habit radius” (a virtual fetish attribute) or an inescapable death presence that “confronts us with the paradox of an unattainable object [...] through it’s being unattainable” (Agamben, 27). A flirtation or dialogue with an unknowable thing and aporia utilized as investigative instrument to engage (death) while (in Southern California) we “perform reflexive motions,” cut lace snowflakes, imagine snow, and pay rent like “yeah, yeah” what else is new. And this too, fiction. The book I wish to right. The restored fallen, heroic. Did you expect a different grace from the world? Or upon exit? I’m working on “tough.” They think I am already. All ready. Who is the dead person? Is "I'm sorry" real to a dead person? Browning grass. My hands on this table. A contentious century. A place to pay rent. Redemptive moments. Am I now the dead person? Dead person, dead person, will you partake in my persimmon feast? The body inside the body astounds, confesses sins of the funhouse. I too have admired the people of this planet. Their frilly, orderly intellects. The use they’ve made of cardamom, radiation as well. How they’ve pasteurized milk, loaned surnames to stars, captured tribes, diseases, streets, and ideas too. The living-body as archive: is it possible to experience the living-body as archive without a (kind of) death? Sifting the rubble, rummaging through hoarded debris, skin sheds, memory-napping, and re-awoken (in flesh and) on terrain. “An investigative poetics seeks to unravel staid communities of thought and grasp at what might always be just beyond reach; a poetics of inquiry that lies between language as meaning, and language as rapturous entry into the world of posited ideas and idealism”( Levitsky). Something snaps. Lights blow out prior to embarking upon an investigative poetics. It begins with a question (often a sexy aporia) that leads to openings. "Every politics of memory [...] implies an intervention of the state. It's a state that legislates and acts with regard to the nonfinite mass of materials to be stored, materials which must be collected, preserved” (Derrida & Stiegler, 62). It seems poetic investigation already contains the potentiality of an (invisible) archive if the writer is “always writing” especially when not. Here’s my stupid digital romantic inclination: the living-body (of a poet) is a self-sustaining archive of non-finite memories. But not even I really believe that. AO innovated and sculpted an investigative poetic praxis. In a conversation with poet Rachel Levitsky, poetic-voice is viewed not as a precious identifier, but as a means to think through/about form, concluding that form is linked to framing. While poetic-voice may have tendency to precede form, it also erupts as a result of framing techniques. “They are frames that hold the shape of thinking (which is also to say of imagining) [...].”7 This reminds me of my rabbit who symmetrically chewed the corners of his hutch, which makes me wonder if it’s an expression of the shape of some animal anxiety tick I won’t ever have access to. Beyond the form/frame, death is an unoriginal yet unique limit; death is a damn deathless thing. It functions as a source of poetic investigation; that thing always “just beyond reach.” And how is death not a fetish (in this case an obsessive reverence for something non-material)? “Insofar as it [death] is a presence, a fetish [...] it is in fact something concrete and tangible; but insofar as it is the presence of an absence, it is, at the same time, immaterial and intangible, because it alludes continuously beyond itself to something that can never really be possessed [...] The fetish is [...] a sign of an absence, it is not an unrepeatable unique object; on the contrary, it is something infinitely capable of substitution, without any successive incarnations ever succeeding in exhausting the nullity of which it is the symbol” (Agamben, 33). AO utilized absence (the absent body [catapulted by the death of a beloved]) as an apparatus to investigate. In the process of conversing with absence or that which is absent, the absent body is affectionately objectified, incessantly summonsed back to a place of recognition, of objects, a desire for the absent body to remain intact while exiting the structural limits of grammar and syntax by moving into chant forms “to say what cannot be said” (Levitsky). from AN ARRIVING GUARD OF ANGELS THUSLY COMING TO GREET dear oluchi- the light is blinking rapidly on the black boxy machine. your room seems bigger than before and i am still planning to read some of those robert jordan books of yours. yesterday at the used bookstore where i was browsing the mysteries to “stall reality” (they are really not mysteries at all, they just employ death as the plot mistress but are unable to grasp its mystery at all)—well the point is, things were calm down here for a while and the world was little. i want to be big like you. or i want you not vast, not dead, not gone, but human small and here. i am so selfish. that is what i really want. to see you again. to oil your scalp. to hear you walk in the door, say ma i’m home . give me a chance to say welcome home son. or when leaving, don’t forget your hat . what do you wear out there? i wish you could have taken your new shoes with you. i’m so proud of you. i’m sorry for the way you died. i miss you all the time. even before, i missed you. out there, one time, some different men said: “shake for me girl, i wanna be your backdoor man.” who dat you love. 5/18/03 A letter-poem in sixteen lines “dear oluchi-” is safe-housed in epistolary form. Poetic voice is rendered as internal thought meanderings, a not-so-much confession, private/(pillow?) talk in the desire to be heard/witnessed by the referent and reader with an intent to absolve. The diminutive “i” bears a relation to poet Fanny Howe’s “little g God” in that “One of the (many) things I like about little g God is that you can have a vodka tonic while you talk to little g God, sing along to Bowie’s “I’m Afraid Of Americans,” and hum Coltrane’s “A Love Supreme,” though maybe not all at the same time” (Oliver, 2009). Towards the middle of the poem AO is at a used bookstore and remarks on the funny employment of death as a ‘plot mistress’ that ‘they’ (the dubious employed mystery authors) are ‘unable to grasp’, thereby giving death a mouthpiece, a modeling job, something to do to pass the time. from THE VISIBLE UNSEEN When I first saw graffiti, I recognized in it an ugly aesthetic, a dialectics of violence, a distortion of limbs, a hieroglyph. It was only later when I read the names of the dead that I then saw the path of ghosts charted there; its narrative of loss for the visible unseen whose place in history has been fictionalized and rendered unseen under the totalizing glare of history. Inscriptions, traces, specters. Graffiti begs a public face just as ghosts require non-ghosts (humans) to sense them. The “visible unseen” is a game of hide-and-seek between public viewer and graffiti-inscriber, an ephemeral-violent aesthetic on an ephemeral-policed canvas. Graffiti-inscribers already submit to being forgotten, expect to be washed away; perhaps it’s a holy urban mandala created by gangster-type monks without Buddhism. [...] in its refusal to disappear it forces a discourse in the public imagination we are forced to see what we would rather not, to make sense of an encoded language that we cannot read on the level of meaning. it irritates, forces its agency on us, speaks outside and beyond semiotic reach. An epic font-size pervading the public’s imagination, illegible, I could just close my eyes, remain passive, drive past, abandon it beyond reach, push it further away beyond death walls. In Barcelona I watched a clean up crew wash walls with an awesome water hose but I was more intrigued by their bodies; not a distortion of limbs, not hieroglyph but also not entirely legible; the laboring body permanently erasing specters of the city, and of course they knew it was also an invitation for the ghosts to return. Graffiti is death’s little sister, is also an aporia. [...] Graffiti (fr GK -graph(os), something drawn or written, to diagram or chart) attempts to stage the impossible: to erase the essence of its own subjectivity. Graffiti is a cartography of ghosts, a mapping of elegiac rapture (the transporting of a person from one place to another, as in heaven) and rupture (the state of being broken open.) Dwelling is a fiction stasis. [...] The notion of the past as being something done with, a look-back event, inhibits the possibility of reading graffiti as rapture, as rupture. If graffiti posits history as always in the process of becoming undone. [...] Because what is the body, if not also a complex temple, an unstable site through which to negotiate subjects, materiality, economies, gods, and modes of representations? The site where we are all already belated. Graphein meaning “to write.” “Derrida says every archive makes a law, and the law of genre is its own rupture” (Bloch, 39). However, graffiti is an (non/anti)-archive of erasure due to (the politics of) washing out its subjectivity, which only adds onto (or is symptomatic of) its character. The inhibition of “reading graffiti as rapture, as rupture” is partly due to it being a “look-back” event in that it’s process involves scratching through layers to reveal previous specters underneath. Graffiti (as an ancient genre) has always been a thing of ‘becoming undone’, and therefore ‘belated and always in arrival’ (Levitsky). It’s a Dionysian activity done at night with it’s back turned toward us. "The specter [...] is of the visible, but of the invisible visible, it is the visibility of a body which is not present in flesh and blood [...] appearing for vision, to the brightness of day [...] something becomes almost visible which is visible only insofar as it is not visible in flesh and blood. It is a night visibility. As soon as there is a technology of the image, visibility brings night. It incarnates in a night body, it radiates in a night light" (Derrida & Stiegler, 115). (shrink)

Formal learning theory formalizes the process of inferring a general result from examples, as in the case of inferring grammars from sentences when learning a language. In this work, we develop a general framework—the supervised learning game—to investigate the interaction between Teacher and Learner. In particular, our proposal highlights several interesting features of the agents: on the one hand, Learner may make mistakes in the learning process, and she may also ignore the potential relation between different hypotheses; on the (...) other hand, Teacher is able to correct Learner’s mistakes, eliminate potential mistakes and point out the facts ignored by Learner. To reason about strategies in this game, we develop a modal logic of supervised learning and study its properties. Broadly, this work takes a small step towards studying the interaction between graph games, logics and formal learning theory. (shrink)

A completeness theory for parameterized computational complexity has been studied in a series of recent papers, and has been shown to have many applications in diverse problem domains including familiar graph-theoretic problems, VLSI layout, games, computational biology, cryptography, and computational learning [ADF,BDHW,BFH, DEF,DF1-7,FHW,FK]. We here study the parameterized complexity of two kinds of problems: (1) problems concerning parameterized computations of Turing machines, such as determining whether a nondeterministic machine can reach an accept state in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} (...) \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $k$\end{document} steps (the Short TM Computation Problem), and (2) problems concerning derivations and factorizations, such as determining whether a word \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $x$\end{document} can be derived in a grammar \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $G$\end{document} in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $k$\end{document} steps, or whether a permutation has a factorization of length \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $k$\end{document} over a given set of generators. We show hardness and completeness for these problems for various levels of the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $W$\end{document} hierarchy. In particular, we show that Short TM Computation is complete for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $W[1]$\end{document}. This gives a new and useful characterization of the most important of the apparently intractable parameterized complexity classes. (shrink)

In this paper we provide an introduction to a set of tools for syntactic analysis based on graph theory, and apply them to the study of some properties of English accusativus cum infinitivo constructions, more commonly known as raising to object or exceptional case marking structures. We focus on puzzling extraction asymmetries between base-generated objects and ‘raised’ objects and on the interaction between raising to object and Right Wrap. We argue that a lexicalised derivational grammar with grammatical functions as (...) primitives delivers empirically adequate analyses. (shrink)

Identification of programs for computable functions from their graphs and identification of grammars for recursively enumerable languages from positive data are two extensively studied problems in the recursion theoretic framework of inductive inference.In the context of function identification, Freivalds et al. have shown that only those collections of functions, , are identifiable in the limit for which there exists a 1-1 computable numbering ψ and a discrimination function d such that1. for each , the number of indices i such (...) that ψi = ƒ is exactly one and2. for each , there are only finitely many indices i such that ƒ and ψi agree on the first d arguments.A similar characterization for language identification in the limit has turned out to be difficult. A partial answer is provided in this paper. Several new techniques are introduced which have found use in other investigations on language identification. (shrink)

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)

Compared to existing classical approaches to semiotics which are dyadic (signifier/signified, F. de Saussure) and triadic (symbol/concept/object, Ch. S. Peirce), this theory can be characterized as tetradic ([sign/semion]//[object/noema]) and is the result of either doubling the dyadic approach along the semiotic/ordinary dimension or splitting the ‘concept’ of the triadic one into two (semiotic/ordinary). Other important features of this approach are (a) the distinction made between concepts (only functional pairs of extent and intent) and categories (as representations of expressions) and (b) (...) the indication of the need for providing the mathematical passage from the duality between two sets (where one is a singleton) within systems of sets to category-theoretical monoids within systems of categories while waiting for the solution of this problem in the field of logic. Last but not least, human language expressions are the most representative physical instances of semiotic objects. Moreover, as computational experiments which are possible with linguistic objects present a high degree of systematicity (of oppositions), in general, it is relatively easy to elucidate their dependence on the concepts underlying signs. This new semiotic theory or rather this new research program emerged as the fruit of experimentation and reflection on the application of data science tools elaborated within the frameworks of Rough Set Theory (RST), Formal Context Analysis (FCA) and, though only theoretically, Distributed Information Logic (DIL). The semiotic objects (s-objects) of this theory can be described in tabular datasets. Nevertheless, at this stage of formalisation of the theory, lattices (not trees) can be used as working representation structures for characterizing the components of concept systems and graphs for categories of each layer. (shrink)

Graph games are interactive scenarios with a wide range of applications. This position paper discusses old and new graph games in tandem with matching logics and identifies general questions behind this match. Throughout, we pursue two strands: logic as a way of analyzing existing graph games, and logic as an inspiration for designing new graph games. Our aim is modest: we propose a perspective that complements existing game-theoretic and computational ones, we raise questions, make observations, and (...) suggest research directions—technical results are left to future work. But frankly, our main aim with this survey paper is to show that graph games are concrete, fun, easy to grasp, and yet challenging to study. (shrink)

Graph theory is a specific concept that has numerous applications throughout many industries. Despite the advancement of this technique, graph theory can still yield ambiguous and imprecise results. In order to cut down on these indeterminate factors, neutrosophic logic has emerged as an applicable solution that is gaining significant attention in solving many real-life decision-making problems that involve uncertainty, impreciseness, vagueness, incompleteness, inconsistency, and indeterminacy. However, empirical research on this specific graph set is lacking. Neutrosophic Graph (...) Theory and Algorithms is a collection of innovative research on the methods and applications of neutrosophic sets and logic within various fields including systems analysis, economics, and transportation. While highlighting topics including linear programming, decision-making methods, and homomorphism, this book is ideally designed for programmers, researchers, data scientists, mathematicians, designers, educators, researchers, academicians, and students seeking current research on the various methods and applications of graph theory. (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 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.

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)

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.

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)

This volume provides a detailed account of the syntax of expressive language, that is, utterances that express, rather than describe, the emotions and attitudes of the speaker... Daniel Gutzmann demonstrates that expressivity has strong syntactic reflexes that interact with the semantic and pragmatic interpretation of these utterances, and argues that expressivity is in fact a syntactic feature on a par with other established features such as tense and gender. Evidence for this claim is drawn from three detailed case studies of (...) expressive adjectives, intensifiers, and vocatives; their puzzling properties are accounted for through a minimalist approach to syntactic features and agreement, which shows that expressivity can partake in agreement operations, trigger movement, and be selected for syntactically. The analysis not only supports the hypothesis of expressive syntax, but also highlights the hidden role that grammar may play in phenomena that are traditionally considered to be solely semantic in nature" -- Publisher. (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)

Wilfred Sieg and John Byrnes. K-Graph Machines: Generalizing Turing's Machines and Arguments.

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.

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)

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)

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.

Metaphysical graphical structuralism is the view that at some fundamental level the world is a mathematical graph of nodes and edges. Randall Dipert has advanced a graphical structuralist theory of fundamental particulars and Alexander Bird has advanced a graphical structuralist theory of fundamental properties. David Oderberg has posed a powerful challenge to graphical structuralism: that it entails the absurd inexistence of the world or the absurd cessation of all change. In this paper I defend graphical structuralism. A sharper formulation, (...) some theorems about such structures, and careful attention to the interaction of metaphysical and mathematical features, shows that the absurdities depend on assumptions that are not essential to the view and brings to light a surprising fact about the necessary structure of fundamental properties. (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 $$\mu$$ below the first fixed-point of the $$\aleph$$ -function, there exists a graph $$\mathcal G_\mu$$ satisfying the following.

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)