Lautemann et al. (1995) gave a descriptive characterisation of the class of context-free languages, showing that a language is context-free iff it is definable as the set of words satisfying some sentence of a particular logic (fragment) over words. The present notes discuss how to specialise this result to the class of linear languages. Somewhat surprisingly, what would seem the most straightforward specialisation actually fails, due to the fact that linear grammars fail to admit a Greibach (...) normal form. We identify an alternative specialisation, based on an alternative characterisation of context-free languages, also noted by Lautemann et al. (1995). (shrink)

The papers collected in this volume exemplify some of the trends in current approaches to logic, language and computation. Written by authors with varied academic backgrounds, the contributions are intended for an interdisciplinary audience. The first part of this volume addresses issues relevant for multi-agent systems: reasoning with incomplete information, reasoning about knowledge and beliefs, and reasoning about games. Proofs as formal objects form the subject of Part II. Topics covered include: contributions on logical frameworks, linear logic, and different (...) approaches to formalized reasoning. Part III focuses on representations and formal methods in linguistic theory, addressing the areas of comparative and temporal expressions, modal subordination, and compositionality. (shrink)

Punctured languages are languages whose words are partial words in the sense that the letters at some positions are unknown. We investigate to which extent restoration of punctured languages is possible if the number of unknown positions or the proportion of unknown positions per word, respectively, is bounded, and we study their relationships for different boundings. The considered restoration classes coincide with similarity classes according to some kind of similarity for languages. Thus all results we can (...) also formulate in the language of similarity. We show some hierarchies of similarity classes for each class from the Chomsky hierarchy and prove the existence of linear languages which are not δ -similar to any regular language for any δ < ½. For δ ≥ ½ this is unknown but it could only be possible in the case of non-slender linear languages. (shrink)

This paper presents an approach to artificial intelligence planning based on linear temporal logic (LTL). A simple and easy-to-use planning language is described, Planning Domain Description Language with control Knowledge (PDDL-K), which allows one to specify a planning problem together with heuristic information that can be of help for both pruning the search space and finding better quality plans. The semantics of the language is given in terms of a translation into a set of LTL formulae. Planning is then (...) reduced to “executing” the LTL encoding, i.e. to model search in LTL. The feasibility of the approach has been successfully tested by means of the system Pdk, an implementation of the proposed method. (shrink)

The natural epistemology of W. V. Quine has not been well understood. Critics argue that Quine's scientific approach to epistemology is circular and fails to be normative, yet these criticisms tend to be based on the very presuppositions concerning language, theory, and epistemology that Quine is at pains to reject or alter. ;Quine's views on the meaningfulness of language use imply a breakdown in the dichotomy between language as a theoretically neutral instrument and theory as the commitment to some subset (...) of the sentences allowed by a language. This breakdown, and the view of language which drives it, result in Quine's doctrine that speaking a language involves substantial theoretical commitments, and that inquiry must begin from within some ongoing theory of the world. That is, our epistemic practices, including epistemology itself, must be globally circular. The traditionally fundamental norm of linear propositional support, which drives the circularity objection, is thus seen as based in a misconception of language and theory. This not only explains Quine's lack of concern with the circularity of his view, but also illuminates the fundamental motivation for his general naturalism. ;Natural epistemology cannot be normative in the traditional sense of providing an independent ground for science. However, having accepted the "terminal parameter" of prediction as the test of theory, normativity becomes a matter of describing which procedures best promote predictively successful theory. Thus, epistemic norms emerge from science as hypotheses concerning the effectiveness of various methods in promoting predictively successful theory. Not only can natural epistemology prescribe and proscribe various epistemic practices, it offers the promise of an explanatory understanding of the strengths and weaknesses of those practices. Based on this understanding, natural epistemology further involves the improvement of current practices and the development of new ones. Crucial to this reconception of epistemology is the reconception of the knower as an adaptive organism employing the language/theory complex as an adaptive tool for interacting with the environment. ;The naturalism/anti-naturalism debate is advanced by acknowledging the substantial theoretical commitments implicit in the traditional view, and by examining Quine's reconception of language, theory, and the human knowing subject. (shrink)

I present a semantics for the language of first-order additive-multiplicative linear logic, i.e. the language of classical first-order logic with two sorts of disjunction and conjunction. The semantics allows us to capture intuitions often associated with linear logic or constructivism such as sentences = games, SENTENCES = resources or sentences = problems, where “truth” means existence of an effective winning strategy.The paper introduces a decidable first-order logic ET in the above language and gives a proof of its soundness (...) and completeness with respect to this semantics. Allowing noneffective strategies in the latter is shown to lead to classical logic.The semantics presented here is very similar to Blass's game semantics. Although there is no straightforward reduction between the two corresponding notions of validity, my completeness proof can likely be adapted to the logic induced by Blass's semantics to show its decidability, which was the main problem left open in Blass's paper.The reader needs to be familiar with classical logic and arithmetic. (shrink)

Recent work in natural language semantics leads to some new observations on generalized quantifiers. In § 1 we show that English quantifiers of type $ $ are booleanly generated by their generalized universal and generalized existential members. These two classes also constitute the sortally reducible members of this type. Section 2 presents our main result--the Generalized Prefix Theorem (GPT). This theorem characterizes the conditions under which formulas of the form Q1x 1⋯ Qnx nRx 1⋯ xn and q1x 1⋯ qnx nRx (...) 1⋯ xn are logically equivalent for arbitrary generalized quantifiers Qi, qi. GPT generalizes, perhaps in an unexpectedly strong form, the Linear Prefix Theorem (appropriately modified) of Keisler & Walkoe (1973). (shrink)

