Showing 1 to 100 of 305 matching Articles
Results per page:
Export (CSV)
By
Kudlek, M.; MartínVide, C.; Mateescu, A.; Mitrana, V.
Show all (4)
16 Citations
We introduce and study a natural extension ofMarcus external contextual grammars. This mathematically simple mechanism whichgenerates a proper subclass of simple matrix languages,known to be mildly contextsensitive ones, is still mildlycontextsensitive. Furthermore, we get an infinite hierarchy ofmildly contextsensitive families of languages.Then we attempt to fill a gap regarding the linguistic relevanceof these mechanisms which consists in defining a tree structure on thestrings generated by manydimensional external contextual grammars,and investigate some related issues. Several open problemsare finally discussed.
more …
By
Jansana, Ramon
6 Citations
Leibniz filters play a prominent role in the theory of protoalgebraic logics. In [3] the problem of the definability of Leibniz filters is considered. Here we study the definability of Leibniz filters with parameters. The main result of the paper says that a protoalgebraic logic S has its strong version weakly algebraizable iff it has its Leibniz filters explicitly definable with parameters.
more …
By
Langholm, Tore; Bezem, Marc
2 Citations
We show that the even linear languages are characterised by a certain extension of the signature of the monadic secondorder logic used by Büchi (1960) and Elgot (1961) to characterise the regular languages.
By
Cieśliński, Cezary
We present a semantic proof of Löb's theorem for theories T containing ZF. Without using the diagonalization lemma, we construct a sentence AUT_{T}, which says intuitively that the predicate “autological with respect to T” (i.e. “applying to itself in every model of T”) is itself autological with respect to T. In effect, the sentence AUT_{T} states “I follow semantically from T”. Then we show that this sentence indeed follows from T and therefore is true.
more …
By
Milnikel, Robert
We present a straightforward embedding of modal nonmonotonic logics into default logic.
By
Tzouvaras, Athanassios
3 Citations
We continue our work [5] on the logic of multisets (or on the multiset semantics of linear logic), by interpreting further the additive disjunction ⊔. To this purpose we employ a more general class of processes, called free, the axiomatization of which requires a new rule (not compatible with the full LL), the cancellation rule. Disjunctive multisets are modeled as finite sets of multisets. The ⊔Horn fragment of linear logic, with the cut rule slightly restricted, is sound with respect to this semantics. Another rule, which is a slight modification of cancellation, added to HF_{⊔} makes the system sound and complete.
more …
By
van Benthem, Johan; Bezhanishvili, Guram; Gehrke, Mai
12 Citations
For a Euclidean space
$$\mathbb{R}^n $$
, let L_{n} denote the modal logic of chequered subsets of
$$\mathbb{R}^n $$
. For every n ≥ 1, we characterize L_{n} using the more familiar Kripke semantics, thus implying that each L_{n} is a tabular logic over the wellknown modal system Grz of Grzegorczyk. We show that the logics L_{n} form a decreasing chain converging to the logic L_{∞} of chequered subsets of
$$\mathbb{R}^\infty $$
. As a result, we obtain that L_{∞} is also a logic over Grz, and that L_{∞} has the finite model property. We conclude the paper by extending our results to the modal language enriched with the universal modality.
more …
By
Davey, Brian A.; Galati, John C.
9 Citations
We give a coalgebraic view of the restricted Priestley duality between Heyting algebras and Heyting spaces. More precisely, we show that the category of Heyting spaces is isomorphic to a full subcategory of the category of all Γcoalgebras, based on Boolean spaces, where Γ is the functor which maps a Boolean space to its hyperspace of nonempty closed subsets. As an appendix, we include a proof of the characterization of Heyting spaces and the morphisms between them.
more …
By
Van Kerkhove, Bart; Vanackere, Guido
8 Citations
This paper defends a pragmatical approach to vagueness. The vaguenessadaptive logic VAL is a good reconstruction of and an excellent, instrument for human reasoning processes in which vague predicates are involved. Apart from its prooftheory and semantics, a Soritestreating model based on it is presented, disarming the paradox. The paper opens perspectives with respect to the construction of theories by means of vague predicates.
more …
By
van Rooy, Robert
40 Citations
Why do we ask questions? Because we want tohave some information. But why this particular kind ofinformation? Because only information of this particularkind is helpful to resolve the decision problemthat the agent faces. In this paper I argue thatquestions are asked because their answers help toresolve the questioner's decision problem, and that thisassumption helps us to interpret interrogativesentences. Interrogative sentences are claimed to have asemantically underspecified meaning and thisunderspecification is resolved by means of the decisionproblem.
more …
By
Indrzejczak, Andrzej
10 Citations
The paper is devoted to the concise description of some Natural Deduction System (ND for short) for Linear Temporal Logic. The system's distinctive feature is that it is labelled and analytical. Labels convey necessary semantic information connected with the rules for temporal functors while the analytical character of the rules lets the system work as a decision procedure. It makes it more similar to Labelled Tableau Systems than to standard Natural Deduction. In fact, our solution of linearity representation is rather independent of the underlying proof method, provided that some form of (analytic) cut is admissible. We will also discuss some generalisations of the system and compare it with other formalizations of linearity.
more …
By
Sabbadin, Michela; Zanardo, Alberto
5 Citations
The aim of this paper is to present a new perspective under which branchingtime semantics can be viewed. The set of histories (maximal linearly ordered sets) in a tree structure can be endowed in a natural way with a topological structure. Properties of trees and of bundled trees can be expressed in topological terms. In particular, we can consider the new notion of topological validity for Ockhamist temporal formulae. It will be proved that this notion of validity is equivalent to validity with respect to bundled trees.
more …
By
Johansson, Ingvar
10 Citations
The paper highlights a certain kind of selffalsifying utterance, which I shall call antiperformative assertions, not noted in speechact theory thus far. By taking such assertions into account, the old question whether explicit performatives have a truthvalue can be resolved. I shall show that explicit performatives are in fact selfverifyingly true, but they are not related to propositions the way ordinary assertions are; antiperformatives have the same unusual relation to propositions, but are selffalsifyingly false. Explicit performatives are speech acts performed in situations where it is important that the speaker is selfreflectively aware of what he is doing in the speech act. Antiperformatives, on the other hand, are speech acts performed in situations where lack of direct selfreflectiveness is required. In order to situate performatives and antiperformatives, the analysis is embedded within a more general discussion of selffalsifying and selfverifying assertions.
more …
By
Skowron, Marcin
This paper introduces interactive graph grammars. An interactive graph grammar (IGG) is a grammar with a derivation controlled by design requirements. Users can interact with IGG by means of a graph description language (GDL). This language makes it possible to use queries and answers for communication between the system and the user.
more …
By
Anchorena, Sergio; Cases, Blanca
Grammar systems are abstract models of computation, in the field of Formal Language Theory, created to study the agent systems proposed by Artificial Intelligence. EcoGrammar or EG systems are grammatical models of ecosystems. Simple EcoGrammar Systems or SEG systems are a subclass of EG. In this work we propose a model of SEG systems whose agents have capabilities ofReproduction, Death and Maturation, called SEG[RDM]. They are able to represent the dynamics of the Logistic equation developed by May in 1973, which is one of the main references in the study of chaos in the dynamics of populations in ecosystems. This work is going on the direction of approaching Artificial Intelligence, Theoretical Computer Sciences and Complex Systems.
more …
By
Taboada, Maite
3 Citations
A common tool for improving theperformance quality of natural languageprocessing systems is the use of contextualinformation for disambiguation. Here I describethe use of a finite state machine (FSM) todisambiguate speech acts in a machinetranslation system. The FSM has two layers thatmodel, respectively, the global and localstructures found in naturallyoccurringconversations. The FSM has been modeled on acorpus of taskoriented dialogues in a travelplanning situation. In the dialogues, one ofthe interactants is a travel agent or hotelclerk, and the other a client requestinginformation or services. A discourse processorbased on the FSM was implemented in order toprocess contextual information in a machinetranslation system. Evaluation results showthat the discourse processor is able todisambiguate and improve the quality of thedialogue translation. Other applicationsinclude humancomputer interaction andcomputerassisted language learning.
more …
By
Burstein, Jill; Marcu, Daniel
10 Citations
This study describes and evaluates twoessaybased discourse analysis systems thatidentify thesis and conclusion statements fromstudent essays written on six different essaytopics. Essays used to train and evaluate thesystems were annotated by two human judges,according to a discourse annotation protocol. Using a machine learning approach, a number ofdiscourserelated features were automaticallyextracted from a set of annotated trainingdata. Using these features, two discourseanalysis models were built using C5.0 withboosting: a topicdependent and atopicindependent model. Both systemsoutperformed a positional algorithm. While thetopicdependent system showed somewhat higherperformance, the topicindependent systemshowed similar results, indicating that asystem can generalize to unseen data – thatis, essay responses on topics that the systemhas not seen in training.
more …
By
Somers, Harold; Tweedie, Fiona
7 Citations
This paper considers the question of authorship attribution techniques whenfaced with a pastiche. We ask whether the techniques can distinguish the real thing from the fake, or can the author fool the computer? If the latter, is this because the pastiche is good, or because the technique is faulty? Using a number of mainly vocabularybased techniques, Gilbert Adair's pastiche of Lewis Carroll, Alice Through the Needle's Eye, is compared with the original `Alice' books. Standard measures of lexical richness, Yule's K andOrlov's Z both distinguish Adair from Carroll, though Z also distinguishesthe two originals. A principal component analysis based on word frequenciesfinds that the main differences are not due to authorship. A discriminantanalysis based on word usage and lexical richness successfully distinguishes thepastiche from the originals. Weighted cusum tests were also unable to distinguish the two authors in a majority of cases. As a crossvalidation, wemade similar comparisons with control texts: another children's story from thesame era, and other work by Carroll and Adair. The implications of thesefindings are discussed.
more …
By
Leacock, Claudia; Chodorow, Martin
99 Citations
Crater is an automated scoringengine that has been developed to scoreresponses to contentbased short answerquestions. It is not simply a stringmatching program – instead it uses predicateargument structure, pronominal reference,morphological analysis and synonyms to assignfull or partial credit to a short answerquestion. Crater has been used in two studies:National Assessment for Educational Progress(NAEP) and a statewide assessment in Indiana.In both studies, crater agreed with humangraders about 84% of the time.
more …
By
Venema, Yde
7 Citations
We prove that every abstractly defined game algebra can be represented as an algebra of consistent pairs of monotone outcome relations over a game board. As a corollary we obtain Goranko's result that van Benthem's conjectured axiomatization for equivalent game terms is indeed complete.
more …
By
Goranko, Valentin
10 Citations
We give a complete axiomatization of the identities of the basic game algebra valid with respect to the abstract game board semantics. We also show that the additional conditions of termination and determinacy of game boards do not introduce new valid identities.
En route we introduce a simple translation of game terms into plain modal logic and thus translate, while preserving validity both ways, game identities into modal formulae.
The completeness proof is based on reduction of game terms to a certain ‘minimal canonical form’, by using only the axiomatic identities, and on showing that the equivalence of two minimal canonical terms can be established from these identities.
more …
By
Bird, Steven; Simons, Gary
12 Citations
As language data and associatedtechnologies proliferate and as the languageresources community expands, it is becomingincreasingly difficult to locate and reuse existingresources. Are there any lexical resources forsuchandsuch a language? What tool workswith transcripts in this particular format?What is a good format to use for linguisticdata of this type? Questions like these dominate manymailing lists, since web search engines are anunreliable way to find language resources. Thispaper reports on a new digital infrastructurefor discovering language resources beingdeveloped by the Open Language Archives Community(OLAC). At the core of OLAC is its metadataformat, which is designed to facilitatedescription and discovery of all kinds oflanguage resources, including data, tools, oradvice. The paper describes OLAC metadata, itsrelationship to Dublin Core metadata, and itsdissemination using the metadata harvesting protocol of the Open Archives Initiative.
more …
By
Mahoney, Anne
This paper describes an encoding for representing quantitativemetrical analyses in TEI SGML or XML documents, using only charactersfrom the standard keyboard set, and a system for converting thisencoding to other forms for display.
By
Berwanger, Dietmar
13 Citations
We investigate the expressive power of Parikh's Game Logic interpreted in Kripke structures, and show that the syntactical alternation hierarchy of this logic is strict. This is done by encoding the winning condition for parity games of rank n. It follows that Game Logic is not captured by any finite level of the modal μcalculus alternation hierarchy. Moreover, we can conclude that model checking for the μcalculus is efficiently solvable iff this is possible for Game Logic
more …
By
Pauly, Marc; Parikh, Rohit
42 Citations
Game Logic is a modal logic which extends Propositional Dynamic Logic by generalising its semantics and adding a new operator to the language. The logic can be used to reason about determined 2player games. We present an overview of metatheoretic results regarding this logic, also covering the algebraic version of the logic known as Game Algebra.
more …
By
van Benthem, Johan
12 Citations
Game logics describe general games through powers of players for forcing outcomes. In particular, they encode an algebra of sequential game operations such as choice, dual and composition. Logic games are special games for specific purposes such as proof or semantical evaluation for firstorder or modal languages. We show that the general algebra of game operations coincides with that over just logical evaluation games, whence the latter are quite general after all. The main tool in proving this is a representation of arbitrary games as modal or firstorder evaluation games. We probe how far our analysis extends to product operations on games. We also discuss some more general consequences of this new perspective for standard logic.
more …
By
Bonanno, Giacomo
2 Citations
Two notions of memory are studied both syntactically and semantically: memory of past beliefs and memory of past actions. The analysis is carried out in a basic temporal logic framework enriched with beliefs and actions.
By
Dekker, Paul
3 Citations
In this paper, I want to contribute to understanding and improving on Keenan'sintriguing equivalence result about reducible type < 2 > quantifiers (Keenan, 1992).I give an alternative proof of his result which generalizes to type < 2 > quantifiers, andI show how the reduction of a reducible type < 2 > quantifier to (the composition of) ntype < n > quantifiers can be effected.
more …
By
Lomuscio, Alessio; Sergot, Marek
69 Citations
We investigate an extension of the formalism of interpreted systems by Halpern and colleagues to model the correct behaviour of agents. The semantical model allows for the representation and reasoning about states of correct and incorrect functioning behaviour of the agents, and of the system as a whole. We axiomatise this semantic class by mapping it into a suitable class of Kripke models. The resulting logic, KD45_{n}^{ij}, is a stronger version of KD, the system often referred to as Standard Deontic Logic. We extend this formal framework to include the standard epistemic notions defined on interpreted systems, and introduce a new doublyindexed operator representing the knowledge that an agent would have if it operates under the assumption that a group of agents is functioning correctly. We discuss these issues both theoretically and in terms of applications, and present further directions of work.
more …
By
Büring, Daniel
142 Citations
This paper presents a comprehensive pragmatic theory ofcontrastive topic and its relation to focus in English.In discussing various constructions involving contrastive topics,it argues that they make reference to complex, hierarchicalaspects of discourse structure. In this, it follows and spellsout a proposal sketched in Roberts (1996, p. 121ff),using the formal tools found in Büring (1994,1997b). It improves on existing accounts in the accuracy with which it predicts the nonoccurrence of the accent patterns associated with focus and contrastive topic, and locates the analysis of contrastive topicswithin a broader picture of discourse and information structure.
more …
By
van Ditmarsch, Hans
39 Citations
Suppose we have a stack of cards that is divided over some players. For certain distributions of cards it is possible to communicate your hand of cards to another player by public announcements, without yet another player learning any of your cards. A solution to this problem consists of some sequence of announcements and is called an exchange. It is called a direct exchange if it consists of (the minimum of) two announcements only. The announcements in an exchange have a special form: they are safe communications, an interesting new form of update. Certain unsafe communications turn out to be unsuccessful updates. A communication is a public announcement that is known to be true. Each communication may be about a set of alternative card deals only, and even about a set of alternatives to the communicating player's own hand only. We list the direct exchanges for a deal of seven cards where the two players holding three cards communicate their hands to each other. Our work may be applicable to the design of cryptographic protocols.
more …
By
Kearns, Kate
11 Citations
Ryle (1949, Chapter V) discusses a range of predicates which in different ways exemplify a property I shall call quasiduality – they appear to report two actions or events in one predicate. Quasiduality is the key property of predicates Ryle classed as achievements. Ryle's criteria for classification were not temporal or aspectual, and Vendler's subsequent adoption of the term achievement for the aktionsart of momentary events changes the term – Rylean achievements and Vendlerian achievements are in principle different classes. Nevertheless, I shall argue in this paper that certain kinds of quasiduality do have aspectual significance.
This paper examines a number of quasidual predicates which are not generally discussed in the aktionsart literature, includingbreak a promise, miscount, and cure the patient. Two types of quasidual predicates are identified and dubbed criterion predicates and causative upshot predicates. It is shown that both types of quasidual predicate lack process progressives, despite being durative, and it is argued that the lack of process progressives identifies these predicates as (aspectual) achievements. They are termed durative achievements to distinguish them from canonical, momentary achievements.
It is argued that these predicates lack process progressives, and hence are achievements, because they express individuallevel predicates on the event argument. A process progressive is stagelevel for the event, and hence is incompatible with a predicate which is lexically individuallevel for the event.
more …
By
Jäger, Gerhard
1 Citations
This paper deals with a series of semantic contrasts between the copula be and the preposition as, two functional elements that both head elementary predication structures. It will be argued that the meaning of as is a type lowering device shifting the meaning of its complement NP from the type of generalized quantifiers to the type of properties (where properties are conceived as relations between individuals and situations), while the copula be induces a type coercion from (partial) situations to (total) possible worlds. Paired with van der Sandt's (1992) theory of presupposition accommodation, these assumptions will account for the observed contrasts between as and be.
more …
By
van der Hoek, Wiebe; Wooldridge, Michael
125 Citations
Branchingtime temporal logics have proved to be an extraordinarily successful tool in the formal specification and verification of distributed systems. Much of their success stems from the tractability of the model checking problem for the branching time logic CTL, which has made it possible to implement tools that allow designers to automatically verify that systems satisfy requirements expressed in CTL. Recently, CTL was generalised by Alur, Henzinger, and Kupferman in a logic known as “Alternatingtime Temporal Logic” (ATL). The key insight in ATL is that the path quantifiers of CTL could be replaced by “cooperation modalities”, of the form 《Γ》, where Γ is a set of agents. The intended interpretation of an ATL formula 《Γ》ϕ is that the agents Γ can cooperate to ensure that ϕ holds (equivalently, that Γ have a winning strategy for ϕ). In this paper, we extend ATL with knowledge modalities, of the kind made popular in the work of Fagin, Halpern, Moses, Vardi and colleagues. Combining these knowledge modalities with ATL, it becomes possible to express such properties as “group Γ can cooperate to bring about ϕ iff it is common knowledge in Γ that ψ”. The resulting logic — Alternatingtime Temporal Epistemic Logic (ATEL) — shares the tractability of model checking with its ATL parent, and is a succinct and expressive language for reasoning about gamelike multiagent systems.
more …
By
van der Meyden, Ron; Wong, Kashu
34 Citations
Sound and complete axiomatizations are provided for a number of different logics involving modalities for the knowledge of multiple agents and operators for branching time, extending previous work of Halpern, van der Meyden and Vardi [to appear, SIAM Journal on Computing] for logics of knowledge and linear time. The paper considers the system constraints of synchrony, perfect recall and unique initial states, which give rise to interaction axioms. The language is based on the temporal logic CTL*, interpreted with respect to a version of the bundle semantics.
more …
By
Amtrup, Jan W.
5 Citations
We present a finite state morphology system augmented with typed feature structures as weights on transitions. This mechanism allows the use of highly efficient finite state approaches for morphological analysis and generation, while providing the rich linguistic descriptions often used in Machine Translation systems. Using a semiring interpretation, the weight of a morphological analysis result represents the possible linguistic interpretations of an input word, while the resulting character string itself represents the lemma of the input. Longdistance phenomena and infixation can be handled in an easy and elegant manner, simultaneously providing a seamless interface to subsequent linguistic processing modules. Two extensions to the basic model are discussed: the incorporation of lexical knowledge into the finite state transducer and a transformation that renders unificationbased finite state models as efficient as those employing other weight structures. The model is applied to morphological operations in a Persian–English Machine Translation system.
more …
By
Pretorius, Laurette; Bosch, Sonja E.
4 Citations
As one of the largest of the 11 official languages of South Africa, Zulu is spoken by approximately 9 million people. It forms part of a language family which is characterized by rich agglutinating morphological structures. This paper discusses a prototype of a computational morphological analyzer for Zulu, built by means of the Xerox finite state tools, in particular lexc and xfst. In addition to considering both the morphotactics and the morphophonological alternation rules that apply, the focus is on implementation and other issues that need to be resolved in order to produce a useful software artefact for automated morphological analysis. The current status of the prototype is alluded to by providing morphological scope, that is the various word categories (parts of speech) that may be handled, and the lexical coverage in terms of the number of different Zulu roots that are included in the embedded lexicon of the analyzer. Preliminary testing and validation procedures are briefly discussed.
more …
By
Skut, Wojciech; Ulrich, Stefan; Hammervold, Kathrine
1 Citations
We describe a novel method of compiling ranked tagging rules into a “bimachine”, i.e. a deterministic finite state device composed of two finite automata: a lefttoright one and a righttoleft one. The actual compilation is based on algorithms for finite state acceptors rather than transducers, which guarantees determinizability and the efficiency of compilation. The compiler has been used in a number of applications within a speech synthesis system.
more …
By
Dhonnchadha, Uí; Pháidín, Caoilfhionn Nic; Genabith, Josef Van
1 Citations
Minority languages must endeavour to keep up with and avail of language technology advances if they are to prosper in the modern world. Finite state technology is mature, stable and robust. It is scalable and has been applied successfully in many areas of linguistic processing, notably in phonology, morphology and syntax. In this paper, the design, implementation and evaluation of a morphological analyser and generator for Irish using finite state transducers is described. In order to produce a highquality linguistic resource for NLP applications, a complete set of inflectional morphological rules for Irish is handcrafted, as is the initial test lexicon. The lexicon is then further populated semiautomatically using both electronic and printed lexical resources. Currently we achieve coverage of 89% on unrestricted text. Finally we discuss a number of methodological issues in the design of NLP resources for minority languages.
more …
By
Kondrak, Grzegorz
29 Citations
The computation of the optimal phonetic alignment andthe phonetic similarity between wordsis an important step in many applications in computational phonology,including dialectometry.After discussing several related algorithms,I present a novel approach to the problem that employsa scoring scheme for computing phonetic similarity between phonetic segmentson the basis of multivalued articulatory phonetic features.The scheme incorporates the key concept of feature salience,which is necessary to properly balance the importance of various features.The new algorithm combines several techniquesdeveloped for sequence comparison:an extended set of edit operations,local and semiglobal modes of alignment,and the capability of retrieving a set of nearoptimal alignments.On a set of 82 cognate pairs,it performs better than comparable algorithms reported in the literature.
more …
By
Heeringa, Wilbert; Braun, Angelika
4 Citations
Measuring dialect distances can be based on the comparison of words, and the comparison words should be based on the comparison of sounds. Inthis research we used an adjusted version of an articulationbased system,developed by Almeida and Braun (1986) for findingsound distances, using the IPA system.For comparison of two pronunciations of a word corresponding with twodifferent varieties, we used the Levenshtein algorithm, which finds theeasiest way in which one word can be changed into the other by inserting,deleting or substituting sounds. As operations weights of these threeoperations we used distances as found with the Almeida & Braun system.The dialect distance is now equal to the average of a range of word distances. We applied the technique to 360 Dutch dialects. The transcriptions of 125 words for each dialect are taken from the Reeks Nederlandse Dialectatlassen (Blancquaert and Peé, 1925–1982). We get a division with clear similarities to traditional dialect maps when classifying dialects. Using logarithmic sound distances improves results compared to results based on constant sound distances.
more …
By
Speelman, Dirk; Grondelaers, Stefan; Geeraerts, Dirk
28 Citations
In this text we present``profilebased linguistic uniformity'', a methoddesigned to compare language varieties on thebasis of a wide range of potentiallyheterogeneous linguistic variables. In manyrespects a parallel can be drawn with currentmethods in dialectometry (for an overview, see,Nerbonne and Heeringa, 2001; Heeringa, Nerbonneand Kleiweg, 2002): in both casesdissimilarities between varieties on the basisof individual variables are summarized inglobal dissimilarities, and a series oflanguage varieties are subsequently clusteredor charted using multivariate techniques suchas cluster analysis or multidimensionalscaling. This global similarity between themethods makes it possible to compare them andto investigate the implications of notabledifferences. In this text we specifically focuson, and defend one characteristic of ourmethodology, its profilebased nature.
more …
By
Kracht, Marcus
We study the effect of various constraints on derivations: Cyclicity, Freeze, and Shortest Steps. It will be shown that given a surface structure, one can effectively determine in polynomial time an ordering on the chain links such that any linear ordering extending it gives rise to a derivation. The length of the steps can be computed as well. Using this, it is shown that up to inessential variations Freeze and Shortest Steps select only one derivation as the right one, while Cyclicity leaves (in the worst case) exponentially many choices. Moreover, the combined effect of Shortest Steps and Cyclicity is determined, once again leading to an essentially unique solution.
more …
By
Wintner, Shuly
1 Citations
An essential prerequisite for modular grammar design is a clear, mathematically wellfounded definition for the semantics of grammar formalisms, facilitating reasoning about grammars and their computational properties. This paper shows that existing definitions for the semantics of unification grammars, both operational and denotational, are not compositional with respect to a simple and natural grammar combination operator. Adapting results from the semantics of logic programming languages, we suggest a denotational semantics that we show to be both compositional and fullyabstract. This semantics induces an equivalence relation by which two grammars are equivalent if and only if they can be interchanged in any context. This provides a clear, mathematically sound way for defining grammar modularity.
more …
By
Heeringa, Wilbert; Gooskens, Charlotte
8 Citations
Gooskens (2003) described an experiment which determined linguistic distances between 15 Norwegian dialects as perceived by Norwegian listeners. The results are compared toLevenshtein distances, calculated on the basis of transcriptions (of the words) of the same recordings as used in the perception experiment. The Levenshtein distance is equal to the sum of the weights of the insertions,deletions and substitutions needed to change one pronunciation into another. The success of the method depends on the reliability of the transcriber.The aim of this paper is to find an acoustic distance measure between dialects which approximates perceptual distance measure. We use andcompare different representations of the acoustic signal: Barkfilter spectrograms, cochleagrams and formant tracks. We now apply the Levenshteinalgorithm to spectra or formant value bundles instead of transcription segments. From these acoustic representations we got the best results usingthe formant track representation. However the transcriptionbased Levenshtein distances correlate still more closely. In the acoustic signalthe speakerdependent influence is kept to some extent, while a transcriberabstracts from voice quality. Using more samples per dialect word (instead of only one as in our research) should improve the accuracy of the measurements.
more …
By
Portner, Paul
49 Citations
The English perfect involves two fundamental components of meaning: a truthconditional one involving temporal notions and a current relevance presupposition best expressed in terms drawn from the analysis of modality. The proposal made here draws much for the Extended Now theory (McCoard 1978 and others), but improves on it by showing that many aspects of the perfect's meaning may be factored out into independent semantic or pragmatic principles.
more …
By
Henle, J. M.
1 Citations
Following [3], we build higherorder models of analysis resembling the frameworks of nonstandard analysis. The models are entirely canonical, constructed without Choice. Weak transfer principles are developed and the models are applied to topology, graph theory, and measure theory. A Loeblike measure is constructed.
more …
By
Ono, Hiroakira
12 Citations
In this paper, a theorem on the existence of complete embedding of partially ordered monoids into complete residuated lattices is shown. From this, many interesting results on residuated lattices and substructural logics follow, including various types of completeness theorems of substructural logics.
more …
By
Sempere, José M.
Linear languages can be characterized by regularlike expressions (linear expressions) according to a previous work. In this paper, we consider some equivalence properties of linear expressions in order to obtain a characterization of reversal and Kolmogorov complexity of linear languages. First, we introduce the relationship between regular expressions equivalence properties and linear expressions equivalence properties. Then, we define permutation and compression equivalence properties in order to handle linear expressions to obtain shorter equivalent ones. The study of reversal and Kolmogorov complexities associated to linear grammars is performed in the rest of the paper. We obtain a speedup theorem for reversal complexity. Finally, we define a Kolmogorovlike complexity associated to linear grammars and we deduce upper bounds for such complexity measure.
more …
By
Vulanović, Relja
1 Citations
An earlier method for measuring grammar efficiency is revisited in this paper. The method is based on a finite analytic grammar which has word order as its dominant component. The grammar description uses the apparatus of set theory, whereas the measure of its efficiency requires some combinatorics and algebra tools, and is related to an optimization problem defining maximally efficient grammars. This results in a numerical representation of the grammatical structure. A simpler and improved formula for measuring grammar efficiency is proposed, enabling a wider and easier applicability of the formula. This is illustrated by many examples, both abstract and those related to natural languages. It is also shown that the reciprocal of grammar efficiency can be used to measure grammar complexity, which indicates how complex a grammar is, relative to the linguistic information it conveys.
more …
By
Nerbonne, John; Kleiweg, Peter
22 Citations
The Linguistic Atlas of the Middle and South Atlantic States(LAMSAS) is admirably accessible for reanalysis (seehttp://hyde.park.uga.edu/lamsas/,Kretzschmar, 1994). The present paper applies alexical distance measure to assess the lexical relatedness of LAMSAS'ssites, a popular focus of investigation in the past(Kurath, 1949; Carver, 1989; McDavid, 1994). Several conclusions arenoteworthy: First, and least controversially, we note that LAMSAS isdialectometrically challenging at least due to the range of fieldworkers and questionnaires employed. Second, on the issue of whichareas ought to be recognized, we note that our investigations tend tosupport a threewayNorth/South/Midlands division rather than a twowayNorth/South division, i.e. they tend to support Kurath and McDavidrather than Carver, but this tendency is not conclusive. Third, weextend dialectometric technique in suggesting means of dealing withalternate forms and multiple responses.
more …
By
Palander, Marjatta; OpasHänninen, Lisa Lena; Tweedie, Fiona
The aim of this study is to show how clusteranalysis can shed light on very complexvariation in a transitional dialect zone ineastern Finland. In the course of history thisarea has been on the border between Sweden andRussia and the population has clearly been oftwo kinds: the Savo people and the Karelians.It is a wellknown fact that there is variationamong these dialects, but the spread and extentof the variation has not been demonstrated previously.The idiolects of the area were studied in thelight of ten phonological and morphologicalfeatures. The material consisted of recordingsof 198 idiolects, totalling around 195 hoursand representing 19 parishes. The variation wasanalysed using hierarchical cluster analysis.While the analysis showed the extent of thevariation between idiolects and parishes, italso demonstrated how the effects of the oldparishes, borders and settlements are stillvisible in the dialects. On the parish level,the data formed clear clusters that correspondwith the main dialects in the area and itssurroundings. On the idiolect level, however,the speakers from the surrounding areas formedfairly homogenous clusters but the idiolectsfrom the Savonlinna area were spread acrossalmost all clusters.
more …
By
Nerbonne, John; Kretzschmar, William
8 Citations
Dialectology is the study of dialects, and dialectometry is themeasurement of dialect differences, i.e. linguistic differences whosedistribution is determined primarily by geography. The earliest worksin dialectology showed that language variation is complex bothgeographically and linguistically and cannot be reduced to simplecharacterizations. There has thus always been a perceived need fortechniques which can deal with large amounts of data in a controlledmeans, i.e. computational techniques. This special issue ofComputers and the Humanities presents a range of recent work onthis topic.
more …
By
Cantini, Andrea
13 Citations
We investigate a contractionless naive set theory, due to Grisin [11]. We prove that the theory is undecidable.
By
Voutsadakis, George
2 Citations
Metalogical properties that have traditionally been studied in the deductive system context (see, e.g., [21]) and transferred later to the institution context [33], are here formulated in the πinstitution context. Preservation under deductive equivalence of πinstitutions is investigated. If a property is known to hold in all algebraic πinstitutions and is preserved under deductive equivalence, then it follows that it holds in all algebraizable πinstitutions in the sense of [36].
more …
By
Priest, Graham
9 Citations
The paper discusses the similarity between geometry, arithmetic, and logic, specifically with respect to the question of whether applied theories of each may be revised. It argues that they can  even when the revised logic is a paraconsistent one, or the revised arithmetic is an inconsistent one. Indeed, in the case of logic, it argues that logic is not only revisable, but, during its history, it has been revised. The paper also discusses Quine's well known argument against the possibility of “logical deviancy”.
more …
By
Habash, Nizar; Dorr, Bonnie; Traum, David
7 Citations
This paper describes Lexogen, a system for generating naturallanguagesentences from Lexical Conceptual Structure, an interlingualrepresentation. The system has been developed as part of aChinese–English Machine Translation (MT) system; however, it isdesigned to be used for many other MT language pairs and naturallanguage applications. The contributions of this work include: (1)development of a largescale Hybrid Natural Language Generation system withlanguageindependent components; (2) enhancements to an interlingualrepresentation and associated algorithm forgeneration from ambiguous input; (3) development of an efficientreusable languageindependent linearization module with a grammardescription language that can be used with other systems; (4)improvements to an earlier algorithm forhierarchically mapping thematic roles to surface positions; and (5)development of a diagnostic tool for lexicon coverage and correctnessand use of the tool for verification of English, Spanish, and Chineselexicons. An evaluation of Chinese–English translation quality showscomparable performance with a commercial translation system. Thegeneration system can also be extended to other languages and this isdemonstrated and evaluated for Spanish.
more …
By
Txurruka, Isabel Gómez
19 Citations
In the first part of this article, we show that, contrary to the Gricean tradition, interclausal and is not semantically equivalent to logical conjunction and, contrary to temporal approaches such as BarLevand Palacas 1980, it is not temporallyloaded. We then explore a commonsenseidea – namely that while sentence juxtaposition might be interpreted either as discourse coordination or subordination, and indicates coordination. SDRT already includes notions of coordinating and subordinating discourse relations (cf. Lascarides and Asher 1993, Asher 1993), and the meaning of and is related to this distinction. Similar distinctions that play a crucial role in anaphora resolution have also appeared in AI – cf. Scha and Polanyi 1988, or Webber 1991. However, this discoursestructurebased distinction has not been well defined yet, and our approach provides independent motivation for it. This paper argues that the semantics of and includes a notion of coordination expressed as the requirement of a Coordinated Discourse Topic (CDT).CDT characterizes aclass of discourse relations, among which are Narration and Result.Once the basic semanticcontribution of and is isolated, effects related to its presence such as changes in temporal structure, blocking of a Discourse Relation, or conditional meanings are shown to follow from the defeasiblearchitecture set up by SDRT.
more …
By
McShane, Marjorie; Nirenburg, Sergei
2 Citations
This paper analyzes the structure and meaning of text elements crosslinguistically and discusses how that information can be elicited from people in a way that is directly useful for NLP applications. We describe a recently developed computerbased linguistic knowledge elicitation system that initiates a new paradigm of knowledge acquisition methodologies for NLP. In particular, we describe the natural language phenomena the system seeks to cover, the approach to knowledge elicitation and its rationale, the elicitation modules themselves, and broader implications of this work.
more …
By
Voutsadakis, George
12 Citations
A category theoretic generalization of the theory of algebraizable deductive systems of Blok and Pigozzi is developed. The theory of institutions of Goguen and Burstall is used to provide the underlying framework which replaces and generalizes the universal algebraic framework based on the notion of a deductive system. The notion of a term πinstitution is introduced first. Then the notions of quasiequivalence, strong quasiequivalence and deductive equivalence are defined for πinstitutions. Necessary and sufficient conditions are given for the quasiequivalence and the deductive equivalence of two term πinstitutions, based on the relationship between their categories of theories. The results carry over without any complications to institutions, via their associated πinstitutions. The πinstitution associated with a deductive system and the institution of equational logic are examined in some detail and serve to illustrate the general theory.
more …
By
Czelakowski, Janusz
7 Citations
The paper is conceived as a first study on the Suszko operator. The purpose of this paper is to indicate the existence of close relations holding between the properties of the Suszko operator and the structural properties of the model class for various sentential logics. The emphasis is put on generality both of the results and methods of tackling the problems that arise in the theory of this operator. The attempt is made here to develop the theory for nonprotoalgebraic logics.
more …
By
Barbour, G. D.; Raftery, J. G.
2 Citations
Relatively congruence regular quasivarieties and quasivarieties of logic have noticeable similarities. The paper provides a unifying framework for them which extends the BlokPigozzi theory of elementarily algebraizable (and protoalgebraic) deductive systems. In this extension there are two parameters: a set of terms and a variable. When the former is empty or consists of theorems, the BlokPigozzi theory is recovered, and the variable is redundant. On the other hand, a class of ‘membership logics’ is obtained when the variable is the only element of the set of terms. For these systems the appropriate variant of equivalent algebraic semantics encompasses the relatively congruence regular quasivarieties.
more …
By
Pałasińska, Katarzyna
7 Citations
We show that a finitely generated protoalgebraic strict universal Horn class that is filterdistributive is finitely based. Equivalently, every protoalgebraic and filterdistributive multidimensional deductive system determined by a finite set of finite matrices can be presented by finitely many axioms and rules.
more …
By
Blok, W. J.; Rebagliato, J.
16 Citations
The notion of an algebraic semantics of a deductive system was proposed in [3], and a preliminary study was begun. The focus of [3] was the definition and investigation of algebraizable deductive systems, i.e., the deductive systems that possess an equivalent algebraic semantics. The present paper explores the more general property of possessing an algebraic semantics. While a deductive system can have at most one equivalent algebraic semantics, it may have numerous different algebraic semantics. All of these give rise to an algebraic completeness theorem for the deductive system, but their algebraic properties, unlike those of equivalent algebraic semantics, need not reflect the metalogical properties of the deductive system. Many deductive systems that don't have an equivalent algebraic semantics do possess an algebraic semantics; examples of these phenomena are provided. It is shown that all extensions of a deductive system that possesses an algebraic semantics themselves possess an algebraic semantics. Necessary conditions for the existence of an algebraic semantics are given, and an example of a protoalgebraic deductive system that does not have an algebraic semantics is provided. The monounary deductive systems possessing an algebraic semantics are characterized. Finally, weak conditions on a deductive system are formulated that guarantee the existence of an algebraic semantics. These conditions are used to show that various classes of nonalgebraizable deductive systems of modal logic, relevance logic and linear logic do possess an algebraic semantics.
more …
By
Siebel, Mark
11 Citations
In the classic Linguistic Communication and Speech Acts,Kent Bach and Robert M. Harnish advocated the idea that to perform an illocutionary actoften just means to express certain attitudes. The underlying definition of attitudeexpression, however, gives rise to serious problems because it requires intentions of a peculiarkind. Recently, Wayne Davis has proposed a different analysis of attitude expression whichis not subject to these difficulties and thus promises a more plausible account of illocutions.It will be shown, however, that this account is too weak since it does not exclude cases wherethe utterer merely pretends to perform an illocutionary act. Davis' analysis also callsinto question a weaker doctrine widely held among speech act theorists by suggesting that, inorder to perform an illocutionary act, it is not even necessary to express mental states.
more …
By
Hoover, David L.
34 Citations
This article examines the usefulness ofvocabulary richness for authorship attributionand tests the assumption that appropriatemeasures of vocabulary richness can capture anauthor's distinctive style or identity. Afterbriefly discussing perceived and actualvocabulary richness, I show that doubling andcombining texts affects some measures incomputationally predictable but conceptuallysurprising ways. I discuss some theoretical andempirical problems with some measures anddevelop simple methods to test how wellvocabulary richness distinguishes texts bydifferent authors. These methods show thatvocabulary richness is ineffective for largegroups of texts because of the extremevariability within and among them. I concludethat vocabulary richness is of marginal valuein stylistic and authorship studies because thebasic assumption that it constitutes awordprint for authors is false.
more …
By
Harvey, J.T.
4 Citations
GIS methodology was used for thepurpose of locating the disputed site of ahistorically significant battle, which tookplace in 1854 when miners on an Australian goldfield staged an armed uprising againstgovernment forces. The route of the firstsurvey of the area (1854) and the earliestknown contour map (1856–1857) were overlaid on amodern street grid. Other features such as thevantage points of illustrators and the authorsof eyewitness accounts were also incorporated. The resulting composite map was used as the keyreference framework for comparing andcritically evaluating a large body of primaryand secondary written accounts, and forreaching a conclusion concerning the site.
more …
By
Tabov, Jordan
In their papers, Kalashnikov et al. (1986),Rachev et al. (1989) and Fomenko et al. (1990)introduced the socalled “volumefunction” describing the chronologicaldistribution of information in historical texts. Here we give anotherapproach to constructing similar functions.
more …
By
Härnqvist, Kjell; Christianson, Ulf; Ridings, Daniel; Tingsell, JanGunnar
Show all (4)
3 Citations
Responses in personalinterviews about education and career with 415Swedish men and women (age 34) forms the basisof a speech corpus with 1.8 million words. Thevocabulary is described by means of two sets ofvariables. One is based on the number of tokensand types, word length and sectioning of therunning text. The other set divides the corpusinto grammatical categories. Both sets ofvariables are related to a number of backgroundvariables such as gender, socioeconomicbackground, education, and indicators of verbalproficiency at age 13 and 32. This possibilityto study the relationship between vocabularyand a broad set of respondent characteristicsis a unique feature of this corpus.
more …
By
Dinu, Liviu P.
1 Citations
We propose and study a model of the graphical syllable using Marcus contextual grammars. For this purpose we introduce two new variants of Marcus contextual grammars: total Marcus contextual grammar with total leftmost derivation, and total Marcus contextual grammar with total leftmost derivation constrained by maximal use of selectors.
more …
