Showing 1 to 100 of 231 matching Articles
Results per page:
Export (CSV)
By
Kobele, Gregory M.
9 Citations
Mirror theory is a theory of (morpho) syntax introduced in (Brody, 1997). Here I present a formalization of the theory, and study some of its language theoretic properties.
By
Probst, Katharina; Levin, Lori; Peterson, Erik; Lavie, Alon; Carbonell, Jaime
Show all (5)
11 Citations
The AVENUE project contains a runtime machine translationprogram that is surrounded by pre and postruntime modules. Thepostruntime module selects among translation alternatives. Thepreruntime modules are concerned with elicitation of data andautomatic learning of transfer rules in order to facilitate thedevelopment of machine translation between a language with extensiveresources for natural language processing and a language with fewresources for natural language processing. This paper describes theruntime transferbased machine translation system as well as two ofthe preruntime modules: elicitation of data from the minoritylanguage and automated learning of transfer rules from theelicited data.
more …
By
McShane, Marjorie; Nirenburg, Sergei; Cowie, James; Zacharski, Ron
Show all (4)
This paper describes Expedition, an environment designed to facilitate the quick rampup of MT systems from practically any alphabetic language (L) into English. The central component of Expedition is a knowledgeelicitation system that guides a linguistically naive bilingual speaker through the process of describing L in terms of its ecological, morphological, grammatical, lexical, and transfer information. Expedition also includes a module for converting the elicited information into the format expected by the underlying MT system and an MT engine that relies on both the elicited knowledge and resident knowledge about English. The Expedition environment is integrated using a configuration and control system. Expedition represents an innovative approach to answering the need for rapidconfiguration MT by preparing an MT system in which the only missing link is information about L, which is elicited in a structured fashion such that it can be directly exploited by the system. In this paper we report on the current state of Expedition with an emphasis on the knowledge elicitation system.
more …
By
Steedman, Mark
27 Citations
The idea that natural language grammar and planned action are relatedsystems has been implicit in psychological theory for more than acentury. However, formal theories in the two domains have tendedto look very different. This article argues that both faculties sharethe formal character of applicative systems based on operationscorresponding to the same two combinatory operations, namely functional composition and typeraising. Viewing them in thisway suggests simpler and more cognitively plausible accounts of bothsystems, and suggests that the language faculty evolved in the speciesand develops in children by a rather direct adaptation of a moreprimitive apparatus for planning purposive action in the world bycomposing affordances of objects or tools. Theknowledge representation that underlies such planning is alsoreflected in the natural language semantics of tense, mood, andaspect, which the paper begins by arguing provides the key tounderstanding both systems.
more …
By
Davey, Kevin
In this paper, we consider two different ways in which modusponens type reasoning with conditional obligations may be formalized. We develop necessary and sufficient conditions for the validity of each, and make some philosophical observations about the differences between the minor premises that each formalization requires. All this is done within the context of the BelnapPerloff stit theory.
more …
By
Zimmermann, Ernst
3 Citations
We develop a predicate logical extension of a subintuitionistic propositional logic. Therefore a Hilbert type calculus and a Kripke type model are given. The propositional logic is formulated to axiomatize the idea of strategic weakening of Kripke's semantic for intuitionistic logic: dropping the semantical condition of heredity or persistence leads to a nonmonotonic model. On the syntactic side this leads to a certain restriction imposed on the deduction theorem. By means of a Henkin argument strong completeness is proved making use of predicate logical principles, which are only classically acceptable.
more …
By
CsuhajVarjú, Erzsébet; Vaszil, György
1 Citations
We examine the generative power of parallel communicating grammar systems with contextfree or E0L components communicating incomplete information, that is, only subwords of their sentential forms. We prove that these systems in most cases, even with E0L components, generate all recursively enumerable languages.
more …
By
Madhu, Mutyam; Krithivasan, Kamala
3 Citations
Generally, in rewriting P systems (MartinVide and Păun, 2000) one uses Chomsky rules (Hopcroft and Ullman, 1979), whereas in contextual P systems (Madhu and Krithivasan, 2002) we considered contextual rules (Marcus, 1969), (Păun, 1997) for processing stringobjects. By combining Chomsky rules and contextual rules, a new class of P systems were introduced in Krishna et al. (2001), the hybrid P systems. In this paper we continue the study of hybrid P systems, and show that systems with two membranes are universal in the case of contextual rules with a regular choice, and systems with four membranes are universal in the case of contextual rules with finite selection.
more …
By
Higginbotham, James
4 Citations
After reviewing some major features of theinteractions between Linguistics and Philosophyin recent years, I suggest that the depth and breadthof current inquiry into semanticshas brought this subject into contact both with questionsof the nature of linguistic competence and with modern andtraditional philosophical study of the nature ofour thoughts, and the problems of metaphysics.I see this development as promising for thefuture of both subjects.
more …
By
Kudlek, Manfred; Martínvide, Carlos; Mitrana, Victor
1 Citations
A word w is obtained by an ordered npattern interpretation of a word x if there are n homomorphisms h_{1},h_{2},ċċċ, h_{n} such that w=h_{1}(x)h_{2}(x)ċs h_{n}(x). This ordered multiple pattern interpretation is naturally extended to languages. We show a strong relationship between the family of languages obtained by ordered multiple pattern interpretations of regular, linear, and contextfree languages and the family of regular, linear, and contextfree simple matrix languages. Concepts of ambiguity and inherent ambiguity of ordered multiple pattern interpretation are defined and it is shown that these properties are not decidable on the class of contextfree languages. Then, we investigate arbitrary multiple pattern interpretations of the same classes of languages in the Chomsky hierarchy. We show that the classes of languages obtained in this way are recognizable in polynomial time provided that all components of the pattern interpretation are injective homomorphisms. We also present a series of open problems.
more …
By
Hintikka, Jaakko
7 Citations
In gametheoretical semantics, perfectlyclassical rules yield a strong negation thatviolates tertium non datur when informationalindependence is allowed. Contradictorynegation can be introduced only by a metalogicalstipulation, not by game rules. Accordingly, it mayoccur (without further stipulations) onlysentenceinitially. The resulting logic (extendedindependencefriendly logic) explains several regularitiesin natural languages, e.g., why contradictory negation is abarrier to anaphase. In natural language, contradictory negationsometimes occurs nevertheless witin the scope of aquantifier. Such sentences require a secondary interpretationresembling the socalled substitutionalinterpretation of quantifiers.This interpretation is sometimes impossible,and it means a step beyond thenormal firstorder semantics, not an alternative to it.
more …
By
van de Vel, Marcel
2 Citations
Features are unary operators used to build recordlike expressions. The resulting term algebras are encountered in linguistic computation and knowledge representation. We present a general description of feature logic and of a slightly restricted version, called record logic. It is shown that every firstorder theory can be faithfully interpreted in a record logic with various additional axioms. This fact is used elsewhere [15] to extend a result of Tarski and Givant [14] on expressing first order theories in relation algebra.
more …
By
Åqvist, Lennart
6 Citations
The paper presents an infinite hierarchy of sound and complete axiomatic systems for TwoDimensional Modal Tense Logic with Historical Necessity, Agents and Acts. A main novelty of these logics is their capacity to represent formally (i) basic actionsentences asserting that such and such an act is performed/omitted by an agent, as well as (ii) causative actionsentences asserting that by performing/omitting a certain act, an agent causes that such and such a stateofaffairs is realized (e.g. comes about/ceases/remains/remains absent). We illustrate how the formal machinery of our systems can be used to reconstruct a number of interesting ideas in the Logic of Agency and Action that have been proposed by authors like von Wright, von Kutschera, Belnap and Segerberg.
more …
By
Coniglio, M.E.; Carnielli, W.A.
6 Citations
In this paper, logics are conceived as twosorted firstorder structures, and we argue that this broad definition encompasses a wide class of logics with theoretical interest as well as interest from the point of view of applications. The language, concepts and methods of model theory can thus be used to describe the relationship between logics through morphisms of structures called transfers. This leads to a formal framework for studying several properties of abstract logics and their attributes such as consequence operator, syntactical structure, and internal transformations. In particular, we treat Belief Revision Systems (BRS) as our main example, defining the Wide Belief Revision Systems (WBRS's). This generalization allows us to define BRS's in an abstract setting for classical and nonstandard logics. We also show how the concept of translation between logics can be obtained as a particular case of transfers.
more …
By
HakkaniTür, Dilek Z.; Oflazer, Kemal; Tür, Gökhan
31 Citations
We present statistical models for morphological disambiguation in agglutinative languages, with a specific application to Turkish. Turkish presents an interesting problem for statistical models as the potential tag set size is very large because of the productive derivational morphology. We propose to handle this by breaking up the morhosyntactic tags into inflectional groups, each of which contains the inflectional features for each (intermediate) derived form. Our statistical models score the probability of each morhosyntactic tag by considering statistics over the individual inflectional groups and surface roots in trigram models. Among the four models that we have developed and tested, the simplest model ignoring the local morphotactics within words performs the best. Our best trigram model performs with 93.95% accuracy on our test data getting all the morhosyntactic and semantic features correct. If we are just interested in syntactically relevant features and ignore a very small set of semantic features, then the accuracy increases to 95.07%.
more …
By
Cha, Jeongwon; Lee, Geunbae; Lee, JongHyeok
3 Citations
Korean Combinatory Categorial Grammar (KCCG) is an extendedcombinatory categorial grammar formalism to capture thesyntax and interpretation of a relative freess word order, longdistance scrambling, and other specific characteristics of Korean.KCCG formalism can uniformly handle word order variations amongarguments and adjuncts within a clause, as well as in complexclauses and across clause boundaries, i.e. long distancescrambling. The approach we develop takes advantage of the ability of CCGfor type raising and composition along with the ability of variablecategories and unordered argument modeling for relatively freeword order treatment (Lee et al., 1994; Lee et al., 1997).We apply a probability model and heuristics using Koreancharacteristics to our KCCG parser.Results of the experiments on varioustext genre show that the KCCG parser performsat 87.67/87.03% constituent precision/recall.
more …
By
Hodkinson, Ian
23 Citations
We prove decidability of satisfiability of sentences of the monodic packed fragment of firstorder temporal logic with equality and connectives Until and Since, in models with various flows of time and domains of arbitrary cardinality. We also prove decidability over models with finite domains, over flows of time including the real order.
more …
By
Gabbay, Dov; Shehtman, Valentin
12 Citations
In this paper we improve the results of [2] by proving the product f.m.p. for the product of minimal nmodal and minimal ntemporal logic. For this case we modify the finite depth method introduced in [1]. The main result is applied to identify new fragments of classical firstorder logic and of the equational theory of relation algebras, that are decidable and have the finite model property.
more …
By
Marx, Maarten
1 Citations
The complexity of the satisfiability problems of various arrow logics and cylindric modal logics is determined. As is well known, relativising these logics makes them decidable. There are several parameters that can be set in such a relativisation. We focus on the following three: the number of variables involved, the similarity type and the kind of relativised models considered. The complexity analysis shows the importance and relevance of these parameters.
more …
By
Sági, Gábor
7 Citations
We will study the class RSA_{α} of αdimensional representable substitution algebras. RSA_{α} is a subreduct of the class of representable cylindric: algebras, and it was an open problem in Andréka [1] that whether RSA_{α} can be finitely axiomatized. We will show, that the answer is positive. More concretely, we will prove, that RSA_{α} is a finitely axiomatizable quasivariety. The generated variety is also described. We note that RSA_{α} is the algebraic counterpart of a certain proportional multimodal logic and it is related to a natural fragment of first order logic, as well.
more …
By
Marx, Maarten; Mikulás, Szabolcs
3 Citations
We consider the problem of the product finite model property for binary products of modal logics. First we give a new proof for the product finite model property of the logic of products of Kripke frames, a result due to Shehtman. Then we modify the proof to obtain the same result for logics of products of Kripke frames satisfying any combination of seriality, reflexivity and symmetry. We do not consider the transitivity condition in isolation because it leads to infinity axioms when taking products.
more …
By
Degtyarev, Anatoli; Fisher, Michael; Lisitsa, Alexei
22 Citations
It has been shown recently that monodic firstorder temporal logic without functional symbols but with equality is incomplete, i.e., the set of the valid formulae of this logic is not recursively enumerable. In this paper we show that an even simpler fragment consisting of monodic monadic twovariable formulae is not recursively enumerable.
more …
By
Smith, J. A.; Kelly, C.
12 Citations
The measure of the lexical richness of literary texts as a tool in thecomparative analysis of literary style has been hampered by the problem ofthe inequality of text lengths within and between literary corpora. Thispaper proposes an empirical method of description of lexical richness byaveraging measures on multiple chunks of text of a standard lengthwithin a literary work or corpus. A workss average vocabulary richness,average portion of hapax legomenaof the corpus from which it derives,and average repetition of frequently appearing vocabulary may thencharacterize that work relative to other works partitioned along withit. This method reveals the possibility of significant variance of thesemeasures of vocabulary among works of a single authorss corpus and warnsagainst the notion of some absolute authorial stylistic character. Weapply this method of vocabulary averaging to the corpora of threeplaywrights from classical antiquity whose works are chronologicallyrankable: Euripides, Aristophanes, and Terence. We look for trends in vocabulary richness over time, which we posit functions as anindicator of progressively changing authorial ability or inclination. This method then holds the potential of predicting datesfor undateable or tenuously dated works within a corpus of otherwisesecurely dated texts. From the results derived, a relatively late date forthe composition of the redrafted version ofAristophaness Clouds appearslikely; we predict an early composition date for the redraft of TerencessHecyra (and thus are inclined to think that the playwright did verylittle redrafting); and finally we findEuripidess Electra andSupplices exhibiting vocabulary characteristics of extremely latecomposition and we predict dates much later than those assigned based onmetrical considerations.
more …
By
Ahmed, Tarek Sayed
7 Citations
We give a new characterization of the class of completely representable cylindric algebras of dimension 2 #lt; n ≤ w via special neat embeddings. We prove an independence result connecting cylindric algebra to Martin's axiom. Finally we apply our results to finitevariable first order logic showing that Henkin and Orey's omitting types theorem fails for L_{n}, the first order logic restricted to the first n variables when 2 #lt; n#lt;w. L_{n} has been recently (and quite extensively) studied as a manydimensional modal logic.
more …
By
Lutz, Carsten; Sturm, Holger; Wolter, Frank; Zakharyaschev, Michael
Show all (4)
10 Citations
The aim of this paper is to construct a tableau decision algorithm for the modal description logic K_{ALC} with constant domains. More precisely, we present a tableau procedure that is capable of deciding, given an ALCformula ϕ with extra modal operators (which are applied only to concepts and TBox axioms, but not to roles), whether ϕ is satisfiable in a model with constant domains and arbitrary accessibility relations. Tableaubased algorithms have been shown to be 'practical' even for logics of rather high complexity. This gives us grounds to believe that, although the satisfiability problem for K_{ALC} is known to be NEXPTIMEcomplete, by providing a tableau decision algorithm we demonstrate that highly expressive description logics with modal operators have a chance to be implementable. The paper gives a solution to an open problem of Baader and Laux [5].
more …
By
van der Hoek, Wiebe; Thijsse, Elias
7 Citations
We extend our general approach to characterizing information to multiagent systems. In particular, we provide a formal description of an agent's knowledge containing exactly the information conveyed by some (honest) formula ϕ. Only knowing is important for dynamic agent systems in two ways. First of all, one wants to compare different states of knowledge of an agent and, secondly, for agent a's decisions, it may be relevant that (he knows that) agent b does not know more than ϕ. There are three ways to study the question whether a formula ϕ can be interpreted as minimal information. The first method is semantic and inspects ‘minimal’ models for ϕ (with respect to some information order ≤ on states). The second one is syntactic and searches for stable expansions, minimal with respect to some language ℒ*. The third method is a deductive test, known as the disjunction property. We present a condition under which the three methods are equivalent. Then, we show how to construct the order ≤ by collecting ‘layered orders’. Focusing on the multiagent case we identify languages ℒ* for various orders ≤, and show how they yield different notions of honesty for different multimodal systems. We then provide several tools for studying honesty types and illustrate their usefulness on a number of examples, for three modal systems of particular interest. Finally, we relate the different notions of minimal knowledge, and describe possible patterns of honesty for these systems.
more …
By
Martín, P. J.; Gavilanes, A.
In this paper we integrate a sorted unification calculus into free variable tableau methods for logics with term declarations. The calculus we define is used to close a tableau at once, unifying a set of equations derived from pairs of potentially complementary literals occurring in its branches. Apart from making the deduction system sound and complete, the calculus is terminating and so, it can be used as a decision procedure. In this sense we have separated the complexity of sorts from the undecidability of first order logic.
more …
By
Damásio, Carlos Viegas; Pereira, Luís Moniz
6 Citations
In this paper we show the embedding of Hybrid Probabilistic Logic Programs into the rather general framework of Residuated Logic Programs, where the main results of (definite) logic programming are validly extrapolated, namely the extension of the immediate consequences operator of van Emden and Kowalski. The importance of this result is that for the first time a framework encompassing several quite distinct logic programming semantics is described, namely Generalized Annotated Logic Programs, Fuzzy Logic Programming, Hybrid Probabilistic Logic Programs, and Possibilistic Logic Programming. Moreover, the embedding provides a more general semantical structure paving the way for defining paraconsistent probabilistic reasoning with a logic programming semantics.
more …
By
Moreno, Antonio; Cortés, Ulises; Sales, Ton
1 Citations
The beliefs of the agents in a multiagent system have been formally modelled in the last decades using doxastic logics. The possible worlds model and its associated Kripke semantics provide an intuitive semantics for these logics, but they commit us to model agents that are logically omniscient. We propose a way of avoiding this problem, using a new kind of entities called subjective situations. We define a new doxastic logic based on these entities and we show how the belief operators have some desirable properties, while avoiding logical omniscience. A comparison with two wellknown proposals (Levesque's logic of explicit and implicit beliefs and Thijsse's hybrid sieve systems) is also provided.
more …
By
Gutiérrez, G.; de Guzmán, I. P.; Martínez, J.; OjedaAciego, M.; Valverde, A.
Show all (5)
4 Citations
The treebased data structure of Δtree for propositional formulas is introduced in an improved and optimised form. The Δtrees allow a compact representation for negation normal forms as well as for a number of reduction strategies in order to consider only those occurrences of literals which are relevant for the satisfiability of the input formula. These reduction strategies are divided into two subsets (meaning and satisfiabilitypreserving transformations) and can be used to decrease the size of a negation normal form A at (at most) quadratic cost. The reduction strategies are aimed at decreasing the number of required branchings and, therefore, these strategies allow to limit the size of the search space for the SAT problem.
more …
By
Casadio, Claudia; Lambek, Joachim
13 Citations
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.
more …
By
Sima'an, Khalil
5 Citations
Recent models of natural language processing employ statistical reasoning for dealing with the ambiguity of formal grammars. In this approach, statistics, concerning the various linguistic phenomena of interest, are gathered from actual linguistic data and used to estimate the probabilities of the various entities that are generated by a given grammar, e.g., derivations, parsetrees and sentences. The extension of grammars with probabilities makes it possible to state ambiguity resolution as a constrained optimization formula, which aims at maximizing the probability of some entity that the grammar generates given the input (e.g., maximum probability parsetree given some input sentence). The implementation of these optimization formulae in efficient algorithms, however, does not always proceed smoothly. In this paper, we address the computational complexity of ambiguity resolution under various kinds of probabilistic models. We provide proofs that some, frequently occurring problems of ambiguity resolution are NPcomplete. These problems are encountered in various applications, e.g., language understanding for text and speechbased applications. Assuming the common model of computation, this result implies that, for many existing probabilistic models it is not possible to devise tractable algorithms for solving these optimization problems.
more …
By
Okhotin, Alexander
8 Citations
The Generalized LR parsing algorithm for contextfree grammars, introduced by Tomita in 1986, is a polynomialtime implementation of nondeterministic LR parsing that uses graph structured stack to represent the contents of the nondeterministic parser's pushdown for all possible branches of computation at a single computation step. It has been specifically developed as a solution for practical parsing tasks arising in computational linguistics, and indeed has proved itself to be very suitable for natural language processing. Conjunctive grammars extend contextfree grammars by allowing the use of an explicit intersection operation within grammar rules. This paper develops a new LRstyle parsing algorithm for these grammars, which is based on the very same idea of a graphstructured pushdown, where the simultaneous existence of several paths in the graph is used to perform the mentioned intersection operation. The underlying finite automata are treated in the most general way: instead of showing the algorithm's correctness for some particular way of constructing automata, the paper defines a wide class of automata usable with a given grammar, which includes not only the traditional LR(k) automata, but also, for instance, a trivial automaton with a single reachable state. A modification of the SLR(k) table construction method that makes use of specific properties of conjunctive grammars is provided as one possible way of making finite automata to use with the algorithm. It is shown that the algorithm is applicable to any conjunctive grammar and can be implemented to work in no more than cubic time. Additionally, the algorithm can be made to work in linear time for the Boolean closure of the family of deterministic contextfree languages.
more …
By
Moot, Richard; Puite, Quintijn
11 Citations
We present a novel way of using proof nets for the multimodal Lambek calculus, which provides a general treatment of both the unary and binary connectives. We also introduce a correctness criterion which is valid for a large class of structural rules and prove basic soundness, completeness and cut elimination results. Finally, we will present a correctness criterion for the original Lambek calculus Las an instance of our general correctness criterion.
more …
By
Schreibman, Susan
3 Citations
The majority of humanities computingprojects within the discipline of literaturehave been conceived more as digital librariesthan monographs which utilise the medium as asite of interpretation. The impetus to conceiveelectronic research in this way comes from theunderlying philosophy of texts and textualityimplicit in SGML and its instantiation for thehumanities, the TEI, which was conceived as ``amarkup system intended for representing alreadyexisting literary texts''. This article exploresthe most common theories used to conceiveelectronic research in literature, such ashypertext theory, OCHO (Ordered Hierarchy ofContent Objects), and Jerome J. McGann's``noninformational'' forms of textuality. It alsoargues that as our understanding of electronictexts and textuality deepens, and as advancesin technology progresses, other theories, suchas Reception Theory and Versioning, may well beadapted to serve as a theoretical basis forconceiving research more akin to an electronicmonograph than a digital library.
more …
By
MacCaull, Wendy; Orłlowska, Ewa
19 Citations
We present a general framework for proof systems for relational theories. We discuss principles of the construction of deduction rules and correspondences reflecting relationships between semantics of relational logics and the rules of the respective proof systems. We illustrate the methods developed in the paper with examples relevant for the Lambek calculus and some of its extensions.
more …
By
van Pelt, Tamise
3 Citations
Deeply held humanist ideasconstitute a residual discourse in our late ageof print, a discourse that has not been effacedby the rise of technology or by widespreadcomputing practices. Against humanism'sEnlightenment idea of the rational individual,midtwentieth century schools of antihumanismpostulated a ``subject'' constructed by, ratherthan controlling, its language, culture, andtechnologies. The contemporary notion of thesubject comes from Lacanian psychoanalytictheory, where Lacan draws upon cybernetics andcomputing as evidence of a symbolic orderconstructive of subjectivity. Thiscomputational symbolic, in turn, owes much toHeidegger's postwar notions of technology. Today, however, work in new media suggests thatthe dominant discourse on the subject – thediscourse underwriting contemporary theory – isbeing challenged by an emergent discourse ofthe posthuman. Consequently, theory itself isthrown into question. The question of theorynow arises since we must ask whether theposthuman subject of technology is rewritingthe antihumanist subject of theory in new andunanticipated ways. This article thus offersan overview of the shift from humanist, toantihumanist, to posthumanist assumptions. Mygoal is to help readers decide whether today'scomputing environments can still be approachedthrough late twentieth century antihumanisttheories or whether etexts demand new,mediaspecific analyses.
more …
By
Wansing, Heinrich
2 Citations
An extension L^{+} of the nonassociative Lambek calculus Lis defined. In L^{+} the restriction to formulaconclusion sequents is given up, and additional left introduction rules for the directional implications are introduced. The system L^{+} is sound and complete with respect to a modification of the ternary frame semantics for L.
more …
By
Došen, Kosta; Petrić, Zoran
6 Citations
Coherence is demonstrated for categories with binary products and sums, but without the terminal and the initial object, and without distribution. This coherence amounts to the existence of a faithful functor from a free category with binary products and sums to the category of relations on finite ordinals. This result is obtained with the help of prooftheoretic normalizing techniques. When the terminal object is present, coherence may still be proved if of binary sums we keep just their bifunctorial properties. It is found that with the simplest understanding of coherence this is the best one can hope for in bicartesian categories. The coherence for categories with binary products and sums provides an easy decision procedure for equality of arrows. It is also used to demonstrate that the categories in question are maximal, in the sense that in any such category that is not a preorder all the equations between arrows involving only binary products and sums are the same. This shows that the usual notion of equivalence of proofs in nondistributive conjunctivedisjunctive logic is optimally defined: further assumptions would make this notion collapse into triviality.
more …
By
Ionescu, Mihai; MartínVide, Carlos; Păun, Gheorghe
8 Citations
We continue here the study of those P systems where the computation is performed by the communication of objects, that is, systems with symport and antiport rules. Instead of the (number of) objects collected in a specified membrane, as the result of a computation we consider the itineraries of a certain object through membranes, during a halting computation, written as a coding of the string of labels of the visited membranes. The family of languages generated in this way is investigated with respect to its place in the Chomsky hierarchy. When the (symport and antiport) rules are applied in a conditional manner, promoted or inhibited by certain objects which should be present in the membrane where a rule is applied, then a characterization of recursively enumerable languages is obtained; the power of systems with the rules applied freely is only partially described.
more …
By
Soules, Marshall
A range of interdisciplinarydiscourses consider the computermediatedwriting space as a unique performance mediumwith characteristic protocols. Drawing oncontemporary performance theory, literarycriticism, and communication theory, the authorproposes that technologists, academics, andartists are developing idiomatic rhetorics – alingua franca – to explore the technicaland expressive properties of the new ``languagemachines'' and their hypertextual environments.The role of improvisation – and itscrossdisciplinary protocols – provides afurther focus in the discussion of computingpractice and performance.
more …
By
Grigar, Dene
2 Citations
Looking specifically at the genre ofadaptive narrative, this article explores thefuture of literature created for and withcomputer technology, focusing primarily on thetrope of mutability as it is played out withnew media. Some of the questions askedare: What can the medium of a work ofliterature, that is its material aspect, tellus about the text? About character? What canit possibly matter if narrative is recounted onpapyrus, retold on parchment and rag, and thenremediated in pixels? Isn't it the messagecarried by the medium we are most concernedwith, stable or unstable throughout the processof inscription, reinscription, encoding anddecoding, translation and remediation? Thispaper speculates about possibilities ratherthan attempts to answer these questions, butthe structuring and meanmaking componentsconsidered here stand as examples of some wemay want to think about when developing futuretheories about literature – and all types ofwriting – generated by and for electronicenvironments.
more …
By
De Swart, Henriëtte; Sag, Ivan A.
57 Citations
This paper addresses the two interpretations that a combination ofnegative indefinites can get in concord languages like French:a concord reading, which amounts to a single negation, and a doublenegation reading. We develop an analysis within a polyadic framework,where a sequence of negative indefinites can be interpreted as aniteration of quantifiers or via resumption. The first option leadsto a scopal relation, interpreted as double negation. The secondoption leads to the construction of a polyadic negative quantifiercorresponding to the concord reading. Given that sentential negationparticipates in negative concord, we develop an extension of thepolyadic approach which can deal with nonvariable binding operators,treating the contribution of negation in a concord context assemantically empty. Our semantic analysis, incorporated into agrammatical analysis formulated in HPSG, crucially relies on theassumption that quantifiers can be combined in more than one wayupon retrieval from the quantifier store. We also considercrosslinguistic variation regarding the participation ofsentential negation in negative concord.
more …
By
Rockwell, Geoffrey
5 Citations
Computer games have not beenadequately theorized within the humanities. Inthis paper a brief history of computer games ispresented as a starting point for developing atopology of games and a theory of computergames as rhetorical artifacts suitable forcritical study. The paper addresses thequestion of why games should be treatedseriously and suggests a theoretical approachbased on Bakhtin's poetics of the novel wherethe experience of time and space (thechronotope) provides a framework of questionsfor discussing computer games.
more …
By
de Groote, Philippe; Lamarche, François
23 Citations
We introduce nonassociative linear logic, which may be seen as the classical version of the nonassociative Lambek calculus. We define its sequent calculus, its theory of proofnets, for which we give a correctness criterion and a sequentialization theorem, and we show proof search in it is polynomial.
more …
By
Siemens, Raymond G.
3 Citations
If there is such a thing as anew computerassisted literary criticism, itsexpression lies in a model that is asbroadbased as that presented in John Smith'sseminal article, ``Computer Criticism,'' and isas encompassing of the discipline of literarystudies as it is tied to the evolving nature ofthe electronic literary text that lies at theheart of its intersection with computing. Itis the desire to establish the parameters ofsuch a model for the interaction betweenliterary studies and humanities computing –for a model of the new computerassistedliterary criticism – that gave rise to thepapers in this collection and to the severalconference panelpresentations and discussionsthat, in their print form, these papersrepresent.
more …
By
Dresner, Eli
13 Citations
In the first section of this paper I present a well known objection to meaning holism, according to which holism is inconsistent with natural language being learnable. Then I show that the objection fails if language acquisition includes stages of partial grasp of the meaning of at least some expressions, and I argue that standard model theoretic semantics cannot fully capture such stages. In the second section the above claims are supported through a review of current research into language acquisition. Finally, in the third section it is argued that contemporary algebraic logical systems consist in a superior formal vehicle through which to capture stages of partial grasp of meaning; this claim is supported by concrete examples.
more …
By
Best, Michael
The surviving texts of many ofShakespeare's plays include what might betermed a ``performance crux'': a moment that ispuzzling to the director and actors, and whichcalls for some kind of stage business tojustify or explain action. Sometimes thedirector's response is simply to remove thepassage. This paper will look at a crux of thiskind, and discuss how a modern, multimediaelectronic edition can provide tools for thereader or actor to explore the possibilitiesboth of the basic text and the performance thatgrows from it. In Romeo and Juliet thereis an awkward moment when Friar Lawrence fleesthe tomb and deserts Juliet as he hears peopleapproach. The plot requires that he be presentas she awakens and absent as she commitssuicide, but Shakespeare is not often asarbitrary as the received text (Quarto 2) makeshim: ``Come go good Iuliet, I dare no longerstay. Exit.'' By comparing this momentwith Quarto 1 (the first published version ofthe text), Shakespeare's source, lateradaptations, and some modern performances, thepaper will discuss the mutual illumination oftext and performance.
more …
By
Winder, William
Parallel to, and to some degree inreaction to French poststructuralisttheorization (as championed by Derrida,Foucault, and Lacan, among others) is a Frenchneostructuralism built directly on theachievements of structuralism using electronicmeans. This paper examines some exemplaryapproaches to text analysis in thisneostructuralist vein: SATOR's topoidictionary, the WinBrill POS tagger andFrançois Rastier's interpretativesemantics. I consider how a computerassisted``Wissenschaft'' accumulation of expertisecomplements the neostructuralist approach.Ultimately, electronic critical studies will bedefined by their strategic position at theintersection of the two chief technologiesshaping our society: the new informationprocessing technology of computers and therepresentational techniques that haveaccumulated for centuries in texts.Understanding how these two informationmanagement paradigms complement each other is akey issue for the humanities, for computerscience, and vital to industry, even beyond thenarrow realm of the language industries. Thedirection of critical studies, a small planetlong orbiting in only rarefied academiccircles, will be radically altered by the sheersize of the economic stakes implied by a newkind of text, the industrial text, thetechnological heart of an information society.
more …
By
Hájek, Petr
5 Citations
Two variants of monadic fuzzy predicate logic are analyzed and compared with the full fuzzy predicate logic with respect to finite model property (properties) and arithmetical complexity of sets of tautologies, satisfiable formulas and of analogous notion restricted to finite models.
more …
By
Esteva, Francesc; Gispert, Joan; Godo, Lluís; Montagna, Franco
Show all (4)
73 Citations
The monoidal tnorm based logic MTL is obtained from Hájek's Basic Fuzzy logic BL by dropping the divisibility condition for the strong (or monoidal) conjunction. Recently, Jenei and Montgana have shown MTL to be standard complete, i.e. complete with respect to the class of residuated lattices in the real unit interval [0,1] defined by leftcontinuous tnorms and their residua. Its corresponding algebraic semantics is given by prelinear residuated lattices. In this paper we address the issue of standard and rational completeness (rational completeness meaning completeness with respect to a class of algebras in the rational unit interval [0,1]) of some important axiomatic extensions of MTL corresponding to wellknown parallel extensions of BL. Moreover, we investigate varieties of MTL algebras whose linearly ordered countable algebras embed into algebras whose lattice reduct is the real and/or the rational interval [0,1]. These embedding properties are used to investigate finite strong standard and/or rational completeness of the corresponding logics.
more …
By
Montagna, Franco; Ono, Hiroakira
27 Citations
The present paper deals with the predicate version MTL∀ of the logic MTL by Esteva and Godo. We introduce a Kripke semantics for it, along the lines of Ono's Kripke semantics for the predicate version of FL_{ew} (cf. [O85]), and we prove a completeness theorem. Then we prove that every predicate logic between MTL∀ and classical predicate logic is undecidable. Finally, we prove that MTL∀ is complete with respect to the standard semantics, i.e., with respect to Kripke frames on the real interval [0,1], or equivalently, with respect to MTLalgebras whose lattice reduct is [0,1] with the usual order.
more …
By
Purdy, William C.
2 Citations
Fluted Logic is essentially firstorder predicate logic deprived of variables. The lack of variables results in reduced expressiveness. Nevertheless, many logical problems that can be stated in natural language, such as the famous Schubert's Steamroller, can be rendered in fluted logic. Further evidence of the expressiveness of fluted logic is its close relation to description logics. Already it has been shown that fluted logic is decidable and has the finitemodel property. This paper shows that fluted logic has the exponentialmodel property and that deciding satisfiability is NEXPTIMEcomplete. It is shown further that fluted logic is 'nice’, that is, it shares with firstorder predicate logic the interpolation property and model preservation properties.
more …
By
Dorr, Bonnie Jean; Levow, GinaAnne; Lin, Dekang
3 Citations
This paper addresses the problem of automatic acquisition of lexical knowledge for rapid construction of engines for machine translation and embedded multilingual applications. We describe new techniques for largescale construction of a Chinese–English verb lexicon and we evaluate the coverage and effectiveness of the resulting lexicon. Leveraging off an existing Chinese conceptual database called How Net and a large, semantically rich English verb database, we use thematicrole information to create links between Chinese concepts and English classes. We apply the metrics of recall and precision to evaluate the coverage and effectiveness of the linguistic resources. The results of this work indicate that: (a) we are able to obtain reliable Chinese–English entries both with and without preexisting semantic links between the two languages; (b) if we have preexisting semantic links, we are able to produce a more robust lexical resource by merging these with our semantically rich English database; (c) in our comparisons with manual lexicon creation, our automatic techniques were shown to achieve 62% precision, compared to a much lower precision of 10% for arbitrary assignment of semantic links.
more …
By
Langlais, Philippe; Lapalme, Guy
13 Citations
We present TransType: a new approach to MachineAided Translation in which the human translator maintains control of the translation process while being helped by realtime completions proposed by a statistical translation engine. The TransType approach is first presented through a series of prototypes that illustrate their underlying translation model and graphical interface. The results of two rounds of in situ evaluation of TransType prototypes are discussed followed by a set of lessons learned in these experiments. It will be shown that this approach is valued by translators but given the short time allotted for the evaluation, translators were not able to quantitatively increase their productivity. TransType is compared with other approaches and new perspectives are elaborated for a new version being developed in the context of a Fifth Framework European Community Project.
more …
By
Rogerson, Susan; Butchart, Sam
6 Citations
In his paper [6], Greg Restall conjectured that a logic supports a naïve comprehension scheme if and only if it is robustly contraction free, that is, if and only if no contracting connective is definable in terms of the primitive connectives of the logic. In this paper, we present infinitely many counterexamples to Restall's conjecture, in the form of purely implicational logics which are robustly contraction free, but which trivialize naïve comprehension.
more …
By
Weiss, M. Angela; Parikh, Rohit
14 Citations
Subset Spaces were introduced by L. Moss and R. Parikh in [8]. These spaces model the reasoning about knowledge of changing states.
In [2] a kind of subset space called intersection space was considered and the question about the existence of a set of axioms that is complete for the logic of intersection spaces was addressed. In [9] the first author introduced the class of directed spaces and proved that any set of axioms for directed frames also characterizes intersection spaces.
We give here a complete axiomatization for directed spaces. We also show that it is not possible to reduce this set of axioms to a finite set.
more …
By
Coecke, Bob
In Coecke (2002) we proposed the intuitionistic or disjunctive representation of quantum logic, i.e., a representation of the property lattice of physical systems as a complete Heyting algebra of logical propositions on these properties, where this complete Heyting algebra goes equipped with an additional operation, the operational resolution, which identifies the properties within the logic of propositions. This representation has an important application “towards dynamic quantum logic”, namely in describing the temporal indeterministic propagation of actual properties of physical systems. This paper can as such by conceived as an addendum to “Quantum Logic in Intuitionistic Perspective” that discusses spinoff and thus provides an additional motivation. We derive a quantaloidal semantics for dynamic disjunctive quantum logic and illustrate it for the particular case of a perfect (quantum) measurement.
more …
By
Hansen, Inge Gorm; Sørensen, Henrik Selsøe
Globalisation of crime poses a serious threat to the international community and is a matter of growing concern to law enforcement agencies all over the world. In the combat against international and organized crime, the European Union (EU) has supported a number of research and development projects within the domain of law enforcement focusing on crossborder communication, information extraction and data analysis in a multilingual context as well as terminology and knowledge management. LinguaNet is a case in point and the only project involving a multilingual messaging system. A high level of user involvement was a prominent feature of the project and the resulting software – the LinguaNet system – has gained widespread recognition and usage. The paper gives an overview of the LinguaNet approach as a whole emphasising the temporary experimental embedding of fully automatic MT in a multilingual messaging system. The system is intended for use by professionals with no background in linguistics but in great need of fast and robust communication. One of the conclusions drawn from this experiment is that authoring errors proved to be much more counterproductive than insufficiencies of MT. Another conclusion is that it is preferable to leave it to the recipient of a message to request a machine translation rather than providing it automatically up front. In more general terms, the police liked the approach and reported the need for more message type templates and MT facilities. Finally, the project lead to the formation of a European LinguaNet user group network.
more …
By
Recanati, François
92 Citations
In a recent paper (Linguistics and Philosophy23, 4, June 2000), Jason Stanley argues that there are no `unarticulated constituents', contrary to what advocates of Truthconditional pragmatics (TCP) have claimed. All truthconditional effects of context can be traced to logical form, he says. In this paper I maintain that there are unarticulated constituents, and I defend TCP. Stanley's argument exploits the fact that the alleged unarticulated constituents can be `bound', that is, they can be made to vary with the values introduced by operators in the sentence. I show that Stanley's argument rests on a fallacy, and I provide alternative analyses of the data.
more …
By
Kaneko, Mamoru; Nagashima, Takashi; Suzuki, NobuYuki; Tanaka, Yoshihito
Show all (4)
4 Citations
In order to capture the concept of common knowledge, various extensions of multimodal epistemic logics, such as fixedpoint ones and infinitary ones, have been proposed. Although we have now a good list of such proposed extensions, the relationships among them are still unclear. The purpose of this paper is to draw a map showing the relationships among them. In the propositional case, these extensions turn out to be all Kripke complete and can be comparable in a meaningful manner. F. Wolter showed that the predicate extension of the HalpernMoses fixedpoint type common knowledge logic is Kripke incomplete. However, if we go further to an infinitary extension, Kripke completeness would be recovered. Thus there is some gap in the predicate case. In drawing the map, we focus on what is happening around the gap in the predicate case. The map enables us to better understand the common knowledge logics as a whole.
more …