A number of general points behind the story of this paper may be worth setting out separately, now that we have come to the end.There is perhaps one obvious omission to be addressed right away. Although the word “information” has occurred throughout this paper, it must have struck the reader that we have had nothing to say on what information is. In this respect, our theories may be like those in physics: which do not explain what “energy” is (a notion (...) which seems quite similar to “information” in several ways), but only give some basic laws about its behaviour and transmission.The eventual recommendation made here has been to use a broad type-theoretic framework for studying various more classical and more dynamic notions of proposition in their interaction. This is not quite the viewpoint advocated by many current authors in the area, who argue for a whole-sale switch from a ‘static’ to a ‘dynamic’ perspective on propositions. This is not the place, however, to survey the conceptual arguments for and against such a more radical move.This still leaves many questions about possible reductions from one perspective to another. For instance, it would seem that classical systems ought to serve as a ‘limiting case’, which should still be valid after procedural details of some cognitive process have been forgotten. There are various ways of implementing the desired correspondence: e.g. by considering extreme cases with ⫅ equal to identity, or, in the pure relational algebra framework by considering only pairs (x, x). What we shall want then are reductions of dynamic logics, in those special cases, to classical logic. But perhaps also, more sophisticated views are possible. How do we take a piece of ‘dynamic’ prose, remove control instructions and the like, and obtain a piece of ‘classical’ text, suitable for inference ‘in the light of eternity’?There is also a more technical side to the matter of ‘reduction’. By now, Logic has reached such a state of ‘inter-translatability’ that almost all known variant logics can be embedded into each other, via suitable translations. In particular, once an adequate semantic has been given for a new system, this usually induces an embedding into standard logic: as we know, e.g., for the case of Modal Logic. Like-wise, all systems of dynamic interpretation or inference proposed so far admit of direct embedding into an ordinary ‘static’ predicate logic having explicit transition predicates (cf. van Benthem 1988b). Thus, our moral is this. The issue is not whether the new systems of information structure or processing are essentially beyond the expressive resources of traditional logical systems: for, they are not. The issue is rather which interesting phenomena and questions will be put into the right focus by them.The next broad issue concerns the specific use of the perspective proposed here, vis-à-vis concrete proposals for information-oriented or dynamic semantics. The general strategy advocated here is to locate some suitable base calculus and then consider which ‘extras’ are peculiar to the proposal. For instance, this is the spirit in which modal S4 would be a base logic of information models, and intuitionistic logicthe special theory devoting itself to upward persistent propositions. Or, with the examples in Section 4.1, the underlying base logic is our relational algebra, whereas, say, ordinary updates then impose special properties, such as ‘idempotence’: $$xRy \Rightarrow yRy$$ Does this kind of application presuppose the existence of one distinguished base logic, of which all others are extensions? This would be attractive-and some form of relational algebra or linear logic might be a reasonable candidate. Nevertheless, the enterprise does not rest on this outcome. What matters is an increased sensitivity to the ‘landscape’ of dynamic logics, just as with the ‘Categorial Hierarchy’ in Categorial Grammar (cf. van Benthem 1989a, 1991) where the family of logics with their interconnections seems more important than any specific patriarch.Finally, perhaps the most important issue in the new framework is the possibility of new kinds of questions arising precisely because of its differences from standard logic. Notably, given the option of regarding propositions as programs, it will be of interest to consider systematically which major questions about programming languages now make sense inside logic too.EXAMPLE. Correctness. When do we have $$\left[\kern-0.15em\left[ \pi \right]\kern-0.15em\right](\left[\kern-0.15em\left[ A \right]\kern-0.15em\right]) \subseteq \left[\kern-0.15em\left[ B \right]\kern-0.15em\right]$$ for (s, t) propositions A, B and a dynamic (s, (s, t)) proposition π?Program Synthesis. Which dynamic proposition will take us from an information state satisfying A to one satisfying B? (This question needs refinement, lest there be trivial answers.)Determinism. Which propositions as programs are deterministic, in the sense of defining single-valued functions from states to states?Querying. What does it mean to ask for information in the present setting? (Again, individual types referring to e will be crucial here.)This is not merely an agenda for wishful thinking. Within Logic, there are various ways of introducing such concerns into semantics, especially, using tools from Automata Theory. (See van Benthem 1989c for further discussion of such computational perspectives in ‘cognitive programming’.)At least if one believes that ‘dynamics’ is of the essence in cognition (rather than a mere interfacing problem between the halls of eternal truth and the noisy streets of reality), the true test for the present enterprise is the development of a significant new research program not merely copying the questions of old. (shrink)

The aim of this paper is to point out the equivalence between three notions respectively issued from recursion theory, computational complexity and finite model theory. One the one hand, the rudimentary languages are known to be characterized by the linear hierarchy. On the other hand, this complexity class can be proved to correspond to monadic second‐order logic with addition. Our viewpoint sheds some new light on the close connection between these domains: We bring together the two extremal notions (...) by providing a direct logical characterization of rudimentary languages and a representation result of second‐order logic into these languages. We use natural arithmetical tools, and our proofs contain no ingredient from computational complexity. (shrink)

