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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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

This paper extends a notion of local grammars in formal language theory to autosegmental representations, in order to develop a sufficiently expressive yet computationally restrictive theory of well-formedness in natural language tone patterns. More specifically, it shows how to define a class ASL\ of stringsets using local grammars over autosegmental representations and a mapping g from strings to autosegmental structures. It then defines a particular class ASL\ using autosegmental representations specific to tone and compares its expressivity to established (...) formal language grammars that have been successfully applied to other areas of phonology. (shrink)

In this paper we consider the relations existing between four deductive systems that have been called categorial grammars and have relevant connections with linguistic investigations: the syntactic calculus, bilinear logic, compact bilinear logic and Curry''s semantic calculus.

Name der Zeitschrift: Semiotica Jahrgang: 2017 Heft: 214 Seiten: 219-229.

This paper investigates the learnability by positive examples in the sense of Gold of Pregroup Grammars. In a first part, Pregroup Grammars are presented and a new parsing strategy is proposed. Then, theoretical learnability and non-learnability results for subclasses of Pregroup Grammars are proved. In the last two parts, we focus on learning Pregroup Grammars from a special kind of input called feature-tagged examples. A learning algorithm based on the parsing strategy presented in the first part (...) is given. Its validity is proved and its properties are examplified. (shrink)

The paper presents a way to transform pregroup grammars into contextfree grammars using functional composition. The same technique can also be used for the proof-nets of multiplicative cyclic linear logic and for Lambek calculus allowing empty premises.

This paper defines the grammar class of sequentially indexed grammars. Sequentially indexed grammars are the result of a change in the index stack handling mechanism of indexed grammars [Aho68, Aho69]. Sequentially indexed grammars are different from linear indexed grammars [Gaz88]. Like indexed languages, sequentially indexed languages are a fully abstract language class. Unlike indexed languages, sequentially indexed languages allow polynomial parsing algorithms. We give a polynomial algorithm for parsing with sequentially indexed gramamrs that is an (...) extension of the Earley algorithm for parsing with context free grammars. (shrink)

Pali classical grammars reflect a specific idea of what Pali Buddhist texts are. According to this traditional idea, texts are mainly conceived as sound and therefore the initial portions of every grammar deal with sound and sound ligature or sandhi. Sandhi in Pali does not work as systematically as it does in Sanskrit and therefore Pali grammarians have struggled with the optionality of many of their rules on sound ligature. Unlike modern linguists, however, they identify certain patterns of fixed (...) or frozen sandhis that are often associated to the formulas of Pali prose. This paper focuses on these specific frozen sandhis in Pali prose and their connection to the nature of Pali literature broadly. The main working hypothesis is the following: in the same way that certain frozen sandhis in verse obey metrical patterns, frozen sandhis in prose suggest that Pali speech-sounds are subordinated to formulaic rhythmic structures. (shrink)

The concept of love has emerged as a central topic for philosophical and theoretical discussion over the past few years. Whereas the dominant ideology of love in contemporary culture insists that love be understood as a discovery of my long lost second half with whom I merge and finally recreate a whole, contemporary philosophers and theorists have stressed the need to reconsider the concept of love within an ethical framework that can sustain the idea of the other as forever different (...) and separate. Taking as a starting point two different taxi scenes offered by Foucault and Woolf respectively, the article outlines and discusses those two contemporary love grammars, focusing on the concepts of lack and fantasy. Whereas Woolf’s taxi scene is reminiscent of a notion of love as a fantasy of unification, Foucault’s notion of love not only observes the need to maintain the other’s specificity and separateness, but also considers lack and fantasy to be primary and fundamental parts of love as lived experience. While Foucault insists on pleasure and action he also observes the central and unavoidable power of imagination that is attributed the name and function of recollection. The article finally addresses the question of if and how we might be responsible for our daydreams and fantasies. (shrink)

Is language somehow innate in the structure of the human brain, or is it completely learned? This debate is still at the heart of linguistics, especially as it intersects with psychology and cognitive science. In collecting papers which discuss the evidence and arguments regarding this difficult question, The Inheritance and Innateness of Grammars considers cases ranging from infants who are just beginning to learn the properties of a native language to language-impaired adults who will never learn one. These studies (...) show that, while precursors of language exist in other creatures, the abilities necessary for constructing full-fledged grammars are part of the biological endowment of human beings. The essays that comprise this volume test the range and specificity of that endowment, while also contributing to our understanding of the intricate and complex relationship between language and biology. (shrink)

We review the properties of Global Index Grammars (GIGs), a grammar formalism that uses a stack of indices associated with productions and has restricted context-sensitive power. We show how the control of the derivation is performed and how this impacts in the descriptive power of this formalism both in the string languages and the structural descriptions that GIGs can generate.

We investigate a new paradigm in the context of learning in the limit, namely, learning correction grammars for classes of computably enumerable (c.e.) languages. Knowing a language may feature a representation of it in terms of two grammars. The second grammar is used to make corrections to the first grammar. Such a pair of grammars can be seen as a single description of (or grammar for) the language. We call such grammars correction grammars. Correction (...) class='Hi'>grammars capture the observable fact that people do correct their linguistic utterances during their usual linguistic activities. We show that learning correction grammars for classes of c.e. languages in the TxtEx-model (i.e., converging to a single correct correction grammar in the limit) is sometimes more powerful than learning ordinary grammars even in the TxtBe-model (where the learner is allowed to converge to infinitely many syntactically distinct but correct conjectures in the limit). For each n ≥ 0, there is a similar learning advantage, again in learning correction grammars for classes of c.e. languages, but where we compare learning correction grammars that make n + 1 corrections to those that make n corrections. The concept of a correction grammar can be extended into the constructive transfinite, using the idea of counting-down from notations for transfinite constructive ordinals. This transfinite extension can also be conceptualized as being about learning Ershov-descriptions for c.e. languages. For u a notation in Kleene's general system $(O,\, < _o )$ of ordinal notations for constructive ordinals, we introduce the concept of an u-correction grammar, where u is used to bound the number of corrections that the grammar is allowed to make. We prove a general hierarchy result: if u and v are notations for constructive ordinals such that $u\, < _o \,v$ , then there are classes of c.e. languages that can be TxtEx-learned by conjecturing v-correction grammars but not by conjecturing u-correction grammars. Surprisingly, we show that— above "ω-many" corrections—it is not possible to strengthen the hierarchy: TxtEx-learning u-correction grammars of classes of c.e. languages, where u is a notation in O for any ordinal, can be simulated by TxtBe-learning ω-correction grammars, where ω is any notation for the smallest infinite ordinal ω. (shrink)