In the first part of this paper, two arguments, one by Chomsky, and one by Bar-Hillel and Shamir, are examined in detail and rejected. Both arguments purport to show that the structure of English precludes its having a finite state grammar which correctly enumerates just the well formed sentences of English. In the latter part of the paper I consider the problem of supporting claims about the structure and properties of a natural language when no grammar for the language has (...) yet been accepted. (shrink)

We show that derivations in the nonassociative and commutative Lambek calculus with product can be transformed to a normal form as it is the case with derivations in noncommutative calculi. As an application we obtain that the class of languages generated by categorial grammars based on the nonassociative and commutative Lambek calculus with product is included in the class of CF-languages. MSC: 68Q50, 03D15, 03B65.

Timing diagrams are popular in hardware design. They have been formalized for use in reasoning tasks, such as computer-aided verification. These efforts have largely treated timing diagrams as interfaces to established notations for which verification is decidable; this has restricted timing diagrams to expressing only regular language properties. This paper presents a timing diagram logic capable of expressing certain context-free and context-sensitive properties. It shows that verification is decidable for properties expressible in this logic. More specifically, it shows that containment (...) of -regular languages generated by Büchi automata in timing diagram languages is decidable. The result relies on a correlation between timing diagram and reversal bounded counter machine languages. (shrink)