Showing 1 to 33 of 33 matching Articles
Results per page:
Export (CSV)
By
Partee, Barbara H.; Meulen, Alice; Wall, Robert E.
In this chapter we discuss two wellknown algebras as specially structured lattices and prove some of their properties as well as present some semantic interpretations of these structures.
By
Partee, Barbara H.; Meulen, Alice; Wall, Robert E.
Certain properties of binary relations are so frequently encountered that it is useful to have names for them. The properties we shall consider are reflexivity, symmetry, transitivity, and connectedness. All these apply only to relations in a set, i.e., in A x A for example, not to relations from A to B, where B ≠ A.
more …
By
Partee, Barbara H.; Meulen, Alice; Wall, Robert E.
We now turn to the second of the logical languages we will examine: predicate logic. In it we will be able to analyze arguments such as (5–1) and (5–2) as well as all the arguments of the statement calculus.
By
Partee, Barbara H.; Meulen, Alice; Wall, Robert E.
At one level of description, a natural language is simply a set of stringsfinite sequences of words, morphemes, phonemes, or whatever. Not every possible sequence is in the language: we distinguish the grammatical strings from those that are ungrammatical. A grammar, then, is some explicit device for making this distinction; it is, in other words, a means for selecting a subset of strings, those that are grammatical, from the set of all possible strings formed from an initially given alphabet or vocabulary.
more …
By
Partee, Barbara H.; Meulen, Alice; Wall, Robert E.
A finite automaton (fa), or finite state automaton (fsa), is an abstract computing device that receives a string of symbols as input, reads this string one symbol at a time from left to right, and after reading the last symbol halts and signifies either acceptance or rejection of the input. At any point in its computation a fa is in one of a finite number of states. The computations of a fa are directed by a “program,” which is a finite set of instructions for changing from state to state as the automaton reads input symbols. A computation always begins in a designated state, the initial state. There is also a specified set of final states; if the fa ends up in one of these after reading the input, it is accepted; otherwise, it is rejected.
more …
By
Partee, Barbara H.; Meulen, Alice; Wall, Robert E.
Most investigators supposed from the time that the Chomsky Hierarchy was first established that natural languages, considered as string sets, would fall somewhere between the context free and the context sensitive languages and, further, that they would lie in some sense “close” to the context free class. On the one hand, the context sensitive languages seemed much too inclusive, containing as they do species such as {a^{n}b^{n!}} (n! is n factorial, i.e., 1 x 2 x 3 x ... x n ) and {a^{n} : n is prime}, which seem unlikely candidates for any sort of linguistic model. On the other hand, a large part of natural language syntax seems to be handled quite nicely by a cfg, and the aspects which seem to cause languages to fall outside the cfl class (as string sets) could be considered rather isolated and infrequent. After all, it took nearly thirty years to find one completely convincing example of a natural language which was not context free.
more …
By
Partee, Barbara H.; Meulen, Alice; Wall, Robert E.
Recall that there is no order imposed on the members of a set. We can, however, use ordinary sets to define an ordered pair, written 〈a, b〉 for example, in which a is considered the first member and b is the second member of the pair. The definition is as follows:
21
$${\rm{ }}\left\langle {a,b} \right\rangle { = _{def}}\left\{ {\left\{ a \right\},\left\{ {a,b} \right\}} \right\}$$
more …
By
Partee, Barbara H.; Meulen, Alice; Wall, Robert E.
We turn next to a class of automata which are more powerful than the finite automata in the sense that they accept a larger class of languages. These are the pushdown automata (pda’s).
By
Partee, Barbara H.; Meulen, Alice; Wall, Robert E.
The syntax of statement logic is very simple: We assume an infinite basic vocabulary of atomic statements represented by the symbols p, q, r, s,..., with primes or subscripts added as needed.
By
Partee, Barbara H.; Meulen, Alice; Wall, Robert E.
One of the most important developments in the mathematical study of grammars of linguistic interest was the work of Peters and Ritchie (1973) and Ginsburg and Partee (1969) on the socalled “standard theory” transformational grammars of the sort outlined in Chomsky (1965).
more …
By
Partee, Barbara H.; Meulen, Alice; Wall, Robert E.
We have seen that a pushdown automaton can carry out computations which are beyond the capability of a finite automaton, which is perhaps the simplest sort of machine able to accept an infinite set of strings. At the other end of the scale of computational power is the Turing machine (after the English mathematician A. M. Turing, who devised them), which can carry out any set of operations which could reasonably be called a computation.
more …
By
Partee, Barbara H.; Meulen, Alice; Wall, Robert E.
A set is an abstract collection of distinct objects which are called the members or elements of that set. Objects of quite different nature can be members of a set, e.g. the set of red objects may contain cars, bloodcells, or painted representations. Members of a set may be concrete, like cars, bloodcells or physical sounds, or they may be abstractions of some sort, like the number two, or the English phoneme /p/, or a sentence of Chinese. In fact, we may arbitrarily collect objects into a set even though they share no property other than being a member of that set. The subject matter of set theory and hence of Part A of this book is what can be said about such sets disregarding the actual nature of their members.
more …
By
Partee, Barbara H.; Meulen, Alice; Wall, Robert E.
This chapter is of a somewhat different nature than the rest of this book since it does not present mathematical tools for linguistic analysis, or show successful applications of such tools to linguistic problems. It is concerned with some of the most difficult issues in philosophical and linguistic semantics, which for a long time have been and still are central to the theory of meaning and interpretation of natural language. Various analyses of these issues have been proposed, using different mathematical tools, but at least in the present state of the art there is no single account of these puzzles which is commonly received and recognized as the right solution. The core of these issues is outlined here without much formalization, only to provide some initial understanding of what is at stake. In Section 3 a simple method is presented to analyze intensionality in natural language, and the discussion in subsequent sections may aid in appreciating the possibilities and limitations of different mathematical methods for linguistic analysis.
more …
By
Partee, Barbara H.; Meulen, Alice; Wall, Robert E.
Formalization or axiomatization is an outgrowth of the broader goals of scientific systematization. Euclid systematized geometry by showing how a great many statements known to be true about geometrical figures could be logically derived from a small set of principles assumed to be true, called the axioms. Newton systematized mechanics by showing how the known laws of motion, both planetary and terrestrial, could be derived from three basic statements. In both cases, the initial assumptions had the status of true statements, ‘selfevident’ in the Euclidean system, empirically discovered truths in the Newtonian system. In both cases the system was concerned with particular objects, points and lines in the one case, physical objects in the other.
more …
By
Partee, Barbara H.; Meulen, Alice; Wall, Robert E.
An algebraA is a set A together with one or more operations f_{i}. We may represent an algebra by writing
91
$${\rm{ }}A = \left\langle {A,{\rm{ }}{f_1},{\rm{ }}{f_2}{\rm{ }}...{\rm{, }}{f_n}} \right\rangle$$
or by using particular symbols for the operations, such as
92
$${\rm{ }}{\bf{A}}{\rm{ = }}\left\langle {A,{\rm{ + , }} \times } \right\rangle$$
The set A may be finite or infinite, and there may be either a finite or an infinite number of different operations. However, each operation must be finitary, i.e. unary, binary, ternary .... Each nary operation must be a welldefined operation, i.e., defined for all ntuples of elements of A and yielding a unique element of A as a value for each ntuple (cf. the mapping condition for functions in Section 2.3).
more …
By
Partee, Barbara H.; Meulen, Alice; Wall, Robert E.
A groupG is an algebra which consists of a set G and a single binary operation, which we will usually write as ο, but which may sometimes be written + or x : G = 〈G, ο〉. To be a group, G must satisfy the following conditions, the group axioms:
G1:
G is an algebra (i.e., ο completely defined and G closed under ο).
G2:
ο is associative.
G3:
G contains an identity element.
G4:
Each element in G has an inverse element.
more …
By
Partee, Barbara H.; Meulen, Alice; Wall, Robert E.
In the preceding chapters we have occasionally dealt with sets, such as the set of positive integers, which we intuitively regard as infinite. We now want to examine the concept of infinity in more detail.
By
Partee, Barbara H.; Meulen, Alice; Wall, Robert E.
In this section and the next, we return in greater detail to the study of formal systems from syntactic and semantic perspectives. In this section we focus on the syntactic side, and our aim will be to link together the notion of recursive definition which we introduced in Chapter 1 as a means of specifying sets with the closely related notions of inductive proof, new in this chapter, and of axiomatic system. Some of the close connections between grammars and formal systems will be illustrated, and various string operations will be formalized, although grammars as a topic in their own right will not be taken up until Part E. The discussion in this section will be purely syntactic (in part so as to illustrate what that means); we will return to a semantic investigation of some of the formal systems discussed here in the next section.
more …
By
Partee, Barbara H.; Meulen, Alice; Wall, Robert E.
A linear bounded automaton (lba) is, in effect, a Turing machine whose computations are restricted to the amount of tape on which the input is written. We can imagine it as consisting of a finite set of states, a finite alphabet (including special right and leftendmarkers [ and ]), a designated initial state, and a finite set of instructions of the same form as the quadruples for Turing machines. We assume, however, that the input to an lba is given between the designated endmarkers, i.e. as [w], and that the lba has no instructions which allow it to move past these endmarkers or to erase or replace them. Thus, the tape head can move only in the portion of the tape originally occupied by w, although an equivalent formulation of lba’s sets the limit on usable tape not as equal to the length of the input but rather as a linear function of the length of the input. (A linear function in a variable x is of the form ax + b, where a and b are constants. Plotting values of ax + b for each value of x on graph paper gives a straight line, whereas plots of functions involving x^{2}, x^{3}, etc. gives curves.) This is the source of the name for these automata—the allowed computational space is bounded by a linear function of the length of the input string.
more …
By
Partee, Barbara H.; Meulen, Alice; Wall, Robert E.
Richard Montague was the first to seriously propose and defend the thesis that the relation between syntax and semantics in a natural language such as English could be viewed as not essentially different from the relation between syntax and semantics in a formal language such as the language of firstorder logic. While Montague’s claim was and is a controversial one, both the perspective he offered and the technical apparatus used in developing it have transformed the study of natural language semantics. In this section we focus first on the principle of compositionality and its central role in articulating the relation of semantics to syntax in a formal language. The principle is also known as Frege’s principle, and Montague took himself to be formalizing a basically Fregean viewpoint in adopting it. The second topic of this chapter is the lambda calculus, invented by Alonzo Church in the 1930’s but introduced to linguists mainly through Montague’s work. The lambda calculus has no intrinsic connection to the principle of compositionality, but it has proved to be one of the most important and fruitful tools in the formal semanticist’s toolbox, and without it, it would be much harder to make a plausible case for the compositionality of natural language semantics. For a linguist interested in semantics, we would suggest that a familiarity with the basics of the lambda calculus could be as important as a familiarity with firstorder predicate logic.
more …
By
Partee, Barbara H.; Meulen, Alice; Wall, Robert E.
The universal and existential quantifiers of predicate logic introduced in Chapter 7 are in two major respects inadequate for the semantic analysis of the rich variety of quantification in natural languages. First of all, as we have seen in translating from English to predicate logic and as was pointed out again in Chapter 13, the syntactic structure of quantified formulas in predicate logic is completely different from the syntactic structure of quantified sentences in natural language. Quantifying expressions of natural language are typically full NPs, where the noun (CN) and possibly additional relative clauses provide essential restrictions on a quantifier. Not just the determiner or specifier of an NP binds dependent arguments or pronouns, but from a semantic point of view the appropriate scopedefining and binding category is the entire NP. It will prove useful for linguistic purposes (too) to distinguish between quantifying over domains and binding arguments of predicates—two jobs conflated by the two standard firstorder quantifiers of predicate logic. Secondly, many forms of quantification in natural language are not expressible or definable in terms of the firstorder logical quantifiers. For instance, the NP more than half of the CN is not expressible in terms of just firstorder quantifiers, since its interpretation requires a onetoone mapping between two finite or infinite sets dependent on a wellordering by cardinality (see Barwise and Cooper (1981) for a complete proof).
more …
By
Partee, Barbara H.; Meulen, Alice; Wall, Robert E.
In the previous chapter we have seen that the arithmetical properties of elements of formal systems may be described in operational structures. Operations may serve to generate new elements from a given set of basic elements, and thus we may view an operational or an algebraic structure naturally as a syntactic system which generates elements in a formally precise way. The relation of this dynamic conception of such systems and the linguistic notion of a grammar which generates strings as elements of a natural or formal language will be explored in much more detail in Part E. The present chapter is concerned with certain ordering relations between elements of systems or domains of objects and the ordertheoretic or ‘topological’ properties of such ordered structures. We will see that the concepts introduced in this chapter provide a universal perspective on set theory and algebra in which important correlations between the two mathematical theories can be insightfully described. Recently linguistic applications of lattices have been made primarily to semantic topics such as plural NPs, mass terms and events, using the ordering relations to structure the domains of an interpretation of a language. The potential usefulness in linguistics of syntactic applications of lattice theory is explored in research on feature systems, for instance. In this chapter we will introduce lattice theory without paying attention to any particular linguistic applications or motivations.
more …