We examined the role of fitness, commonly assumed without proof to be conferred by the mastery of language, in shaping the dynamics of language evolution. To that end, we introduced island migration (a concept borrowed from population genetics) into the shared lexicon model of communication (Nowak et al., 1999). The effect of fitness linear in language coherence was compared to a control condition of neutral drift. We found that in the neutral condition (no coherence-dependent fitness) even a small migration (...) rate – less than 1% – suffices for one language to become dominant, albeit after a long time. In comparison, when fitness-based selection is introduced, the subpopulations stabilize quite rapidly to form several distinct languages. Our findings support the notion that language confers increased fitness. The possibility that a shared language evolved as a result of neutral drift appears less likely, unless migration rates over evolutionary times were extremely small. (shrink)

The American Sign Language Sentence Reproduction Test (ASL-SRT) requires the precise reproduction of a series of ASL sentences increasing in complexity and length. Error analyses of such tasks provides insight into working memory and scaffolding processes. Data was collected from three groups expected to differ in fluency: deaf children, deaf adults and hearing adults, all users of ASL. Quantitative (correct/incorrect recall) and qualitative error analyses were performed. Percent correct on the reproduction task supports its sensitivity to fluency as test performance (...) clearly differed across the three groups studied. A linguistic analysis of errors further documented differing strategies and bias across groups. Subjects' recall projected the affordance and constraints of deep linguistic representations to differing degrees, with subjects resorting to alternate processing strategies when they failed to recall the sentence correctly. A qualitative error analysis allows us to capture generalizations about the relationship between error pattern and the cognitive scaffolding, which governs the sentence reproduction process. Highly fluent signers and less-fluent signers share common chokepoints on particular words in sentences. However, they diverge in heuristic strategy. Fluent signers, when they make an error, tend to preserve semantic details while altering morpho-syntactic domains. They produce syntactically correct sentences with equivalent meaning to the to-be-reproduced one, but these are not verbatim reproductions of the original sentence. In contrast, less-fluent signers tend to use a more linear strategy, preserving lexical status and word ordering while omitting local inflections, and occasionally resorting to visuo-motoric imitation. Thus, whereas fluent signers readily use top-down scaffolding in their working memory, less fluent signers fail to do so. Implications for current models of working memory across spoken and signed modalities are considered. (shrink)

This paper presents a novel approach to the unsupervised learning of syntactic analyses of natural language text. Most previous work has focused on maximizing likelihood according to generative PCFG models. In contrast, we employ a simpler probabilistic model over trees based directly on constituent identity and linear context, and use an EM-like iterative procedure to induce structure. This method produces much higher quality analyses, giving the best published results on the ATIS dataset.

A large body of psycholinguistic research demonstrates that both language processing and language acquisition are sensitive to the distributions of linguistic constructions in usage. Here we investigate how statistical distributions at different linguistic levels – morphological and lexical (Experiments 1 and 2), and phrasal (Experiment 2) – contribute to the ease with which morphosyntax is processed and produced by second language learners. We analyze Chinese ESL learners’ knowledge of four English inflectional morphemes:-ed,-ing, and third-person-son verbs, and plural-son nouns. In Elicited (...) Imitation Tasks, participants listened to length- and difficulty-matched sentences each containing one target morpheme and typed the whole sentence as accurately as they could after a short delay. Experiment 1 investigated lexical and morphemic levels, testing the hypotheses that a morpheme is expected to be more easily processed when it is (1) highlyavailable(i.e., occurring in frequent word-forms), and (2) highlyreliable(i.e., occurring in lemma words that are consistently conjugated in the form containing this morpheme). Thirty sentences were made for each morpheme, divided into three Availability-Reliability Distribution (ARD) groups on the basis of corpus analysis in the Corpus of Contemporary American English (COCA;Davies, 2008-): 10 target words high in availability, 10 high in reliability, and 10 low in both reliability and availability. Responses were scored on whether the target morpheme was accurately reproduced given the provision of the correct lemma. A generalized linear mixed-effects logit model (GLMM) revealed fixed effects of morpheme type, availability, and reliability on the accuracy of morpheme provision. There were no effects of lemma frequency. Experiment 2 successfully replicated these results and extended the investigation to explore phrasal formulaicity by manipulating the frequency of the four-word strings in which the morpheme was embedded. GLMMs replicated the effects of word-form availability and reliability and additionally revealed independentphrase-superiority effectswhere morphemes were better reproduced in contexts of higher string-frequency. Taken together, these findings demonstrate that morpheme acquisition reflects the distributional properties of learners’ experience and the mappings therein between lexis, morphology, phraseology, and semantics. These conclusions support an emergentist view of the statistical symbolic learning of morphology where language acquisition involves the satisfaction of competing constraints across multiple grain-sizes of units. (shrink)

The notion of language in e-Learning is still not very clear from a technical as well as semantic point of view. In the era of Information Technology, it is more and more important to unify the principles of language used and its semantic meaning to be more simple and precise when taking into consideration online educational courses. During the last years, e-Learning courses have begun to be popular around the world as during an internet era, we tend to find consolidated (...) information sources on internet rather than in traditional courses which require our physical presence. The crucial issue which makes an e- Learning course function is the language used to transmit all the information to the students in a clear and effective manner. For such language to be considered effective, it is necessary to adjust it to the general standards adopted in an international environment. The notion of a language used in e-Learning also faces some problems as it should be so concise as to be accessible for everybody regardless of gender, nationality, and intellectual level. It is hard to standardise its principles, thus over the years many scientists have tried to unify the top requirements a perfect e-Learning course should have. Nowadays, most of the population should stop considering e-Learning as an alternative form of education and focus on developing new models and structures for education and learning that fully exploit the opportunities of today’s digital revolution. With a laptop, a mobile device and Wi-Fi, you can manage your own e-Learning course, and take courses yourself, at any time and place, in any language. A typical model of an e-Learning course is based on guided self-study with a linear progression through modules consisting of recorded lectures, course literature, written assignments and multiple-choice self-tests. Technology has got an even better solution which consists of standardising the learning process and adopting it to a commonly known level of difficulty which might be expected when considering its use by an average person. (shrink)

