text:
All Android applications categories
Are Premenstrual Tension Symptoms Wrecking Your Well Being and Relationships?
Are you tired of the mood swings, headaches, muscle, diarrhea, cramps, bloating, acne, breast sensitivity, food cravings and over all pain and misery that occurs in the days that lead up to the arrival of your period every month?
Do you want to do something about this misery (also sometimes known as PMS - for premenstrual syndrome) but are leery of taking the birth control pills or antidepressants usually prescribed for premenstrual tension symptoms?
In Curing Premenstrual Tension Naturally I discuss potential solutions and ways of coping with condition such as -
How you can change your eating patterns so your symptoms are not as severe
How Tai Chi and Yoga benefit your body while it is going through this important life change
How taking wild yam can help regulate your metabolism and make you feel better in general
How sprinkling brewer's yeast on your cereal in the morning can assist you with bad PMS symptoms
The vegetables that you can eat that are natural diuretics and can help you expel water to reduce the bloating associated with PMS
An explanation of the role that salt intake can play in making your condition better or worse
How to decide whether or not birth control therapy is for you
What the risks are to your health if you should decide to take antidepressants
Why it is constant but not heavy exercise that can help your body get rid of any excess weight gain
How to increase the rate of metabolism in your body as the decrease in hormones slows it down just before you get your period
What you can do to relieve stress on your heart and blood pressure that is caused by hormonal changes and allay some anxiety
The precise yoga postures that can help you reduce tension weight gain and bring back your sexual desire
How to condition your breathing to control the anxiety and moodiness associated with PMS and PMT
How a regimen of meditation can help treat major symptoms - especially fatigue and mood swings
How aromatherapy can play a role in counteracting some of the symptoms associated with PMS
The three best aromatherapy oils that can be absorbed through the skin to help allay mood swings and other PMS symptoms
How eliminating sugar and caffeine from your diet can help with the symptoms of PMS
How sleeping for this particular number of hours a night can help eliminate the symptoms of premenstrual tension
The number of ounces of water that you should drink a day to get rid of those symptoms of PMS
What essential nutritional supplements you should be taking to banish PMS
Which herbs are most effective for fighting premenstrual tension
How acupuncture is used nowadays as a therapy for PMS
How taking herbs that nourish the endocrine system can help you master the symptoms of premenstrual tension
A list of herbal teas that can help you manage the symptoms of PMS more effectively
How evening primrose oil and starflower oil can help your symptoms thanks to the presence of this rich source of gamma oils
How drinking juiced fruits and vegetables can help you combat hormonal changes associated with PMS
What omega 3 and omega 6 fatty acids can do to allay your PMS symptoms
Whichever way you look at it, going through premenstrual tension is a tough time for every woman. You have to take care of your own body, pamper it, and look after it and you will have an easier time of it every month.
Its time to Cure Premenstrual Tension naturally. Thanks.
Tags: paper on premenstrual stress , why are you in tension , how to cure embutido , tension , tension comment , is there a natural way to treat pre menstrual tensions , premenstrual , premenstrual stress , role of music therapy and meditation on premenstrual tension syndrome
Download Cure Premenstrual Tension
Sorry ...
This app is no longer available.
Share this app


text:
SnowBunnys Hostel
Bichlstrasse 30, A-6370, Kitzbuhel, Austria
Atmosphere 82%
Cleanliness 89%
Facilities 80%
Location 100%
Safety 89%
Staff 80%
Value 84%
- Free Breakfast
- Free Wi-Fi
- Self-Catering Facilities
- 24 Hour Security
- Adaptors
- Airport Transfers
- Bicycle Hire
- Bicycle Parking
- Book Exchange
- Cable TV
- Common Room
- Free City Maps
- Free Internet Access
- Hair Dryers
- Hot Showers
- Internet Access
- Laundry Facilities
- Linen Included
- Parking
- Steam room
- Tea/Coffee Making Facilities
- Vending Machines
- Washing machine
Important Information
This property requires the CVV code of the used credit card in order to secure your booking. IN case you do not send this three digit code directly to the property, your reservation might be cancelled. In such a case, payments, such as the deposit, are non-refundable.
Private parking is possible on site (reservation is needed) and charges may be applicable.
City tax is €1.80 per person per night is not included, and is due on arrival.
Check-out: 11am. ( Late departure can result in added charges )
If you will be checking in after 10pm, please notify us ahead of time by email or phone.
Cash payment only, please.
Passports are needed for registration.
We have pay parking.
This is a non-smoking hostel. It's not a party hostel either.
Do you have allergies? Warning: We've got cats; may also contain nuts.
Check-in / Check-out
Earliest check-in: 11:00
Latest Check-out: 11:00
- Credit Cards Not Accepted
- No Curfew
- Non Smoking
- Taxes Not Included
Group booking?
Group of 15 or more traveling to Kitzbuhel?
Map and Directions
Kitzbühel has two railway stations, Kitzbühel and Kitzbühel Hahnenkamm.
We are closest to Kitzbühel Hahnenkamm which is a 200m walk from the hostel. If you arrive on one of the trains that only stops at Kitzbühel Main Train station (some InterCity and Euro Trains do this) it is about a 20 minute walk. (Or in winter you can take the ring bus.)
Bichlstrasse 30
Latitude / Longitude 47.44422343745782,12.39393800497055 (on Google Maps and OpenStreetMap )
Hahnenkammbahn Kitzbühel
1.Head downhill on Josef-Herold-Straße
go 260 m
2.Turn right onto Malingg.
go 140 m
3.Slight left to stay on Malingg.
go 26 m
4.Turn right onto Bichlstr.
SnowBunnys is on the right opposite the Q Hotel Maria Teresa.
If you plan to arrive after 10pm 22.00 please notify the Hostel by Email or Phone.
We ask that you check in as soon as you arrive in Kitzbuhel.
If you arrive drunk you will be refused entry and your booking cancelled.
SnowBunnys is not a cheap Hotel, Pension or Guest House SnowBunnys in noway offers any Hotel type services, SnowBunnys is purley a Hostel.
Please Note: To preserve and maintain our laid-back atmosphere SnowBunnys does not accept any
• Male only groups. ***
• Stag parties
• Pets
*** More than 4 is a group, If such a booking is made the booking will be cancelled and the deposit not refunded.
For special groups please contact us.
SnowBunnys will not accept any Damages, Abuse or Annoyance towards other Guests or Staff, SnowBunnys does not give second chances if needed police will escort such persons from the Hostel.
Cancellations must be made at least 2 days before your scheduled arrival day.
If you miss this deadline, the hostel is entitled to charge the equivalent of the first night or up to 40% of your booking.
Large & Long bookings maybe required to pay a extra higher deposit.
This booking engine has taken a deposit from your credit card you have as yet not made any payment to the hostel,
It is not possible to pay for the entire booking via this booking engine, the remainder payment should be paid to the hostel upon arrival.
Payment is required upon arrival
Cash Payments Only
Check Out is 11.00am
Passports are needed for registration
SnowBunnys is a No Smoking Hostel
SnowBunnys is not a Party Hostel
SnowBunnys has monitored CCTV
SnowBunnys is Gay Friendly
SnowBunnys has Pay Parking
SnowBunnys is only a 1 hour drive from Salzburg Airport, by train it can take over 3 hours,
Please note if you fly to Salzburg after 9pm cet you most likley wont find a train to Kitzbuhel,
Airport Taxi Transfers
Tel.: +43 (0)5356 66222
Fax: +43 (0)5356 66223
Mobil: +43 (0)664 2808465
Email: firstname.lastname@example.com
+43 6767940233
Stressed Bunny

subset: commoncrawl


text:
by Water Gear
Order now to get it by: Saturday August 05 - Monday August 07
Get it on Tuesday August 1st with expedited shipping.
Select the expedited delivery option after adding this item to your cart.
Condition: New
Product ID: 767370
Delivery Information |Returns & Exchanges |Payment Methods
Soft, comfortable closed cell EVA foam will not absorb water or chip. Buckles easily on back for young swimmers, freeing
arms for proper motion. Features a split float that allows adjustment as swimmer progresses.
Speedo Aqua Jog Water Aerobic Swim Training Belt
Instructional Swim Belt - Three Module
AquaJogger Short Waist Athletic Fit Belt with DVD
Aqua Jogger Jr. Belts
Aqua Jogger Classic Belt - Blue
Speedo Hydro Resistant Jog Belt Swim Training Aid, Silver/Red
Water Gear Water Runner Flotation Belt - 160 - 220 lbs
Water Gear Instructional Swim Belt - (4 Piece)


text:
HP's new Z1 G3 Workstation is slender, stylish, won't take up much room on your desk and is packed with powerful features that can handle intensive editing workflows. Better yet, it can be customized from a choice of processors, graphics cards and even operating systems (Windows 7, 10 or Linux).
Compared to the previous generation, the new Z1 G3 is smaller, lighter and less expensive without sacrificing any features. The base and monitor are both smaller and the high resolution 16:9 display is now 23.6 inches versus the G2's 27-inches. By minimizing the Z1 G3's display size, users have more space for a second display.
HP has also made it easy to update and service the workstation. Just pop off the back cover to access the guts of this workstation, including its two storage bays and 4 memory slots, which can hold up to 64GB of memory.
In addition to USB 3.0 ports, the Z1 G3 is equipped with dual Thunderbolt 3 and USB 3.1 capabilities. And, as a bonus, HP's new remote graphics software (RGS) now offers Mac support so you can access the workstation remotely from your Mac.
There are far too many specs—and options—to list here, but with a base price of around $1,500, it's worth the few minutes it will take to check out the details on the HP site.