Any approach to the study of managerial situations undertaken without reflection on the underpinning philosophy is flawed because it limits our ability to question the validity of the knowledge claimed in the analysis. The paper considers this issue and presents a philosophical reflection on the use of a systems approach to the modelling of human enterprises. It draws on insights from systems thinking, cognitive science, autopoiesis, communication theory and non-linear dynamics. These are interpreted within the context of social systems (...) as networks of conversations that are generated in language. It is written to invite an exchange of ideas concerning the role of the generative dialogue. (shrink)

Previous studies provided evidence for a connection between language processing and language change. We add to these studies with an exploration of the influence of lexical-distributional properties of words in orthographic space, semantic space, and the mapping between orthographic and semantic space on the probability of lexical extinction. Through a binomial linear regression analysis, we investigated the probability of lexical extinction by the first decade of the twenty-first century (2000s) for words that existed in the first decade of the (...) nineteenth-century (1800s) in eight data sets for five languages: English, French, German, Italian, and Spanish. The binomial linear regression analysis revealed that words that are more similar in form to other words are less likely to disappear from a language. By contrast, words that are more similar in meaning to other words are more likely to become extinct. In addition, a more consistent mapping between form and meaning protects a word from lexical extinction. A nonlinear time-to-event analysis furthermore revealed that the position of a word in orthographic and semantic space continues to influence the probability of it disappearing from a language for at least 200 years. Effects of the lexical-distributional properties of words under investigation here have been reported in the language processing literature as well. The results reported here, therefore, fit well with a usage-based approach to language change, which holds that language change is at least to some extent connected to cognitive mechanisms in the human brain. (shrink)

Einleitung, Zwischen Sprache und Denken / Alex Burri -- Linearity and structure / Peter Simons -- The role of language in intelligence / Daniel C. Dennett -- Die Fiktion einer Sprache des Geistes in der zeitgenössischen Philosophie / Katia Saporiti -- Ist eine Sprache des Geistes möglich? / Ansgar Beckermann -- Searles chinesischer Zauber oder Wahrnehmung, Sprachverständnis und der Turing-Test / Wolfgang Lenzen -- On determining reference / Michael Devitt -- How perception fixes reference / Kevin Mulligan -- Rede zwischen (...) Aktion und Kognition / Kuno Lorenz -- Die kausale Relevanz des Geistigen / Thomas Ruprecht -- Kantian schemata and the unity of perception / Jay F. Rosenberg -- Der sichtbare Geist / Gérard Bornet -- Intention und Kognition / Dieter Münch -- Zur sog. Naturalisierung von Intentionalität / Andreas Kemmerling -- Thinking that one thinks / David M. Rosenthal -- The nature of thought / Fred Dretske -- Sprache und Wahrheit / Josef Seifert -- Anschauliches und symbolisches Denken / Andreas Kamlah -- Logisches und analogisches Denken / Gottfried Gabriel. (shrink)

Cross-linguistic evidence from widespread modes of language variation and change demonstrate that language evolution proceeds (at least in part, perhaps in whole) by breaking and renewing symmetrical patterns. Since this activity is identified with semiosis (Nöth 1994, 1998), these patterns-in-process establish further grounds for insisting that the science of language be more adequately situated within semiotic understanding as “an ideoscopic science and sub-discipline under the general doctrine of signs” (Deely 2012: 334). After summarizing the theoretical context of my thesis, including (...) relationships between analogy, symmetry, and linguistic diagrammatization, I present supporting comparative data in successive stages of complexity, ranging from simple reversals of linguistic diagrams through time to the emergence of more involved linguistic mirror patterns, to the emergence of intertwining diagrams and linguistic fractal symmetries. I then point back to the embodied and psychological sources of these patterns in the primary modeling system of the human Umwelt. The essay ends with gestures toward further unexplored sources of evidence and a summary proposal for understanding language evolution as non-linear process, qua semiosis. (shrink)

Group size is a function of relative neocortical volume in nonhuman primates. Extrapolation from this regression equation yields a predicted group size for modern humans very similar to that of certain hunter-gatherer and traditional horticulturalist societies. Groups of similar size are also found in other large-scale forms of contemporary and historical society. Among primates, the cohesion of groups is maintained by social grooming; the time devoted to social grooming is linearly related to group size among the Old World monkeys and (...) apes. To maintain the stability of the large groups characteristic of humans by grooming alone would place intolerable demands on time budgets. It is suggested that (1) the evolution of large groups in the human lineage depended on the development of a more efficient method for time-sharing the processes of social bonding and that (2) language uniquely fulfills this requirement. Data on the size of conversational and other small interacting groups of humans are in line with the predictions for the relative efficiency of conversation compared to grooming as a bonding process. Analysis of a sample of human conversations shows that about 60% of time is spent gossiping about relationships and personal experiences. It is suggested that language evolved to allow individuals to learn about the behavioural characteristics of other group members more rapidly than is possible by direct observation alone. (shrink)

The paper develops Lambda Grammars, a form of categorial grammar that, unlike other categorial formalisms, is non-directional. Linguistic signs are represented as sequences of lambda terms and are combined with the help of linear combinators.

In recent years we have seen a dramatic shift, in several different areas of communication studies, from an information-theoretic to a dynamic systems paradigm. In an information processing system, communication, whether between cells, mammals, apes, or humans, is said to occur when one organism encodes information into a signal that is transmitted to another organism that decodes the signal. In a dynamic system, all of the elements are continuously interacting with and changing in respect to one another, and an aggregate (...) pattern emerges from this mutual co-action. Whereas the information-processing paradigm looks at communication as a linear, binary sequence of events, the dynamic systems paradigm looks at the relation between behaviors and how the whole configuration changes over time. One of the most dramatic examples of the significance of shifting from an information processing to a dynamic systems paradigm can be found in the debate over the interpretation of recent advances in ape language research (ALR). To some extent, many of the early ALR studies reinforced the stereotype that animal communication is functional and stimulus bound, precisely because they were based on an information-processing paradigm that promoted a static model of communicative development. But Savage-Rumbaugh's recent results with bonobos has introduced an entirely new dimension into this debate. Shifting the terms of the discussion from an information-processing to a dynamic systems paradigm not only highlights the striking differences between Savage-Rumbaugh's research and earlier ALR studies, but further, it sheds illuminating light on the factors that underpin the development of communication skills in great apes and humans, and the relationship between communicative development and the development of language. Key Words: apes; ape language research (ALR); brain development; co-regulation; communication; dynamic systems; language development; symbols. (shrink)

The present study analyzes the English diaries written by a young Chinese English as a foreign language learner over a 1-year period in an attempt to determine the developmental process of Chinese EFL young learners’ written language in terms of syntactic complexity. This study aimed to use a wide range of metrics to explore densely collected data based on Dynamic Systems Theory. The longitudinal study data were analyzed through eight large-grained measures related to sentential, clausal, and phrasal features by using (...) L2 Syntactic Complexity Analyzer, as well as fine-grained measures related to seven modifiers, an adjective placed before a noun, ordinal numerals are indicated, cardinal numeral, predicative adjective, adverbial adjective, adverbs, prepositional phrases, subordinate, and relative clause, through manual annotations. The results show that, first, the developmental process was not linear but spiral in terms of large-grained measures. The sentential level varied, and the development process of the young learner is different from Chinese English learners studying in colleges. Second, the dynamic features of fine-grained measures are also prominent in the seven indicators. ADJA, PREP, and REL showed a steady increase, ADJP showed an obvious decline, while ADV and SUB first increased and then declined. Third, the correlation analysis revealed a competitive interaction within fine-grained measures and between large-grained and fine-grained measures. (shrink)

This paper implements the continuous Hindi Automatic Speech Recognition (ASR) system using the proposed integrated features vector with Recurrent Neural Network (RNN) based Language Modeling (LM). The proposed system also implements the speaker adaptation using Maximum-Likelihood Linear Regression (MLLR) and Constrained Maximum likelihood Linear Regression (C-MLLR). This system is discriminatively trained by Maximum Mutual Information (MMI) and Minimum Phone Error (MPE) techniques with 256 Gaussian mixture per Hidden Markov Model(HMM) state. The training of the baseline system has been (...) done using a phonetically rich Hindi dataset. The results show that discriminative training enhances the baseline system performance by up to 3%. Further improvement of ~7% has been recorded by applying RNN LM. The proposed Hindi ASR system shows significant performance improvement over other current state-of-the-art techniques. (shrink)

Linguistic category learning has been shown to be highly sensitive to linear order, and depending on the task, differentially sensitive to the information provided by preceding category markers (premarkers, e.g., gendered articles) or succeeding category markers (postmarkers, e.g., gendered suffixes). Given that numerous systems for marking grammatical categories exist in natural languages, it follows that a better understanding of these findings can shed light on the factors underlying this diversity. In two discriminative learning simulations and an artificial language (...) learning experiment, we identify two factors that modulate linear order effects in linguistic category learning: category structure and the level of abstraction in a category hierarchy. Regarding category structure, we find that postmarking brings an advantage for learning category diagnostic stimulus dimensions, an effect not present when categories are non‐confusable. Regarding levels of abstraction, we find that premarking of super‐ordinate categories (e.g., noun class) facilitates learning of subordinate categories (e.g., nouns). We present detailed simulations using a plausible candidate mechanism for the observed effects, along with a comprehensive analysis of linear order effects within an expectation‐based account of learning. Our findings indicate that linguistic category learning is differentially guided by pre‐ and postmarking, and that the influence of each is modulated by the specific characteristics of a given category system. (shrink)

Temporal propositions are mapped to sets of strings that witness (in a precise sense) the propositions over discrete linear Kripke frames. The strings are collected into regular languages to ensure the decidability of entailments given by inclusions between languages. (Various notions of bounded entailment are shown to be expressible as language inclusions.) The languages unwind computations implicit in the logical (and temporal) connectives via a system of finite-state constraints adapted from finite-state morphology. Applications to Hybrid Logic (...) and non-monotonic inertial reasoning are briefly considered. (shrink)