text:
Introduction. W. Buszkowski Type Logics in Grammar
- Brian Crawford
- 2 years ago
- Views:
1 W. Buszkowski Type Logics in Grammar Introduction Type logics are logics whose formulas are interpreted as types. For instance, A B is a type of functions (procedures) which send inputs of type A to outputs of type B, and A B is a type of pairs (f, g) such that f is of type A and g is of type B. The scope of possible realizations is huge: from constructivism in mathematics to logics of computation, from combinators and lambda calculus to linear logics, from type theories of Russell and Church to theories of syntax, proposed by Leśniewski, Ajdukiewicz, Chomsky, Curry and Lambek. In this paper I try to illuminate the current state of the latter theories, often characterized as logical grammar or, more generally, formal grammar. Not every logician would be inclined to attach this region to logic proper. Fortunately, numerous contributions of last thirty years have lifted up the logic of grammar to a vivid research branch with a well-defined conceptual framework and promising connections with linguistics and computer science (also philosophy, cognitive science, semantics). From the standpoint of logic, formal systems appearing in this discipline belong to substructural logics, since their sequential formats abandon structural rules (Weakening, Contraction, Exchange); see [69]. Hiż [34] dubbed the term grammar logicism for the thesis: grammar reduces to logic. Not discussing all subtleties of this standpoint, I believe Hiż soundly characterizes the real content of so-called formal linguistics with its standard syntactic devices (automata, grammars, trees, transformations) which are conceptually and methodologically akin to logical entities (routines of computation, theories, proofs, deductive systems). It seems to be important that grammatical structures influence the creation and evolution of new logical formalisms, as e.g. the Lambek calculus and noncommutative linear logics. Reduction of grammar to logic need not be restricted to the dimension of V. F. Hendricks and J. Malinowski (eds.), Trends in Logic: 50 Years of Studia Logica Trends in Logic 21: , c 2003 Kluwer Academic Publishers. Printed in the Netherlands.
2 322 W. Buszkowski syntax. Since Montague [57], semantics of natural language has extensively been studied within philosophical logic. Semantical problems seem to be more sophisticated and solutions less definitive. I am inclined to remove any strict borderline between syntax and semantics; the former is a representation of the latter, the latter must be anchored in the former. Type grammars are especially close to the description of syntax according to general semantic paradigms. Connections of type grammars with Montague semantics are based on the Curry-Howard isomorphism between proofs in Natural Deduction format and lambda terms. For Lambek logics, main results are due to van Benthem [76, 78], Moortgat [58, 59] and their collaborators. In this survey, semantical aspects are briefly mentioned at the beginning of section 3. Grammars based on logics of types are traditionally called categorial grammars (after Bar-Hillel et al. [5]). From the modern perspective, the term type grammars seems to be more adequate: all formal grammars classify language expressions into categories, but a characteristic feature of type grammars is the usage of (logical) types as carriers of grammatical information. The present paper mainly focuses on type grammars and their logics, which evidently reflects the author s predilection and experience. Hopingly, it shows a more general significance of some central ideas. We begin with the simplest formalization of type grammar: Classical Categorial Grammar (CCG) of Ajdukiewicz [3] and Bar-Hillel [5]. Ajdukiewicz was strongly influenced by logical syntax, designed by Leśniewski [54], and the idea of universal grammar, due to Husserl [36]. The logic of CCG is a purely implicational propositional logic with modus ponens and no axioms; in the bidirectional format, stemming from Lambek [49] and Bar-Hillel [5], it admits two conditionals A B and B A and two MP-schemes. We discuss three major topics concerning CCG: (i) syntactic unambiguity (related to Polish notation), (ii) connections with Chomsky grammars and tree automata, (iii) learnability. The latter exhibits a new, promising direction of formal learning theory, employing logical unification to design successful algorithms for language acquisition. Next, we consider full-fledged type logics, originating in Syntactic Calculus of Lambek [49]. They are closely connected with other logical formalisms, as e.g. linear logics, lambda calculus and combinators, labelled deductive systems. First, we present different versions of type logics and discuss their proof-theoretic and computational aspects. Second, we sketch a landscape of models of these logics. We also regard central problems related to type grammars based on these logics. This survey is complementary to the author s [14]. Certain topics, largely
3 Type Logics in Grammar 323 discussed there, e.g. algebra of syntactic structures and modelling type logics in the lambda calculus, are almost completely omitted here. On the other hand, we present in more detail some special matters, characteristic of current research, as e.g. learning theory and computational complexity. In section 3, we mix algebraic models and computational problems, because they are mutually dependent. Algebraic structures influence the shape of formal systems and are useful for illuminating proof-theoretic properties, i.e. the subformula property. We report results of many people, including the author, who apologizes for the great number of self-citations in comparing with others. The reason is obvious: the author focuses on problems he has been involved in and informs the reader where she may find proofs abandoned here. In compensation, let me emphasize a particular role of two persons. Joachim Lambek has originated some central ideas, and Johan van Benthem has shown their broader significance for logic. Classical Categorial Grammar Pr denotes a set of primitive types (propositional variables). Types (formulas) are formed out of two conditionals (right arrow) and (left arrow). We denote types by A, B, C, D. Γ, denote finite sequences (strings) of types, and Γ denotes the concatenation of Γ and. Sequents are expressions of the form Γ A. The empty string is denoted by ɛ. The logic AB (after Ajdukiewicz and Bar-Hillel) can be presented as a structured consequence relation (in the sense of Gabbay [28]), which is determined by MP-schemes: (MP-R) A(A B) B, (MP-L) (B A)A B, and the following structural rules: (Id) A A, (CUT) ΓAΓ B; A Γ Γ. B Equivalently, AB can be presented as a rewriting system, based on reduction rules: A, A B B and B A, A B. Then, Γ AB A iff Γ reduces to A by a finite number of applications of reduction rules. We write Γ AB A for: Γ A is provable in AB, and similarly for other systems. Clearly, if Γ AB A then Γ ɛ.
4 324 W. Buszkowski Ajdukiewicz [3] introduced the ( ) fragment of this logic; precisely, he regarded multiple-argument types B A 1,..., A n with reduction rules: (B A 1,..., A n ), A 1,..., A n B. In Natural Deduction (ND) format, AB is axiomatized by (Id) and two conditional elimination rules: ( E) Γ A; A B Γ B, ( E) Γ B A; A. Γ B Proofs in the ND-format determine the so-called functor-argument structures (fa-structures) on antecedents of provable sequents. Types are atomic fa-structures. If X, Y are fa-structures, then (XY ) 1 and (XY ) 2 are fastructures. X is the functor, and Y is the argument of (XY ) 1, and the converse holds for (XY ) 2. The logic ABs (i.e. AB in structure form) arises from AB (in ND-format) by replacing Γwith X, with Y in premises of rules, and Γ with (XY ) 2 (resp. (XY ) 1 ) in the conclusion of ( E) (resp. ( E)). Every proof of Γ A in AB determines a unique fa-structure X on Γ such that X ABs A. The same could be done for the original version of AB. Syntactic unambiguity It is well known that the Polish notation is unambigous, that means, the structure of a formula is uniquely determined by the string of symbols. This property is actually a property of the logic AB, restricted to one conditional. Since this a rather untypical property of a logical system, and it is in focus of Ajdukiewicz [3], we have decided to discuss the problem in some detail. For any structure X, there is at most one type A such that X ABs A. One computes this type by a successive replacement of every substructure of X of the form (A(A B)) 2 or ((B A)A) 1 with type B. This property will be referred to as type unambiguity of ABs. Also, every provable sequent X A has a unique proof tree in the ND-format of ABs (proof unambiguity). AB is both type and proof ambiguous. (A A)A(A A) A has two proofs in AB which determine structures (C(AD) 2 ) 1 and ((CA) 1 D) 2, for C = A A, D = A A. For Γ = ((A D) A)AD, with D as above, we have both Γ AB A D and Γ AB A. One-directional fragments of AB are both type and proof unambigous, which is a nonstandard proof-theoretic property, clearly related to (generalized) Polish notation: a string of symbols supplied with one-directional types admits a unique syntactic analysis (see [13] for a discussion and the
5 Type Logics in Grammar 325 proof for the general case of multiple-argument types). We sketch the proof for the ( ) fragment of AB. In types B A 1 A n parentheses are grouped to the left. If D is of the above form, with B primitive, then C < D means that C equals B A 1 A i, for some 0 i < n. The relation < is irreflexive, transitive and quasi-linear: if A < C and B < C, then A < B or A = B or B < A. The following lemmas are crucial. (L1) If AΓ AB B and Γ ɛ then B < A. (L2) If B < A then AΓ AB B, for some Γ ɛ. (L3) If Γ AB A then there is no ɛ such that Γ AB A. We prove (L3). We use the following property of the restricted AB: if Γ AB A and Γ has a length greater than 1, then Γ = (A 2 A 1 )Γ 1 Γ 2 with Γ 1 AB A 1 and A 2 Γ 2 AB A. The proof of (L3) proceeds by induction on the length of Γ. Let Γ be of length 1. Assume Γ AB A and Γ AB A, for ɛ. Then, Γ = A, and consequently, A < A, by (L1). Contradiction. Let Γ be of length greater than 1. Assume the same as above. Using the property, mentioned above, we get types A 1, A 2 and nonempty strings Γ i, i, for i = 1, 2, such that: 1. Γ = (A 2 A 1 )Γ 1 Γ 2, 2. Γ = (A 2 A 1 ) 1 2, 3. Γ 1 AB A 1, 1 AB A 1, 4. A 2 Γ 2 AB A, A 2 2 AB A. Clearly, the length of Γ 1 is less than the length of Γ, and similarly for Γ 2. By the induction hypothesis, neither Γ 1 is a proper initial segment of 1, nor 1 is a proper initial segment of Γ 1. Consequently, Γ 1 = 1. Then, Γ 2 is a proper initial segment of 2, hence A 2 Γ 2 is a proper initial segment of A 2 2, and its length is less than that of Γ. This contradicts the induction hypothesis. We prove type unambiguity. Assume Γ AB A and Γ AB B, with A B. Let C be the first type in Γ. Since A B, then Γ is of length greater than 1. By (L1), A < C and B < C. Consequently, A < B or B < A. If A < B then there exists ɛ such that B AB A, by (L2),
6 326 W. Buszkowski which yields Γ AB A, by (CUT). This contradicts (L3). The case B < A is symmetrical. We prove proof unambiguity. Precisely, we show that every provable sequent admits a unique ND proof tree in the restricted AB. Let d 1, d 2 be proofs of Γ A. We prove d 1 = d 2, by induction on the length of Γ. Assume Γ is of length 1. Then, Γ = A, and d 1, d 2 consist of the only application of (Id). Assume Γ is of length greater than 1. Then, both d 1 and d 2 use ( E). We consider the last application of this rule in either proof. For d 1, let the premises be Γ 1 A C, 1 C, and for d 2, let them be Γ 2 A D, 2 D. We show C = D. Assume C D. Then, Γ 1 or Γ 2 is of length greater than 1, hence A C < A D or A D < A C, by (L1) and properties of <. This is impossible, by the definition of <. Now, Γ 1 is an initial segment of Γ 2 or conversely. Neither of them can be a proper initial segment of the other, by (L3), which yields Γ 1 = Γ 2, and consequently, 1 = 2. By the induction hypothesis, subproofs of d 1, d 2 leading to the left premise are equal, and similarly for the right premise. Consequently, d 1 = d 2. Ajdukiewicz [3] has designed a simple parsing procedure. Given a string Γ, find the left-most occurrence of (B A)A and replace it with B. Then, Γ AB C iff Γ reduces to C by finitely many applications of left-most reduction. As shown in [13], this is not true for multiple-argument types (considered by Ajdukiewicz) but is true for one-argument types, considered here. The Ajdukiewicz procedure is fully deterministic and shows, in fact, that languages generated by rigid type grammars based on this fragment of AB are deterministic context-free languages, i.e. they can be recognized by deterministic push-down automata (rigid grammars are defined below). CCG versus other formal grammars A CCG can formally be defined as a triple G = (V G, I G, S G ) such that V G is a nonempty finite lexicon (alphabet), I G is a finite relation between elements of V G and types, and S G Pr; V G, I G, S G are called the lexicon, the initial type assignment and the principal type, respectively, of G. We write G : v A for (v, A) I G. We say that G assigns type A to string a = v 1... v n, v i V G, if there are types A i such that G : v i A i, for i = 1,..., n, satisfying A 1... A n AB A; we write a G A. The language of G (L(G)) is the set of all strings a such that a G S G. Other type grammars, considered later on, are defined in a similar way; only AB is to be replaced by a different type logic. The fa-structures on V G are defined as fa-structures of types except that
7 Type Logics in Grammar 327 atomic fa-structures are elements of V G. By F (V G ) we denote the set of fa-structures on V G. We say that G assigns type A to structure X F (V G ) if there is an fa-structure X of types which arises from X by replacing each atom v by a type B such that G : v B, satisfying X ABs A; we again write X G A. The f-language of G (L f (G)) is the set of all X F (V G ) such that X G S G. For instance, let G admit the following assignment: Joan A, works B, hardly C, where A =PN (proper noun), B = A S, C = B B, and S G =S (sentence). Then, L f (G) contains structures: 1. (Joan works) 2, 2. (Joan (works hardly) 2 ) 2, 3. (Joan ((works hardly) 2 hardly) 2 ) 2, and so on. L(G) contains the strings resulting from the above structures after one has dropped all structure markers. The above grammar is a rigid CCG, i.e. it assigns at most one type to any lexical atom. Rigidness is characteristic of grammars designed for formal languages of logic and mathematics, while natural language usually requires several types to be assigned to one lexical atom. The negation not is assigned type S S, as in the sentence not every man works with structure (not ((every man) works)), but also type C C (C defined as above), as in John works not hardly. We have used a structure without functor markers; such structures are called phrase structures (p-structures). For X F (V G ), by p(x) we denote the p-structure resulting from X after one has dropped all functor markers. The phrase language of G (L p (G)) consists of all p(x), for X L f (G). Now, let us turn to some basic notions of Chomsky linguistics. A contextfree grammar (CF-grammar) is a quadruple G = (V G, N G, R G, S G ) such that V G, N G are disjoint finite alphabets, S G N G, and R G is a finite subset of N G (V G N G ) (W denotes the set of all finite strings of elements of set W ). Elements of V G, N G, R G are called terminal symbols, nonterminal symbols and production rules, respectively, of G, and S G is called the initial symbol of G. Production rules are written A a instead of (A, a). We say that string b is directly derivable from string a in G (write a G b) if there exist strings c, d, e and rule A e in R G such that a = cad, b = ced. We say that string b is derivable from string a in G (write a G b) if there exists
8 328 W. Buszkowski a sequence (a 0,..., a n ) such that n 0, a 0 = a, a n = b and a i 1 G a i, for all i = 1,..., n. The language of G (L(G)) is the set of all a VG such that S G G a. Grammars G, G are said to be (weakly) equivalent if L(G) = L(G ). It is well-known (see e.g. [72]) that every CF-grammar G such that ɛ L(G) can be transformed into an equivalent CF-grammar G in the Chomsky normal form: all production rules of G are of the form A v or A BC, where A, B, C N G, v V G. The CCG exemplified above can be replaced with a CF-grammar (in the Chomsky normal form) whose production rules are as follows: S AB, B BC, A Joan, B works, C hardly, with S G =S, N G = {S, A, B, C}, and V G consisting of lexical atoms Joan, works and hardly. A derivation of Joan works hardly is: S AB ABC Joan works hardly. Every CF-derivation determines a unique p-structure on the derived string; the above derivation leads to structure (Joan (works hardly)). The phrase language of CF-grammar G (L p (G)) consists of all p-structures on strings from L(G) which are determined by possible derivations of these strings. A principal difference between CCG and CF-grammar is that the former is lexical, that means: all particular linguistic information is put in the initial assignment of types to lexical atoms, and the derivation procedure is based on universal rules, common for all languages, whereas the latter puts the linguistic information in the production rules which underly the derivation procedure. Lexicality is characteristic of all basic kinds of type grammar: the universal rules for derivation procedures are provable sequents of some logics, being independent of the particular language. In section 3, we shall show that lexicality is, actually, a restriction: larger classes of languages can only be described by type grammars avoiding lexicality. The Gaifman theorem [5] establishes the (weak) equivalence of CCG s and CF-grammars (for ɛ free languages). It is easy to show that every CCG is equivalent to some CF-grammar. Let G be a CCG, and let T G denote the set of all types appearing in I G. By T (G) we denote the set of all subtypes of types from T G. Clearly, T (G) is finite and contains all types assigned by
9 Type Logics in Grammar 329 G to any strings. A CF-grammar G is defined by: V G = V G, N G = T (G), S G = S G, and R G consists of all rules: B A(A B), B (B A)A, for (A B), (B A) T (G), and all lexical rules A v, for (v, A) I G. One easily proves: A 1... A n AB A iff A G A 1... A n, for all A i, A T (G), and consequently, L(G) = L(G ). The converse direction is more sophisticated. It is easier if one assumes that the CF-grammar G is in the Greibach normal form, that means: all production rules are of the form A v, A vb or A vbc, for A, B, C N G, v V G (every CF-grammar G such that ɛ L(G) is equivalent to a CF-grammar in the Greibach normal form [72]). We identify nonterminal symbols of G with primitive types. A CCG G is defined by: V G = V G, S G = S G, and I G consists of: 1. all pairs (v, A) such that (A v) R G, 2. all pairs (v, A B) such that (A vb) R G, 3. all pairs (v, A C B) such that (A vbc) R G. By induction on n, one proves: A G v 1... v n iff v 1... v n G A, for all A N G, v i V G, which yields L(G) = L(G ). Actually, the Gaifman theorem has been proven earlier than the Greibach normal form theorem. Since the CCG, constructed by Gaifman, is precisely of the above form, then his proof can be treated as the first proof of the Greibach normal form theorem for CF-grammars (see an analysis of this proof in [10]). CCG s are not equivalent to CF-grammars on the level of p-structures. Let P (V ) denote the set of all p-structures on alphabet V. Let L P (V ). We say that X P (V ) is equivalent to Y P (V ) with respect to L (write X L Y ) if, for all Z P (V ), Z[X] L iff Z[Y ] L (as usual in logic, Z[X] denotes Z with a distinguished occurrence of substructure X, and Z[Y ] denotes the result of replacing X with Y in Z). By the classical theorem of Thatcher, L = L p (G), for some CF-grammar G, iff the relation L is of finite index. By the external degree of X P (V ) (think of X as a tree)
10 330 W. Buszkowski we mean the length of the shortest branch of X, and the degree of X is the maximal external degree of substructures of X. For instance, v is of degree 0, (vw) is of degree 1, and ((vw)(v w )) is of degree 2. It has been shown in [9] that L = L p (G), for some CCG G, iff both L is of finite index and all structures in L are of bounded degree. Accordingly, phrase languages of CCG s are a narrower class than those of CF-grammars. For instance, the CF-grammar given by rules S SS, S v produces all possible p-structures on {v}, hence its phrase language is of unbounded degree, and consequently, it cannot be generated by any CCG. Phrase languages generated by CCG s are regular tree languages in the sense of tree automata (see [30]); this follows from the above characterization of them as languages of finite index. Tiede [74] obtains analogous results for ND proof trees associated with CCG s and other kinds of categorial grammars. For grammars based on the nonassociative Lambek calculus, some related results have been proven by Kandulski [43]. A similar characterization can be given for functor languages generated by CCG s: for L F (V ), there is a CCG G such that L = L f (G) iff both the relation L is of finite index and all structures in L are of bounded functor degree (one counts the length of functor branches only; see [14]). Consequently, functor languages of CCGs are regular tree languages. Standard techniques of tree automata [30] yield the decidability of the emptiness problem, the inclusion problem and the equality problem for these languages; for a discussion, see [14]. In particular, the problem of whether L f (G) L f (G ) is decidable, which is crucial for some learnability results in the next subsection. Learnability Formal learning theory, stemming from Gold [31], is a theory of language acquisition, based on formal grammars and recursion theory. It has evident links with logical theories of inductive inference and knowledge discovery. Technical results are mainly due to people working in theoretical computer science; see the survey [64]. In [20], the logical method of unification has been applied to design learning procedures for CCG s. Kanazawa [38, 39] uses these procedures to construct convergent learning functions for several classes of CCG s. Negative postulates are considered in [20, 56, 18, 26, 27]. Unification in type grammar has also been studied in e.g. [77, 75]. Due to lexicality (and the functional structure of types), type grammars seem to be especially suitable to experiment learning algorithms employing
11 Type Logics in Grammar 331 unification. Hopingly, similar techniques can be developed for dependency grammars and minimalist grammars (C. Retore, E. Stabler). We shall describe fundamental lines of this approach for CCG s. First, we recall some basic notions of formal learning theory. A grammar system is a triple (Ω, E, L) such that Ω and E are countably infinite sets, and L is a function from Ω into the powerset of E. Elements of Ω are called grammars, elements of E are called expressions, and L(G), for G Ω, is called the language of G. W + denotes the set of all nonempty strings of elements of W. A learning function for the grammar system is a partial function from E + into Ω. Intuitively, the learning function assigns grammars to finite samples of a language. Let (s i ) i ω be an infinite sequence of expressions. One says that a learning function ϕ converges on this sequence to G Ω if ϕ((s i ) i<n ) is defined and equals G, for all but finitely many n ω. Let G Ω. We denote L(G) = {L(G) : G G}. A sequence (s i ) i ω is called a text for a language L E if L = {s i : i ω}. One says that a learning function ϕ learns G if, for every L L(G) and every text for L, there is G G such that L = L(G) and ϕ converges to G on this text. A class G is said to be (effectively) learnable if there exists a computable learning function ϕ that learns G. Informally, G is learnable iff there exists an algorithmic procedure which hypothesizes a grammar on the basis of a finite language sample (it need not be defined on all samples); if the inputs are successive initial segments of any text for any language generated by a grammar from this class, then, after a finite number of steps, the outputs provide a fixed grammar from G which generates this language. Let L be a class of subsets of E (languages on E). One says that L admits a limit point if there exists a stricly ascending chain (L n ) n ω of languages from L such that the join of this chain belongs to L. It is known that if L(G) admits a limit point then G is not (even uneffectively) learnable. As a consequence, if G generates all finite languages and at least one infinite language, then G is not learnable. This holds for all standard classes of formal grammars, e.g. regular grammars, CF-grammars, CCG s and so on. Accordingly, learnability can be gained for some restricted classes only, as e.g. context-sensitive grammars with at most k production rules [71]. Kanazawa [38, 39] shows that rigid CCG s and k valued CCG s are learnable. Wright [81] has defined the following property of a class L of languages: L has finite elasticity if there exists no pair ((s i ) i ω, (L i ) i ω ), s i E, L i L, such that s i L i but s 0,..., s i L i+1, for all i ω. Kapur [44] has proven
12 332 W. Buszkowski that finite elasticity entails the following condition: (D) for every L L, there exists a finite set D L L such that L is the smallest language L L, satisfying D L L. We prove that finite elasticity is equivalent to a strengthening of (D): (D ) for every L E, there exists a finite set D L L such that, for every L L, if D L L then L L. Assume that L does not satisfy (D ). Then, there exists L E such that, for any finite D L, there is L L such that D L but L L. Take D =. There is L L such that L L. Put s 0 L L, L 0 = L. Assume s i L and L i L, for i = 0,... n, have already been defined with s i L i, for 0 i n, and s 0,..., s i L i+1, for 0 i < n. There is L L such that s 0,..., s n L but L L. Put s n+1 L L, L n+1 = L. In this way, we define a sequence (s i ) i ω and a sequence (L i ) i ω, showing that L does not have finite elasticity. Assume that L satisfies (D ). Let (s i ) be an infinite sequence of expressions. By (D ), there is n ω such that, for any L L, if s 0,..., s n L then s i L, for all i ω. Consequently, there exists no infinite sequence (L i ), of languages from L, such that s 0,..., s n L n+1 but s n+1 L n+1, which proves the finite elasticity of L. This yields Kapur s theorem, since (D) follows from (D ). If L is a closure system, that means: L is closed under arbitrary meets, then L satisfies (D ) iff it admits no infinite ascending chains, that means: there is no infinite sequence (L i ), of languages from L, such that L i L i+1, for all i ω (this observation and the equivalence of finite elasticity with (D ) seem to have been overlooked in literature). We prove this fact. Assume L satisfies (D ). Let (L i ) be an infinite sequence of languages from L such that L i L i+1, for all i ω. Let L be the join of this sequence. Take a finite set D L L, as in (D ). Then, D L L n, for some n ω. Consequently, L L n, hence L n = L n+1. Therefore, L admits no infinite ascending chains. Assume that L is a closure system which does not satisfy (D ). Then, there exists L E such that, for every finite D L, there is L L, satisfying D L but L L. Clearly, L is infinite. Let (s i ) be an infinite sequence of all expressions from L. For every n ω, let L n denote the smallest language L L such that s 0,..., s n L ; it exists, since L is a closure system. Clearly, L n L n+1, for all n ω. For every n ω, there is L L such that s 0,..., s n L but L L, and consequently, there is
13 Type Logics in Grammar 333 m > n such that s m L n, which yields L n L m. Then, there exists an infinite, strictly ascending chain of languages from L. Let G Ω. We always assume that G is recursively enumerable and the universal membership problem s L(G), for s E, G G, is decidable. We need one more condition: (MIN) there exists a computable partial function χ from the set of finite subsets of E into G such that the domain of χ is recursive and, for any finite D E, the family {L L(G) : D L} is nonempty iff χ(d) is defined; if so, L(χ(D)) is a minimal language in this family. We prove a basic theorem, due to Kapur [44]: (T1) if G satisfies (MIN) and L(G) has finite elasticity, then G is learnable. Assume G satisfies (MIN), and L(G) has finite elasticity. function ϕ is defined as follows: A learning (l0) ϕ((s 0 )) = χ({s 0 }), (l1) if ϕ((s 0,..., s i )) = G is and s i+1 L(G) then ϕ((s 0,..., s i+1 )) = G, (l2) ϕ((s 0,..., s i+1 )) = χ({s 0,..., s i+1 }), otherwise. The relation ϕ is defined on (s 0,..., s i ) is recursive, since both the domain of χ and the relation s L(G), for G G, are recursive. Consequently, ϕ is recursive. It is easy to show the following: if ϕ((s 0,..., s i )) = G is defined, then L(G) is a minimal language in the family of all L L(G) such that s 0,..., s i L. Let L L(G), and let (s i ) be a text for L. Clearly, ϕ((s 0,..., s i )) is defined, for all i ω. Let D L L be as in (D). There exists n ω such that D L {s 0,..., s n }. Since L is the smallest language L L such that D L L, then L = L(G), for G = ϕ((s 0,..., s n )). By (l1), G = ϕ((s 0,..., s m )), for all m n. We have shown that ϕ learns G. Since ϕ satisfies (l1), it is conservative in the sense of formal learning theory. If conservativity is not required, then the finite elasticity of L(G) is a sufficient condition for the learnability of G [64]. Now, we apply these methods to CCG. Let us consider the grammar system (Ω, E, L) such that Ω is the class of CCG s (with a fixed lexicon V ), E = F (V ), and L(G) = L f (G), for G Ω. We assume that all grammars in Ω have the same principal type S. Since V and S are fixed, a grammar G can be identified with I G.
14 334 W. Buszkowski First, we recall a unification-based learning procedure from [20]. Let D F (V ) be a nonempty, finite set. We define a CCG GF(D), called the general form of a grammar for D. S is treated as a constant, whereas other primitive types are treated as variables. We assign S to all structures from D and distinct variables to all occurrences of argument substructures of these structures. Then, we assign types to functor substructures of these structures according to the rules: (fr) if (XY ) 2 is assigned B and X is assigned A then Y is assigned A B, (fl) if (XY ) 1 is assigned B and Y is assigned A then X is assigned B A. GF(D) contains all assignments v A obtained in this way, for v V ; the principal type of GF(D) is S. For instance, if D consists of structures (Joan works) 2 and (Joan (works hardly) 2 ) 2, then GF(D) contains the assignments: Joan x, y, works z, x S, hardly z (y S). A substitution is a mapping from variables to types; it is naturally extended to a mapping from types to types. If G is a CCG, and σ is a substitution, then Gσ is a (unique) CCG which assignments v Aσ, whenever G : v A. We have L f (G) L f (Gσ), for all G, σ. For G, G Ω, we write G G if I G I G. The following lemma is crucial [20]. (L1) Let D F (V ) be nonempty and finite. Then, for every G Ω, D L f (G) iff there exists σ such that GF (D)σ G. The following notions come from the logical theory of unification; we modify definitions from [20]. A substitution σ is called a unifier of G Ω if, for all v V and types A, B such that G : v A and G : v B, there holds Aσ = Bσ. It is called a most general unifier (m.g.u.) of G if it is a unifier of G and, for every unifier η of G, there exists a substitution γ such that η = σγ. G is said to be unifiable if there exists a unifier of G. The standard algorithm of unification can be used to decide whether a given CCG G is unifiable and, if so, to produce an m.g.u. of G (it is unique up to variants). For rigid CCG s, and any nonempty, finite D F (V ), there holds the following theorem [20]. (T2) There exists a rigid G Ω such that D L f (G) iff GF(D) is unifiable. If σ is an m.g.u. of GF(D), then GF(D)σ is a rigid CCG from Ω whose functor language is the smallest language L(G) such that G Ω is rigid and D L(G).
15 Type Logics in Grammar 335 GF(D) from the above example is unifiable; an m.g.u. σ is the substitution: y/x, z/x S, hence GF(D)σ is given by: Joan x, works x S, hardly (x S) (x S), which agrees with our earlier analysis of these sentences. We define RG(D) =GF(D)σ, if GF(D) is unifiable and σ is an m.g.u. of GF(D). Kanazawa [38, 39] proves that RG({s 0,..., s n }) is a conservative learning function for the class G r, of all rigid grammars from Ω. It is true if one identifies isomorphic grammars. It is easier to show that, for χ(d) =RG(D), the learning function ϕ, defined by (l0)-(l2), learns G r (now, isomorphic grammars need not be identified); this function is conservative. By (T1), one needs (MIN) and finite elasticity of L(G r ). (MIN) holds, by (T2). To prove finite elasticity one may use Kanazawa s lemma on chains of rigid languages: (L2) There exists no infinite sequence (G i ) of rigid CCG s from Ω such that L f (G i ) L f (G i+1 ), for all i ω. We omit a rather involved, combinatorial proof of (L2). Let L be the class L(G r ) enriched with the total language F (V ). Using (L2) and (T2), we prove that L is a closure system. Let {L i } i I be a family of languages from L, and let L be the meet of this family. If I =, then L = F (V ), hence L L. So, we may assume I and L F (V ); further, we may also assume L i L(G r ), for all i I. We consider two cases. (1) L is finite. By (T2), RG(L) exists, and the functor language of RG(L) is the smallest language L L(G r ) such that L L. Consequently, this functor language contains L and is contained in all L i, for i I, hence it equals L. Thus, L L. (2) L is infinite. Let (s i ) be a text for L. We define D n = {s 0,..., s n }. By (T2), RG(D n ) exists, for all n ω. Let L(n) denote the functor language of RG(D n ). Clearly, L(n) L(n + 1) and L(n) L i, for all n ω, i I. By (L2), there exists n ω such that L(m) = L(n), for all m n, and consequently, L = L(n). Again, L L. So, L is a closure system which admits no infinite ascending chains. By the fact on closure systems, proven above, L has finite elasticity, and consequently, L f (G r ) has finite elasticity (this property is preserved by subclasses). This yields the learnability of G r. A CCG G is said to be k valued if {A : (v, A) G} is of cardinality at most k, for any v V. By G k we denote the class of all k valued grammars in Ω. Again, (T1) yields the learnability of G k. To show the finite elasticity of L f (G k ) Kanazawa uses the following lemma.
16 336 W. Buszkowski (L3) Let R E 1 E 2 be a finite valued relation, that means, for any s E 1, there exist at most finitely many t E 2 such that (s, t) R. Let L be a family of languages on E 2 which has finite elasticity. Then, the family {R 1 [L] : L L} has finite elasticity. The proof of (L3) is an application of the König lemma: every infinite, finitely branching tree has an infinite branch. Each atom from V is associated with k copies v 1,..., v k. Let W denote the set of all copies of atoms from V. A mapping f : F (W ) F (V ) is defined by: (i) f(v i ) = v, (ii) f((xy ) i ) = (f(x)f(y )) i. We define a finite valued relation R F (V ) F (W ): (X, Y ) R iff X = f(y ). For any grammar G G k, we define a rigid grammar G with lexicon W in the following way: if A 1,..., A i are all types assigned to v by G, then G assigns A j to v j, for j = 1,..., i. Clearly, L f (G) = R 1 [L f (G )] and L f (G k ) = R 1 [L f (G r )]. So, the latter class has finite elasticity. To prove (MIN) one uses a modification of the construction of RG(D). Let GF k (D) denote the set of all grammars G with lexicon W, satisfying the conditions: for all v V and types A, GF (D) : v A iff, for some i, G : v i A, (ii) if i j then G assigns no common type to both v i and v j. Clearly, GF k (D) is a finite set, efectively constructed from GF(D). Let GF k (D) be defined as follows: (i) construct all grammars Gσ such that G GF k (D), σ is an m.g.u. of G (if exists), (ii) return to lexicon V, by assigning to v all types Gσ assigns to copies of v. GF k (D) is an effectively constructed set of k valued grammars, fulfilling an analogue of (L1): for any k valued grammar G, D L f (G) iff there exist G GF k (D) and substitution σ such that G σ G. Consequently, among languages L f (G), G GF k (D), there appear all minimal languages L such that L = L f (G), for some k valued grammar G with D L f (G). Since the inclusion problem L f (G) L f (G ) is decidable, then we can effectively find a grammar G GF k (D) such that L f (G) is minimal among all languages of grammars from GF k (D), and consequently, among all languages of k valued grammars G such that D L f (G). Accordingly, a function χ satisfying (MIN) exists. Kanazawa also considers learnability from strings. Now, the set E consists of all nonempty strings on V, and L(G) is the string language of G. For X F (V ), by s(x) we denote the string on V resulting from X after one has dropped all structure markers. The relation R between strings and structures, given by: (a, X) R iff a = s(x), is finite valued, and consequently, if L f (G) has finite elasticity, then L(G) has finite elasticity, by (L3). So, both L(G r ) and L(G k ) have finite elasticity, hence G r and G k are learnable from strings, by a general theorem of formal learning theory, mentioned above.
17 Type Logics in Grammar 337 The corresponding learning functions need not be conservative. Kanazawa defines nonconservative learning functions for these classes which use the above constructions performed on all possible structures admissible for a given string. We have discussed learnability from positive data. As observed by Gold [31], if one admits texts consisting of all expressions from E and informing which expressions belong and which expressions do not belong to the language, then every recursively enumerable class of grammars is learnable. The learning function simply picks the first grammar G n (in the fixed recursive sequence of all grammars from the class) which is compatible with the sample. In [20, 56], negative data have been handled in a different way. Samples consist of positive data only, while some negative information is employed to restrict the search space of admissible grammars. In [56], there are considered classes B, of grammars, fulfilling the following conditions: (N1) if G G and G B, then G B, (N2) if Gσ B, then G B. The order of type A is defined by: o(a) = 0, for primitive A, o(a B) = o(b A) = max(o(b), o(a) + 1). Thus, o(p q) = 1 and o((p q) r) = 2. The order of G is the maximal order of types in G; we denote it by o(g). Always o(g) o(gσ), hence the class of all CCG s of order at most n satisfies (N1) and (N2). Another example is the following. We admit Pr contains some other constant types besides S, say PN, N etc. Let X 1,..., X n be structures in F (V ), and let A 1,..., A n be variable-free types. Then, the class of all CCG s which do not assign A i to X i, for i = 1,..., n, satisfies (N1), (N2). A set S, of substitutions, is said to be hereditary, if: ση S entails σ S. If B satisfies (N2), then, for any G, the set of all σ such that Gσ B is hereditary. If B is recursive, then the latter set is recursive. We say that G is unifiable in S if there exists a unifier of G which belongs to S. If S is hereditary, then G is unifiable in S iff the m.g.u. of G exists and belongs to S. Using these facts, all results discussed above for classes G r and G k can also be obtained for these classes restricted to grammars from a recursive class B, fulfilling (N1), (N2). Many results of that kind can be found in [56, 18, 26, 27].
18 338 W. Buszkowski Kanazawa considers similar problems for type grammars based on logics stronger than AB; Moortgat [60] proposes an extension to grammars based on multimodal logics. Recently, Foret has shown that string languages of rigid grammars based on Associative Lambek Calculus (see section 3) admit a limit point, hence this class of grammars is not learnable from strings. Rigidness is not a natural constraint for Lambek grammars, since the Lambek calculus transforms each type to infinitely many types. Consequently, no Lambek grammar is esentially rigid (or k valued), and grammars of that kind seem to require some different notion of learnability. On the other hand, methods discussed above can be adapted to various grammar formalisms, different from CCG but interpretable in it, as e.g. finite state automata, CF-grammars in (generalized) Greibach normal form, planar dependency grammars, and others. Type logics The basic logic AB can be extended in various ways. Lambek [49] has introduced Syntactic Calculus, now called Associative Lambek Calculus (AL). Types are formed out of primitive types by,,. The axioms are (Id) and: (ASS) (A B) C A (B C), A (B C) (A B) C, and inference rules are: (RRES) A B C iff B A C, (LRES) A B C iff A C B, (CUT1) if A B and B C then A C. Theorems of AL (in this format) are simple sequents A B, interpreted as: every expression of type A is also of type B. By (Id), (RRES) and (LRES), one gets: A (A B) B, (B A) A B, which correspond to the reduction rules of AB. AL provides many theorems not derivable in AB, as e.g.: (1) A B (A B), A (B A) B, (2) (A B) (B C) A C, (C B) (B A) C A,
19 Type Logics in Grammar 339 (3) (A B) C A (B C), A (B C) (A B) C, (4) A B (B A), A (A B) B, called expansion, composition, associativity and lifting, respectively. According to (1), type PN (proper noun) can be expanded to NP (noun phrase) equal to S (PN S). As a consequence, noun phrase conjunctions of type (NP NP) NP can be used in contexts like Joan and some teacher, analysed as compound noun phrases. According to (2), the sentence negation not of type S S can be composed with a noun phrase to produce a negated noun phrase, e.g. not every teacher. An application of (3) was observed by Lambek. Let NP equal to (S PN) S be the type of noun phrases on the object position, as in likes every teacher. (PN S) PN is the type of transitive verb phrases. If we assign NP to him, then Joan likes him gives rise to the sequent: NP (PN S) PN (S PN) S S, which is derivable in AL but not in AB (in AL, use (3) to the middle type). The sequence A 1... A n in the antecedent is interpreted as A 1 A n. Type transformations provided by AL are justified by an algebra of types, which is assumed by Lambek but not by Ajdukiewicz and Bar-Hillel. In CCG, types of expressions are completely determined by the initial type assignment of a categorial grammar. If Joan is assigned type PN, then PN is the only type of Joan in all syntactic analyses. According to Lambek, Joan has type PN, but also type NP, NP and infinitely many other types A such that PN A is derivable in AL. Types are interpreted as sets of nonempty strings on a lexicon V (languages on V ). The logical constants,, are interpreted by the following operations on languages: (5) L 1 L 2 = {ab : a L 1, b L 2 }, (6) L 1 \L 2 = {a V + : ( b L 1 )ba L 2 }, (7) L 1 /L 2 = {a V + : ( b L 2 )ab L 1 }. A language model is defined as a pair (V, µ) such that V is a nonempty finite set, and µ is a mapping from Pr into P (V + ). One extends µ to a mapping from Tp (the set of types) into P (V + ), by setting: µ(a B) = µ(a) µ(b), µ(a B) = µ(a)\µ(b), µ(a B) = µ(a)/µ(b). A sequent A B is said to be true in this model, if µ(a) µ(b). It is easy to show that sequents provable in AL are true in all language models. Pentus
20 340 W. Buszkowski [66] proves the completeness: every sequent true in all language models is provable in AL (for product-free sequents, it has been shown in [7]). Since AL is sound and complete with respect to language models, grammars based on AL cannot yield incorrect types of expressions provided that the initial type assignment is correct. Lambek [50] discusses the following example. Let us assign type PN PN to adjectives. Then, AL yields type S to pseudo-sentence Joan likes poor him, if Joan, likes and him are typed as above. Lambek concludes that AL is too strong, and proposes to replace AL by its nonassociative variant without (ASS). Nonassociative Lambek Calculus (NL) is interesting for many reasons, but Lambek s conclusion seems to be misleading. Type PN PN of poor and type (PN S) PN of likes are correct, and the sequent: (PN S) PN PN PN (S PN) S PN S is provable in AL (hence true in language models), but likes poor him is not a syntactically correct expression of type PN S (intransitive verb phrase). The conslusion must be: NP is not a correct type of him. On the other hand, it is difficult to find totally correct types of lexical atoms in natural language. Dropping associativity makes this task easier: now, likes poor is not a syntactically correct expression of type (PN S) PN, hence NP can correctly be assigned to him. So, Lambek is right in his final solution. Language models of NL interpret types as phrase languages on V. Type tranformations in AL correspond to semantic transformations definable in the lambda calculus. Primitive semantic types are t (truth value), e (entity), and possibly others. a b is the type of functions which assign objects of type b to objects of type a. Syntactic types of AL correspond to semantic types: PN corresponds to e, S to t, and A B, B A correspond to a b, where a corresponds to A and b to B. For instance, the semantic type of intransitive verb phrases is e t, of functions which assign truth values to entities; they can be identified with sets of entities. The semantic type corresponding to NP is (e t) t, of functions which assign truth values to objects of type e t; they can be identified with families of sets of entities. (The noun phrase every student denotes the family of all sets W such that every student belongs to W.) We say that a type transformation a 1... a n a is lambda definable, if there exists a lambda term M of type a with free variables x i of type a i, for i = 1,..., n. Let us consider composition (1) for A =PN, B =S. The corresponding type transformation e (e t) t is definable by the term: λx e t.x e t y e,
CHAPTER 7 GENERAL PROOF SYSTEMS 1 Introduction Proof systems are built to prove statements. They can be thought as an inference machine with special statements, called provable statements, or sometimesMore information
A Propositional Dynamic Logic for CCS Programs
A Propositional Dynamic Logic for CCS Programs Mario R. F. Benevides and L. Menasché Schechter {mario,firstname.lastname@example.com Abstract This work presents a Propositional Dynamic Logic in which the programs areMore information
Non-deterministic Semantics and the Undecidability of Boolean BI
1 Non-deterministic Semantics and the Undecidability of Boolean BI DOMINIQUE LARCHEY-WENDLING, LORIA CNRS, Nancy, France DIDIER GALMICHE, LORIA Université Henri Poincaré, Nancy, France We solve the openMore information
M.Sc. program in mathematics INTRODUCTORY SET THEORY Katalin Károlyi Department of Applied Analysis, Eötvös Loránd University H-1088 Budapest, Múzeum krt. 6-8. CONTENTS 1. SETS Set, equal sets, subset,More information
WHAT ARE MATHEMATICAL PROOFS AND WHY THEY ARE IMPORTANT? introduction Many students seem to have trouble with the notion of a mathematical proof. People that come to a course like Math 216, who certainlyMore information
Parametric Domain-theoretic models of Linear Abadi & Plotkin Logic
Parametric Domain-theoretic models of Linear Abadi & Plotkin Logic Lars Birkedal Rasmus Ejlers Møgelberg Rasmus Lerchedahl Petersen IT University Technical Report Series TR-00-7 ISSN 600 600 February 00More information
3. Mathematical Induction
3. MATHEMATICAL INDUCTION 83 3. Mathematical Induction 3.1. First Principle of Mathematical Induction. Let P (n) be a predicate with domain of discourse (over) the natural numbers N = {0, 1,,...}. If (1)More information
Summary Last Lecture. Automated Reasoning. Outline of the Lecture. Definition sequent calculus. Theorem (Normalisation and Strong Normalisation)
Summary Summary Last Lecture sequent calculus Automated Reasoning Georg Moser Institute of Computer Science @ UIBK Winter 013 (Normalisation and Strong Normalisation) let Π be a proof in minimal logicMore information
A set is a Many that allows itself to be thought of as a One. (Georg Cantor)
Chapter 4 Set Theory A set is a Many that allows itself to be thought of as a One. (Georg Cantor) In the previous chapters, we have often encountered sets, for example, prime numbers form a set, domainsMore information
Mathematics for Computer Science/Software Engineering. Notes for the course MSM1F3 Dr. R. A. Wilson
Mathematics for Computer Science/Software Engineering Notes for the course MSM1F3 Dr. R. A. Wilson October 1996 Chapter 1 Logic Lecture no. 1. We introduce the concept of a proposition, which is a statementMore information
CS510 Software Engineering
CS510 Software Engineering Propositional Logic Asst. Prof. Mathias Payer Department of Computer Science Purdue University TA: Scott A. Carr Slides inspired by Xiangyu Zhang http://nebelwelt.net/teaching/15-cs510-seMore information
Remarks on Non-Fregean Logic
STUDIES IN LOGIC, GRAMMAR AND RHETORIC 10 (23) 2007 Remarks on Non-Fregean Logic Mieczys law Omy la Institute of Philosophy University of Warsaw Poland firstname.lastname@example.com 1 Introduction In 1966 famous PolishMore information
CARDINALITY, COUNTABLE AND UNCOUNTABLE SETS PART ONE With the notion of bijection at hand, it is easy to formalize the idea that two finite sets have the same number of elements: we just need to verifyMore information
4 Domain Relational Calculus
4 Domain Relational Calculus We now present two relational calculi that we will compare to RA. First, what is the difference between an algebra and a calculus? The usual story is that the algebra RA isMore information
Likewise, we have contradictions: formulas that can only be false, e.g. (p p).
CHAPTER 4. STATEMENT LOGIC 59 The rightmost column of this truth table contains instances of T and instances of F. Notice that there are no degrees of contingency. If both values are possible, the formulaMore information
Categorial Type Logics
Categorial Type Logics Michael Moortgat Utrecht Institute of Linguistics, OTS Excerpt from Chapter Two in J. van Benthem and A. ter Meulen (eds.) Handbook of Logic and Language. Elsevier, 1997. ContentsMore information
Research Note. Bi-intuitionistic Boolean Bunched Logic
UCL DEPARTMENT OF COMPUTER SCIENCE Research Note RN/14/06 Bi-intuitionistic Boolean Bunched Logic June, 2014 James Brotherston Dept. of Computer Science University College London Jules Villard Dept. ofMore information
Fundamentele Informatica II
Fundamentele Informatica II Answer to selected exercises 1 John C Martin: Introduction to Languages and the Theory of Computation M.M. Bonsangue (and J. Kleijn) Fall 2011 Let L be a language. It is clearMore information
Predicate Logic Review
Predicate Logic Review UC Berkeley, Philosophy 142, Spring 2016 John MacFarlane 1 Grammar A term is an individual constant or a variable. An individual constant is a lowercase letter from the beginningMore information
Classical BI. (A Logic for Reasoning about Dualising Resources) James Brotherston Cristiano Calcagno
Classical BI (A Logic for Reasoning about Dualising Resources) James Brotherston Cristiano Calcagno Dept. of Computing, Imperial College London, UK {jbrother,firstname.lastname@example.com Abstract We show how toMore information
x < y iff x < y, or x and y are incomparable and x χ(x,y) < y χ(x,y).
12. Large cardinals The study, or use, of large cardinals is one of the most active areas of research in set theory currently. There are many provably different kinds of large cardinals whose descriptionsMore information
Regular Languages and Finite Automata
Regular Languages and Finite Automata 1 Introduction Hing Leung Department of Computer Science New Mexico State University Sep 16, 2010 In 1943, McCulloch and Pitts [4] published a pioneering work on aMore information
CODING TRUE ARITHMETIC IN THE MEDVEDEV AND MUCHNIK DEGREES PAUL SHAFER Abstract. We prove that the first-order theory of the Medvedev degrees, the first-order theory of the Muchnik degrees, and the third-orderMore information
Degrees of Truth: the formal logic of classical and quantum probabilities as well as fuzzy sets.
Degrees of Truth: the formal logic of classical and quantum probabilities as well as fuzzy sets. Logic is the study of reasoning. A language of propositions is fundamental to this study as well as trueMore information
Bi-approximation Semantics for Substructural Logic at Work
Bi-approximation Semantics for Substructural Logic at Work Tomoyuki Suzuki Department of Computer Science, University of Leicester Leicester, LE1 7RH, United Kingdom firstname.lastname@example.com AbstractMore information
24. The Branch and Bound Method
24. The Branch and Bound Method It has serious practical consequences if it is known that a combinatorial problem is NP-complete. Then one can conclude according to the present state of science that noMore information
Bulletin of the Section of Logic Volume 15/2 (1986), pp. 72 79 reedition 2005 [original edition, pp. 72 84] Ryszard Ladniak ON THE DEGREE OF MAXIMALITY OF DEFINITIONALLY COMPLETE LOGICS The following definitionMore information
Chapter 7: Functional Programming Languages
Chapter 7: Functional Programming Languages Aarne Ranta Slides for the book Implementing Programming Languages. An Introduction to Compilers and Interpreters, College Publications, 2012. Fun: a languageMore information
Foundational Proof Certificates
An application of proof theory to computer science INRIA-Saclay & LIX, École Polytechnique CUSO Winter School, Proof and Computation 30 January 2013 Can we standardize, communicate, and trust formal proofs?More information
Fixed-Point Logics and Computation
1 Fixed-Point Logics and Computation Symposium on the Unusual Effectiveness of Logic in Computer Science University of Cambridge 2 Mathematical Logic Mathematical logic seeks to formalise the process ofMore information
Introducing Functions
Functions 1 Introducing Functions A function f from a set A to a set B, written f : A B, is a relation f A B such that every element of A is related to one element of B; in logical notation 1. (a, b 1More information
System BV is NP-complete
System BV is NP-complete Ozan Kahramanoğulları 1,2 Computer Science Institute, University of Leipzig International Center for Computational Logic, TU Dresden Abstract System BV is an extension of multiplicativeMore information
The Halting Problem is Undecidable
185 Corollary G = { M, w w L(M) } is not Turing-recognizable. Proof. = ERR, where ERR is the easy to decide language: ERR = { x { 0, 1 }* x does not have a prefix that is a valid code for a Turing machineMore information
C H A P T E R Regular Expressions regular expression
7 CHAPTER Regular Expressions Most programmers and other power-users of computer systems have used tools that match text patterns. You may have used a Web search engine with a pattern like travel cancunMore information
Correspondence analysis for strong three-valued logic
Correspondence analysis for strong three-valued logic A. Tamminga abstract. I apply Kooi and Tamminga s (2012) idea of correspondence analysis for many-valued logics to strong three-valued logic (K 3 ).More information
Logic in general. Inference rules and theorem proving
Logical Agents Knowledge-based agents Logic in general Propositional logic Inference rules and theorem proving First order logic Knowledge-based agents Inference engine Knowledge base Domain-independentMore information
This asserts two sets are equal iff they have the same elements, that is, a set is determined by its elements.
3. Axioms of Set theory Before presenting the axioms of set theory, we first make a few basic comments about the relevant first order logic. We will give a somewhat more detailed discussion later, butMore information
Automata and Formal Languages
Automata and Formal Languages Winter 2009-2010 Yacov Hel-Or 1 What this course is all about This course is about mathematical models of computation We ll study different machine models (finite automata,More information
(LMCS, p. 317) V.1. First Order Logic. This is the most powerful, most expressive logic that we will examine.
(LMCS, p. 317) V.1 First Order Logic This is the most powerful, most expressive logic that we will examine. Our version of first-order logic will use the following symbols: variables connectives (,,,,More information
Theory of Computation
Theory of Computation For Computer Science & Information Technology By www.thegateacademy.com Syllabus Syllabus for Theory of Computation Regular Expressions and Finite Automata, Context-Free Grammar sMore information
Logical Methods in Computer Science Vol. 6 (3:3) 2010, pp. 1 42 www.lmcs-online.org Submitted Aug. 1, 2009 Published Jul. 20, 2010 CLASSICAL BI: ITS SEMANTICS AND PROOF THEORY JAMES BROTHERSTON a AND CRISTIANOMore information
3. Equivalence Relations. Discussion
3. EQUIVALENCE RELATIONS 33 3. Equivalence Relations 3.1. Definition of an Equivalence Relations. Definition 3.1.1. A relation R on a set A is an equivalence relation if and only if R is reflexive, symmetric,More information
A Note on Context Logic
A Note on Context Logic Philippa Gardner Imperial College London This note describes joint work with Cristiano Calcagno and Uri Zarfaty. It introduces the general theory of Context Logic, and has beenMore information
Local periods and binary partial words: An algorithm
Local periods and binary partial words: An algorithm F. Blanchet-Sadri and Ajay Chriscoe Department of Mathematical Sciences University of North Carolina P.O. Box 26170 Greensboro, NC 27402 6170, USA E-mail:More information
Finite Automata and Formal Languages
Finite Automata and Formal Languages TMV026/DIT321 LP4 2011 Lecture 14 May 19th 2011 Overview of today s lecture: Turing Machines Push-down Automata Overview of the Course Undecidable and Intractable ProblemsMore information
A first step towards modeling semistructured data in hybrid multimodal logic
A first step towards modeling semistructured data in hybrid multimodal logic Nicole Bidoit * Serenella Cerrito ** Virginie Thion * * LRI UMR CNRS 8623, Université Paris 11, Centre d Orsay. ** LaMI UMRMore information
INCIDENCE-BETWEENNESS GEOMETRY MATH 410, CSUSM. SPRING 2008. PROFESSOR AITKEN This document covers the geometry that can be developed with just the axioms related to incidence and betweenness. The fullMore information
Computability Theory
CSC 438F/2404F Notes (S. Cook and T. Pitassi) Fall, 2014 Computability Theory This section is partly inspired by the material in A Course in Mathematical Logic by Bell and Machover, Chap 6, sections 1-10.More information
EMBEDDING COUNTABLE PARTIAL ORDERINGS IN THE ENUMERATION DEGREES AND THE ω-enumeration DEGREES MARIYA I. SOSKOVA AND IVAN N. SOSKOV 1. Introduction One of the most basic measures of the complexity of aMore information
Which Semantics for Neighbourhood Semantics?
Which Semantics for Neighbourhood Semantics? Carlos Areces INRIA Nancy, Grand Est, France Diego Figueira INRIA, LSV, ENS Cachan, France Abstract In this article we discuss two alternative proposals forMore information
Discrete Mathematics and Probability Theory Fall 2009 Satish Rao, David Tse Note 2
CS 70 Discrete Mathematics and Probability Theory Fall 2009 Satish Rao, David Tse Note 2 Proofs Intuitively, the concept of proof should already be familiar We all like to assert things, and few of usMore information
Finite Sets. Theorem 5.1. Two non-empty finite sets have the same cardinality if and only if they are equivalent.
MATH 337 Cardinality Dr. Neal, WKU We now shall prove that the rational numbers are a countable set while R is uncountable. This result shows that there are two different magnitudes of infinity. But weMore information
Lights and Darks of the Star-Free Star
Lights and Darks of the Star-Free Star Edward Ochmański & Krystyna Stawikowska Nicolaus Copernicus University, Toruń, Poland Introduction: star may destroy recognizability In (finitely generated) traceMore information
! " # The Logic of Descriptions. Logics for Data and Knowledge Representation. Terminology. Overview. Three Basic Features. Some History on DLs
,!0((,.+#$),%$(-&.& *,2(-$)%&2.'3&%!&, Logics for Data and Knowledge Representation Alessandro Agostini firstname.lastname@example.com University of Trento Fausto Giunchiglia email@example.com The Logic of Descriptions!$%&'()*$#)More information
Étale groupoids and their morphisms
Étale groupoids and their morphisms Ganna Kudryavtseva University of Ljubljana Semigroup Representations 2013 Edinburgh Ganna Kudryavtseva (Ljubljana) Étale groupoids and their morphisms April 11, 2013More information
The Banach-Tarski Paradox
University of Oslo MAT2 Project The Banach-Tarski Paradox Author: Fredrik Meyer Supervisor: Nadia S. Larsen Abstract In its weak form, the Banach-Tarski paradox states that for any ball in R, it is possibleMore information
Dedekind s forgotten axiom and why we should teach it (and why we shouldn t teach mathematical induction in our calculus classes)
Dedekind s forgotten axiom and why we should teach it (and why we shouldn t teach mathematical induction in our calculus classes) by Jim Propp (UMass Lowell) March 14, 2010 1 / 29 Completeness Three commonMore information
Notes on Richard Dedekind s Was sind und was sollen die Zahlen?
Notes on Richard Dedekind s Was sind und was sollen die Zahlen? David E. Joyce, Clark University December 2005 Contents Introduction 2 I. Sets and their elements. 2 II. Functions on a set. 5 III. One-to-oneMore information
Computational Logic and Cognitive Science: An Overview
Computational Logic and Cognitive Science: An Overview Session 1: Logical Foundations Technical University of Dresden 25th of August, 2008 University of Osnabrück Who we are Helmar Gust Interests: AnalogicalMore information
This chapter is all about cardinality of sets. At first this looks like a
CHAPTER Cardinality of Sets This chapter is all about cardinality of sets At first this looks like a very simple concept To find the cardinality of a set, just count its elements If A = { a, b, c, d },More information
Formal Languages and Automata Theory - Regular Expressions and Finite Automata -
Formal Languages and Automata Theory - Regular Expressions and Finite Automata - Samarjit Chakraborty Computer Engineering and Networks Laboratory Swiss Federal Institute of Technology (ETH) Zürich MarchMore information
Foundations of mathematics
Foundations of mathematics 1. First foundations of mathematics 1.1. Introduction to the foundations of mathematics Mathematics, theories and foundations Sylvain Poirier http://settheory.net/ MathematicsMore information
Sets and Cardinality Notes for C. F. Miller
Sets and Cardinality Notes for 620-111 C. F. Miller Semester 1, 2000 Abstract These lecture notes were compiled in the Department of Mathematics and Statistics in the University of Melbourne for the useMore information
Introduction to Automata Theory. Reading: Chapter 1
Introduction to Automata Theory Reading: Chapter 1 1 What is Automata Theory? Study of abstract computing devices, or machines Automaton = an abstract computing device Note: A device need not even be aMore information
THE TURING DEGREES AND THEIR LACK OF LINEAR ORDER JASPER DEANTONIO Abstract. This paper is a study of the Turing Degrees, which are levels of incomputability naturally arising from sets of natural numbers.More information
First-Order Logics and Truth Degrees
First-Order Logics and Truth Degrees George Metcalfe Mathematics Institute University of Bern LATD 2014, Vienna Summer of Logic, 15-19 July 2014 George Metcalfe (University of Bern) First-Order LogicsMore information
Theory of Computation Lecture Notes
Theory of Computation Lecture Notes Abhijat Vichare August 2005 Contents 1 Introduction 2 What is Computation? 3 The λ Calculus 3.1 Conversions: 3.2 The calculus in use 3.3 Few Important Theorems 3.4 WorkedMore information
Metric Spaces. Chapter 1
Chapter 1 Metric Spaces Many of the arguments you have seen in several variable calculus are almost identical to the corresponding arguments in one variable calculus, especially arguments concerning convergenceMore information
Chapter 4, Arithmetic in F [x] Polynomial arithmetic and the division algorithm.
Chapter 4, Arithmetic in F [x] Polynomial arithmetic and the division algorithm. We begin by defining the ring of polynomials with coefficients in a ring R. After some preliminary results, we specializeMore information
Foundations of Geometry 1: Points, Lines, Segments, Angles
Chapter 3 Foundations of Geometry 1: Points, Lines, Segments, Angles 3.1 An Introduction to Proof Syllogism: The abstract form is: 1. All A is B. 2. X is A 3. X is B Example: Let s think about an example.More information
Degrees that are not degrees of categoricity
Degrees that are not degrees of categoricity Bernard A. Anderson Department of Mathematics and Physical Sciences Gordon State College email@example.com www.gordonstate.edu/faculty/banderson BarbaraMore information
Relations: their uses in programming and computational specifications
PEPS Relations, 15 December 2008 1/27 Relations: their uses in programming and computational specifications Dale Miller INRIA - Saclay & LIX, Ecole Polytechnique 1. Logic and computation Outline 2. ComparingMore information
Chapter 6: Episode discovery process
Chapter 6: Episode discovery process Algorithmic Methods of Data Mining, Fall 2005, Chapter 6: Episode discovery process 1 6. Episode discovery process The knowledge discovery process KDD process of analyzingMore information
Completeness Theorems for Syllogistic Fragments
Completeness Theorems for Syllogistic Fragments Lawrence S. Moss Department of Mathematics Indiana University Bloomington, IN 47405 USA Comments/Corrections Welcome! Abstract Traditional syllogisms involveMore information
Logic, Algebra and Truth Degrees 2008. Siena. A characterization of rst order rational Pavelka's logic
Logic, Algebra and Truth Degrees 2008 September 8-11, 2008 Siena A characterization of rst order rational Pavelka's logic Xavier Caicedo Universidad de los Andes, Bogota Under appropriate formulations,More information
Contemporary Mathematics THIN GROUPS OF FRACTIONS Patrick DEHORNOY Abstract. A number of properties of spherical Artin Tits groups extend to Garside groups, defined as the groups of fractions of monoidsMore information
Testing LTL Formula Translation into Büchi Automata
Testing LTL Formula Translation into Büchi Automata Heikki Tauriainen and Keijo Heljanko Helsinki University of Technology, Laboratory for Theoretical Computer Science, P. O. Box 5400, FIN-02015 HUT, FinlandMore information
Properties of Stabilizing Computations
Theory and Applications of Mathematics & Computer Science 5 (1) (2015) 71 93 Properties of Stabilizing Computations Mark Burgin a a University of California, Los Angeles 405 Hilgard Ave. Los Angeles, CAMore information
THE SEARCH FOR NATURAL DEFINABILITY IN THE TURING DEGREES ANDREW E.M. LEWIS 1. Introduction This will be a course on the Turing degrees. We shall assume very little background knowledge: familiarity withMore information
Algebraic Recognizability of Languages
of Languages LaBRI, Université Bordeaux-1 and CNRS MFCS Conference, Prague, August 2004 The general problem Problem: to specify and analyse infinite sets by finite means The general problem Problem: toMore information
Bindings, mobility of bindings, and the -quantifier
ICMS, 26 May 2007 1/17 Bindings, mobility of bindings, and the -quantifier Dale Miller, INRIA-Saclay and LIX, École Polytechnique This talk is based on papers with Tiu in LICS2003 & ACM ToCL, and experienceMore information
University of Ostrava. Reasoning in Description Logic with Semantic Tableau Binary Trees
University of Ostrava Institute for Research and Applications of Fuzzy Modeling Reasoning in Description Logic with Semantic Tableau Binary Trees Alena Lukasová Research report No. 63 2005 Submitted/toMore information
Markov Algorithm. CHEN Yuanmi December 18, 2007
Markov Algorithm CHEN Yuanmi December 18, 2007 1 Abstract Markov Algorithm can be understood as a priority string rewriting system. In this short paper we give the definition of Markov algorithm and alsoMore information
Simulation-Based Security with Inexhaustible Interactive Turing Machines
Simulation-Based Security with Inexhaustible Interactive Turing Machines Ralf Küsters Institut für Informatik Christian-Albrechts-Universität zu Kiel 24098 Kiel, Germany email@example.com information
Applications of Methods of Proof
CHAPTER 4 Applications of Methods of Proof 1. Set Operations 1.1. Set Operations. The set-theoretic operations, intersection, union, and complementation, defined in Chapter 1.1 Introduction to Sets areMore information
POWER SETS AND RELATIONS L. MARIZZA A. BAILEY 1. The Power Set Now that we have defined sets as best we can, we can consider a sets of sets. If we were to assume nothing, except the existence of the emptyMore information
Scalable Automated Symbolic Analysis of Administrative Role-Based Access Control Policies by SMT solving
Scalable Automated Symbolic Analysis of Administrative Role-Based Access Control Policies by SMT solving Alessandro Armando 1,2 and Silvio Ranise 2, 1 DIST, Università degli Studi di Genova, Italia 2 SecurityMore information
Reading 13 : Finite State Automata and Regular Expressions
CS/Math 24: Introduction to Discrete Mathematics Fall 25 Reading 3 : Finite State Automata and Regular Expressions Instructors: Beck Hasti, Gautam Prakriya In this reading we study a mathematical modelMore information
Omega Automata: Minimization and Learning 1
Omega Automata: Minimization and Learning 1 Oded Maler CNRS - VERIMAG Grenoble, France 2007 1 Joint work with A. Pnueli, late 80s Summary Machine learning in general and of formal languages in particularMore information
ON UNIQUE FACTORIZATION DOMAINS JIM COYKENDALL AND WILLIAM W. SMITH Abstract. In this paper we attempt to generalize the notion of unique factorization domain in the spirit of half-factorial domain. ItMore information
Handout #1: Mathematical Reasoning
Math 101 Rumbos Spring 2010 1 Handout #1: Mathematical Reasoning 1 Propositional Logic A proposition is a mathematical statement that it is either true or false; that is, a statement whose certainty orMore information
So let us begin our quest to find the holy grail of real analysis.
1 Section 5.2 The Complete Ordered Field: Purpose of Section We present an axiomatic description of the real numbers as a complete ordered field. The axioms which describe the arithmetic of the real numbersMore information
EQUATIONAL LOGIC AND ABSTRACT ALGEBRA * Taje I. Ramsamujh Florida International University Mathematics Department ABSTRACT Equational logic is a formalization of the deductive methods encountered in studyingMore information
We give a basic overview of the mathematical background required for this course.
1 Background We give a basic overview of the mathematical background required for this course. 1.1 Set Theory We introduce some concepts from naive set theory (as opposed to axiomatic set theory). TheMore information
Partitioning edge-coloured complete graphs into monochromatic cycles and paths
arxiv:1205.5492v1 [math.co] 24 May 2012 Partitioning edge-coloured complete graphs into monochromatic cycles and paths Alexey Pokrovskiy Departement of Mathematics, London School of Economics and PoliticalMore information
A Beginner s Guide to Modern Set Theory
A Beginner s Guide to Modern Set Theory Martin Dowd Product of Hyperon Software PO Box 4161 Costa Mesa, CA 92628 www.hyperonsoft.com Copyright c 2010 by Martin Dowd 1. Introduction..... 1 2. Formal logic......More information
Consistency, completeness of undecidable preposition of Principia Mathematica. Tanmay Jaipurkar
Consistency, completeness of undecidable preposition of Principia Mathematica Tanmay Jaipurkar October 21, 2013 Abstract The fallowing paper discusses the inconsistency and undecidable preposition of PrincipiaMore information
ML for the Working Programmer
ML for the Working Programmer 2nd edition Lawrence C. Paulson University of Cambridge CAMBRIDGE UNIVERSITY PRESS CONTENTS Preface to the Second Edition Preface xiii xv 1 Standard ML 1 Functional ProgrammingMore information
Chapter II. Controlling Cars on a Bridge
Chapter II. Controlling Cars on a Bridge 1 Introduction The intent of this chapter is to introduce a complete example of a small system development. During this development, you will be made aware of theMore information
DEGREES OF ORDERS ON TORSION-FREE ABELIAN GROUPS ASHER M. KACH, KAREN LANGE, AND REED SOLOMON Abstract. We construct two computable presentations of computable torsion-free abelian groups, one of isomorphismMore information


text:
The Gatsby email newsletter
Sign up to receive our monthly email newsletter featuring information about upcoming performances and ticket dates.
You must be 13 or older to submit any information to Minnesota Public Media. The personally identifying information you provide will not be sold, shared, or used for purposes other than to communicate with you about things like our programs, products, and services. See Minnesota Public Radio's Terms of Use and Privacy Statement.