Linguistic category learning has been shown to be highly sensitive to linear order, and depending on the task, differentially sensitive to the information provided by preceding category markers (premarkers, e.g., gendered articles) or succeeding category markers (postmarkers, e.g., gendered suffixes). Given that numerous systems for marking grammatical categories exist in natural languages, it follows that a better understanding of these findings can shed light on the factors underlying this diversity. In two discriminative learning simulations and an artificial language (...) learning experiment, we identify two factors that modulate linear order effects in linguistic category learning: category structure and the level of abstraction in a category hierarchy. Regarding category structure, we find that postmarking brings an advantage for learning category diagnostic stimulus dimensions, an effect not present when categories are non‐confusable. Regarding levels of abstraction, we find that premarking of super‐ordinate categories (e.g., noun class) facilitates learning of subordinate categories (e.g., nouns). We present detailed simulations using a plausible candidate mechanism for the observed effects, along with a comprehensive analysis of linear order effects within an expectation‐based account of learning. Our findings indicate that linguistic category learning is differentially guided by pre‐ and postmarking, and that the influence of each is modulated by the specific characteristics of a given category system. (shrink)

This paper investigates logical aspects of combining linear orders as semantics for modal and temporal logics, with modalities for possible paths, resulting in a variety of branching time logics over classes of trees. Here we adopt a unified approach to the Priorean, Peircean and Ockhamist semantics for branching time logics, by considering them all as fragments of the latter, obtained as combinations, in various degrees, of languages and semantics for linear time with a modality for possible paths. (...) We then consider a hierarchy of natural classes of trees and bundled trees arising from a given class of linear orders and show that in general they provide different semantics. We also discuss transfer of definability from linear orders to trees and introduce a uniform translation from Priorean to Peircean formulae which transfers definability of properties of linear orders to definability of properties of all paths in trees. (shrink)

We present the propositional logic LEC for the two epistemic modalities of current and stable knowledge used by an agent who system-atically enriches his language. A change in the linguistic resources of an agent as a result of certain cognitive processes is something that commonly happens. Our system is based on the logic LC intended to formalize the idea that the occurrence of changes induces the passage of time. Here, the primitive operator C read as: it changes that, defines the (...) temporal succession of states of the world. The notion of current knowledge concerns variable components of the world and it may change over time. We represent it by the primitive operator k read as: the agent currently knows that, and assume that it has S5 properties. The second type of knowledge, symbolized by the primitive operator K read as: the agent stably knows that, relates to constant components of the world and it does not change. As a result of the axiomatic entanglement of C, K and k we show that stable knowledge satisfies axioms of S4.3. K and k modalities are not mutually definable, stable knowledge implies the current one and if the latter never changes, then it comes to be stable. The combination of K and k with the idea of an expanding language allows questioning of the so-called perfect recall principle. It cannot be maintained for both types of knowledge just because of changes in the vocabulary of the agent and possibly the growing spectrum of possible states of the world. We interpret LEC in the semantics of histories of epistemic changes and show that it is complete. Finally, we compare our logic with selected epistemic logics based on the concept of linear discrete time. (shrink)

Spanning the period between Wittgenstein's return to Cambridge in 1929 and the first version of Philosophical Investigations in 1936, Piotr Dehnel explores the middle stage in Ludwig Wittgenstein's philosophical development and identifies the major issues which engrossed him, including phenomenology, philosophy of mathematics and philosophy of language. Contrary to the dominant perspective, Dehnel argues that this period was intrinsically different from the early and late stages and should not be viewed as a mere transitional phase. The distinctiveness of Wittgenstein's middle (...) work can be seen in his philosophical thinking as it unfolds in a non-linear trajectory: thoughts do not follow upon each other, ideas do not appear sequentially one by one, and insights do not form a straight chain. Dehnel portrays the diffused and multifarious quality of Wittgenstein's middle thinking, enabling readers to form a more comprehensive view of his entire philosophy and acquire a better grasp of his conceptual trajectory, complete with the intricacies and challenges that it poses. (shrink)

This paper develops a proof theory for logical forms of proofs in the case of monadic languages. Among the consequences are different kinds of generalization of proofs in various schematic proof systems. The results use suitable relations between logical properties of partial proof data and algebraic properties of corresponding sets of linear diophantine equations.

A Linear Logic automaton is a hybrid of a finite automaton and a non-deterministic Petri net. LL automata commands are represented by propositional Horn Linear Logic formulas. Computations performed by LL automata directly correspond to cut-free derivations in Linear Logic.A programming language of LL automata is developed in which typical sequential, non-deterministic and parallel programming constructs are expressed in the natural way.All non-deterministic computations, e.g. computations performed by programs built up of guarded commands in the Dijkstra's approach (...) to non-deterministic programming, are directly simulated within the framework of Linear Logic automata, and thereby within the Horn framework of Linear Logic. (shrink)

Online trading invariably involves dealings between strangers, so it is important for one party to be able to judge objectively the trustworthiness of the other. In such a setting, the decision to trust a user may sensibly be based on that user’s past behaviour. We introduce a specification language based on linear temporal logic for expressing a policy for categorising the behaviour patterns of a user depending on its transaction history. We also present an algorithm for checking whether the (...) transaction history obeys the stated policy. To be useful in a real setting, such a language should allow one to express realistic policies which may involve parameter quantification and quantitative or statistical patterns. We introduce several extensions of linear temporal logic to cater for such needs: a restricted form of universal and existential quantification; arbitrary computable functions and relations in the term language; and a “counting” quantifier for counting how many times a formula holds in the past. We then show that model checking a transaction history against a policy, which we call the history-based transaction monitoring problem, is PSPACE-complete in the size of the policy formula and the length of the history, assuming that the underlying interpreted func-. (shrink)

Levesque et al. have defined a programming language, Golog, in order to reason about complex actions within the framework of the situation calculus. We build on previous work of ours and show how to translate Golog into linear logic, suitably augmented.

We show that linear logic can serve as an expressive framework in which to model a rich variety of combinatorial auction mechanisms. Due to its resource-sensitive nature, linear logic can easily represent bids in combinatorial auctions in which goods may be sold in multiple units, and we show how it naturally generalises several bidding languages familiar from the literature. Moreover, the winner determination problem, i.e., the problem of computing an allocation of goods to bidders producing a certain (...) amount of revenue for the auctioneer, can be modelled as the problem of finding a proof for a particular linear logic sequent. (shrink)

The λσ-calculus adds explicit substitutions to the λ-calculus so as to provide a theoretical framework within which the implementation of functional programming languages can be studied. This paper generalises the λσ-calculus to provide a linear calculus of explicit substitutions, called xDILL, which analogously describes the implementation of linear functional programming languages.Our main observation is that there are non-trivial interactions between linearity and explicit substitutions and that xDILL is therefore best understood as a synthesis of its underlying (...) logical structure and the technology of explicit substitutions. This is in contrast to the λσ-calculus where the explicit substitutions are independent of the underlying logical structure. (shrink)

The paper studies the logic TL(NBox+-wC) – logic of discrete linear time with current time point clusters. Its language uses modalities Diamond+ (possible in future) and Diamond- (possible in past) and special temporal operations, – Box+w (weakly necessary in future) and Box-w (weakly necessary in past). We proceed by developing an algorithm recognizing theorems of TL(NBox+-wC), so we prove that TL(NBox+-wC) is decidable. The algorithm is based on reduction of formulas to inference rules and converting the rules in special (...) reduced normal form, and, then, on checking validity of such rules in models of singleexponential size in the rules. Also we consider the admissibility problem for TL(NBox+-wC) and show how to reduce the problem for admissibility to the decidability of TL(NBox+-wC) itself using definable universal modalities. (shrink)

This short enquiry investigates the relationships between knowledge of English and attitude towards the English language as held by Japanese university students. The goal of this study was to gain a better understanding of how attitude affects the learning of English and whether gender or geographic location of a student ’s hometown plays a role. A random sample of 85 participants completed a 26 item questionnaire which measured background information, attitude to English and knowledge of English. The difference in English (...) knowledge over several prefectures was tested using ANOVA and the results indicated that there was no statistical difference observed. Difference in attitude to English between male and female students was tested using a t-test and no statistical difference was observed. Pearson Correlation was used to test for any relationship between knowledge and attitude to English, but again no statistical different relationship was found. In addition , Multiple Regression was used to determine if there was a linear relationship between knowledge of English, and the 3 variables attitude to English, gender and prefecture. Again there was no statistically significant linear relationship between these variable. (shrink)

In the dissertation we study the complexity of generalized quantifiers in natural language. Our perspective is interdisciplinary: we combine philosophical insights with theoretical computer science, experimental cognitive science and linguistic theories. -/- In Chapter 1 we argue for identifying a part of meaning, the so-called referential meaning (model-checking), with algorithms. Moreover, we discuss the influence of computational complexity theory on cognitive tasks. We give some arguments to treat as cognitively tractable only those problems which can be computed in polynomial time. (...) Additionally, we suggest that plausible semantic theories of the everyday fragment of natural language can be formulated in the existential fragment of second-order logic. -/- In Chapter 2 we give an overview of the basic notions of generalized quantifier theory, computability theory, and descriptive complexity theory. -/- In Chapter 3 we prove that PTIME quantifiers are closed under iteration, cumulation and resumption. Next, we discuss the NP-completeness of branching quantifiers. Finally, we show that some Ramsey quantifiers define NP-complete classes of finite models while others stay in PTIME. We also give a sufficient condition for a Ramsey quantifier to be computable in polynomial time. -/- In Chapter 4 we investigate the computational complexity of polyadic lifts expressing various readings of reciprocal sentences with quantified antecedents. We show a dichotomy between these readings: the strong reciprocal reading can create NP-complete constructions, while the weak and the intermediate reciprocal readings do not. Additionally, we argue that this difference should be acknowledged in the Strong Meaning hypothesis. -/- In Chapter 5 we study the definability and complexity of the type-shifting approach to collective quantification in natural language. We show that under reasonable complexity assumptions it is not general enough to cover the semantics of all collective quantifiers in natural language. The type-shifting approach cannot lead outside second-order logic and arguably some collective quantifiers are not expressible in second-order logic. As a result, we argue that algebraic (many-sorted) formalisms dealing with collectivity are more plausible than the type-shifting approach. Moreover, we suggest that some collective quantifiers might not be realized in everyday language due to their high computational complexity. Additionally, we introduce the so-called second-order generalized quantifiers to the study of collective semantics. -/- In Chapter 6 we study the statement known as Hintikka's thesis: that the semantics of sentences like ``Most boys and most girls hate each other'' is not expressible by linear formulae and one needs to use branching quantification. We discuss possible readings of such sentences and come to the conclusion that they are expressible by linear formulae, as opposed to what Hintikka states. Next, we propose empirical evidence confirming our theoretical predictions that these sentences are sometimes interpreted by people as having the conjunctional reading. -/- In Chapter 7 we discuss a computational semantics for monadic quantifiers in natural language. We recall that it can be expressed in terms of finite-state and push-down automata. Then we present and criticize the neurological research building on this model. The discussion leads to a new experimental set-up which provides empirical evidence confirming the complexity predictions of the computational model. We show that the differences in reaction time needed for comprehension of sentences with monadic quantifiers are consistent with the complexity differences predicted by the model. -/- In Chapter 8 we discuss some general open questions and possible directions for future research, e.g., using different measures of complexity, involving game-theory and so on. -/- In general, our research explores, from different perspectives, the advantages of identifying meaning with algorithms and applying computational complexity analysis to semantic issues. It shows the fruitfulness of such an abstract computational approach for linguistics and cognitive science. (shrink)

In _The Boundaries of Babel_, Andrea Moro tells the story of an encounter between two cultures: contemporary theoretical linguistics and the cognitive neurosciences. The study of language within a biological context has been ongoing for more than fifty years. The development of neuroimaging technology offers new opportunities to enrich the "biolinguistic perspective" and extend it beyond an abstract framework for inquiry. As a leading theoretical linguist in the generative tradition and also a cognitive scientist schooled in the new imaging technology, (...) Moro is uniquely equipped to explore this. Moro examines what he calls the "hidden" revolution in contemporary science: the discovery that the number of possible grammars is not infinite and that their number is biologically limited. This radical but little-discussed change in the way we look at language, he claims, will require us to rethink not just the fundamentals of linguistics and neurosciences but also our view of the human mind. Moro searches for neurobiological correlates of "the boundaries of Babel" -- the constraints on the apparent chaotic variation in human languages -- by using an original experimental design based on artificial languages. He offers a critical overview of some of the fundamental results from linguistics over the last fifty years, in particular regarding syntax, then uses these essential aspects of language to examine two neuroimaging experiments in which he took part. He describes the two neuroimaging techniques used, but makes it clear that techniques and machines do not provide interesting data without a sound theoretical framework. Finally, he discusses some speculative aspects of modern research in biolinguistics regarding the impact of the linear structure of linguistics expression on grammar, and more generally, some core aspects of language acquisition, genetics, and evolution. (shrink)

Considering the significant contribution of teachers’ professional triumph in the prosperity of students, the current study aims to investigate the existence of any relationship among three factors influencing teachers’ success: immunity, mindfulness, and engagement. Furthermore, we attempt to investigate whether English as a foreign language teachers’ immunity and mindfulness can predict their work engagement. To this end, a Likert-scale questionnaire including items on teacher immunity, mindfulness, and work engagement was distributed to 582 EFL teachers in China through the WeChat application (...) by employing a convenient sampling. To analyze the collected data, the Spearman Rho correlation index and linear multiple regression analysis are employed. The findings are that there does exist an indication of a direct relationship among EFL teachers’ immunity, mindfulness, and work engagement. Also, it is found that immunity and mindfulness can predict EFL teachers’ work engagement. The current study’s findings support the necessity of training language teachers to cope with the EFL context adversities. (shrink)

We present the model construction technique called Linear Realizability. It consists in building a category of Partial Equivalence Relations over a Linear Combinatory Algebra. We illustrate how it can be used to provide models, which are fully complete for various typed λ-calculi. In particular, we focus on special Linear Combinatory Algebras of partial involutions, and we present PER models over them which are fully complete, inter alia, w.r.t. the following languages and theories: the fragment of System (...) F consisting of ML-types, the maximal theory on the simply typed λ-calculus with finitely many ground constants, and the maximal theory on an infinitary version of this latter calculus. (shrink)

Linear arithmetics are extensions of Presburger arithmetic () by one or more unary functions, each intended as multiplication by a fixed element (scalar), and containing the full induction schemes for their respective languages. In this paper, we construct a model of the 2‐linear arithmetic (linear arithmetic with two scalars) in which an infinitely long initial segment of “Peano multiplication” on is ‐definable. This shows, in particular, that is not model complete in contrast to theories and that (...) are known to satisfy quantifier elimination up to disjunctions of primitive positive formulas. As an application, we show that, as a discretely ordered module over the discretely ordered ring generated by the two scalars, does not have the NIP, answering negatively a question of Chernikov and Hils. (shrink)

After the seminal work of Kraus, Lehmann and Magidor (formally known as the KLM approach) on conditionals and preferential models, many aspects of defeasibility in more complex formalisms have been studied in recent years. Examples of these aspects are the notion of typicality in description logic and defeasible necessity in modal logic. We discuss a new aspect of defeasibility that can be expressed in the case of temporal logic, which is the normality in an execution. In this contribution, we take (...) Linear Temporal Logic (LTL) as case study for this defeasible aspect. LTL has found extensive applications in Computer Science and Artificial Intelligence, notably as a formal framework for representing and verifying computer systems that vary over time. However, some systems may presents exceptions at some innocuous time points where they can be tolerated, or conversely, exceptions at other crucial time points where they need to be addressed. In order to ensure the reliability of such systems, we study a preferential extension of LTL, called defeasible linear temporal logic (LTL ~ ). In the first part of this paper, we show how semantics of KLM's preferential models can be integrated with LTL. We also discuss the addition of non-monotonic temporal operators as a way to formalise defeasible properties of these systems. The second part of this paper is a study of the satisfiability problem of LTL ~ sentences. Based on Sistla and Clarke's work on the complexity of the classical LTL language, we show the bounded-model property of two fragments of LTL ~ language. Moreover, we provide a procedure to check the satisfiability of sentences in both of these fragments. (shrink)

We present an overview of linear-time temporal logics with Presburger constraints whose models are sequences of tuples of integers. Such formal specification languages are well-designed to specify and verify systems that can be modelled with counter systems. The paper recalls the general framework of LTL over concrete domains and presents the main decidability and complexity results related to fragments of Presburger LTL. Related formalisms are also briefly presented.