Mesh Selection for a Nearly Singular Boundary Value Problem

In this paper, we investigate the numerical solution of a model equation u _xx = exp(– ) (and several slightly more general problems) when 1 using the standard central difference scheme on nonuniform grids. In particular, we are interested in the error behaviour in two limiting cases: (i) the total mesh point number N is fixed when the regularization parameter 0, and (ii) is fixed when N. Using a formal analysis, we show that a generalized version of a special piecewise uniform mesh 12 and an adaptive grid based on the equidistribution principle share some common features. And the optimal meshes give rates of convergence bounded by |log()| as 0 and N is given, which are shown to be sharp by numerical tests.     

Context-sensitive immediate constituent analysis: Context-free languages revisited

The ability of context-sensitive grammars togenerate non-context-free languages is well known. However, phrase-structure rules are often used in both natural and artificial languages, not to generate sentences, but rather toanalyze or parse given putative sentences. Linguistic arguments have been advanced that this is the more fruitful use of CS rules for natural languages, and that, further, it is the purported phrasestructure tree which is presented and analyzed, rather than merely the terminal string itself. In this interpretation, for example the rules {S AB, A a/__b, B b/ a__} parse the sentenceab for they analyze the tree represented by the labeled bracketing [_S[_Aa]_A[_Bb]_B]_S, even though these rules do not generateab when interpreted as a CS grammar.We shall say that a languageL is parsed by the finite setR of context-sensitive rules ifL consists of the terminal strings of trees analyzed byR. An actual parsing of an artificial language might be obtained, for example, by using a standard parsing algorithm for the associated CF grammar (obtained by deleting all contexts from rules) to generate putative trees and then analyzing these trees with the given CS grammar. In this paper, a language is shown to becontext-free if and only if there is a finite set ofcontext-sensitive rules which parse this language; i.e., if and only if there is a collection of trees whose terminal strings are the sentences of this language and a finite set of CS rules which analyze exactly these trees.This work was supported in part by the 1968 Advanced Research Seminar in Mathematical Linguistics, sponsored by the Mathematical Social Science Board, Center for Advanced Study in the Behavioral Sciences. The authors wish also to acknowledge their debt to Dr. Robert E. Wall for several helpful and stimulating conversations about this material. It was presented at the Association for Computing Machinery Symposium on the Theory of Computing held in Marina del rey, California in May 1969.     

Condensed detachment is complete for relevance logic: A computer-aided proof

The condensed detachment ruleD is a combination of modus ponens with a minimal amount of substitution. EarlierD has been shown to be complete for intuitionistic and classical implicational logic but incomplete forBCK andBCI logic. We show thatD is complete for the relevance logic. One of the main steps is the proof of the formula ((a a) a) a found in interaction with our resolution theorem prover. Various strategies of generating consequences of the axioms and choosing best ones for the next iteration were tried until the proof was found.     

A combinatorial property of EOL languages

Let be an alphabet and II its nontrivial binary partition. Each word over can uniquely be decomposed in subwords (called blocks) consisting of letters of II _i only,i {1,2}. LetK ^*.K has a long block property (with respect to II), abbreviated asLB-property, if there exists a functionf:N ⁺ N ⁺ such that for everyw K and every positive integerm the number of blocks of length at mostm inw is bounded byf(m). K has a clustered block property (with respect to II), abbreviated asCB-property, if there exists a positive integern _o and a growing functiong:N ⁺ N ⁺ such that for everyw K and for every positive integerm the blocks of length at mostm can be covered by at mostn _o segments of length at mostg(m).It is proved that aCB-property always implies aLB-property but not necessarily other way around. It is proved that an EOL language has aLB-property if and only if it has aCB-property.     

The plane with parallel coordinates

By means ofParallel Coordinates planar graphs of multivariate relations are obtained. Certain properties of the relationship correspond tothe geometrical properties of its graph. On the plane a point line duality with several interesting properties is induced. A new duality betweenbounded and unbounded convex sets and hstars (a generalization of hyperbolas) and between Convex Unions and Intersections is found. This motivates some efficient Convexity algorithms and other results inComputational Geometry. There is also a suprising cusp inflection point duality. The narrative ends with a preview of the corresponding results inR ^N .     

Types with intersection: An introduction

This paper is an informal introduction to the theory of types which use a connective for the intersection of two types and a constant for a universal type, besides the usual connective for function-types. This theory was first devised in about 1977 by Coppo, Dezani and Sallé in the context of-calculus and its main development has been by Coppo and Dezani and their collaborators in Turin. With suitable axioms and rules to assign types to-calculus terms, they obtained a system in which (i) the set of types given to a term does not change under-conversion, (ii) some interesting sets of terms, for example the solvable terms and the terms with normal form, can be characterised exactly by the types of their members, and (iii) the type-apparatus is not so complex as polymorphic systems with quantifier-containing types and therefore probably not so expensive to implement mechanically as these systems.There are in fact several variant systems with different detailed properties. This paper defines and motivates the simplest one from which the others are derived, and describes its most basic properties. No proofs are given but the motivation is shown by examples. A comprehensive bibliography is included.     

On Bounding Solutions of Underdetermined Systems

Sufficient conditions for the existence and uniqueness of a solution x* D (R ⁿ ) of Y(x) = 0 where : R ⁿ R ^m (m n) with C ²(D) where D R ⁿ is an open convex set and Y = (x)⁺ are given, and are compared with similar results due to Zhang, Li and Shen (Reliable Computing 5(1) (1999)). An algorithm for bounding zeros of f (·) is described, and numerical results for several examples are given.     

Sur les générateurs algébriques et linéaires

Résumé Nous étudions certaines propriétés des générateurs algébriques et linéaires. Nous montrons que le langage algébrique E engendré par la grammaire: S aSbSc + d domine tous les langages algébriques par applications séquentielles fidèles. Nous en déduisons que pour tout langage algébrique L et tout générateur algébrique L, il existe une transduction rationnelle fonctionnelle et fidèle telle que L=(L). Ce résultat, qui n'est pas vérifié pour la famille, Lin, des langages algébriques linéaires, nous permet de montrer qu'aucun générateur algébrique n'appartient à la famille EDTOL. Enfin, nous établissons que si L est un générateur linéaire, L # est un générateur séquentiel pour Lin.

---

Algebraic and linear generators

Summary We study some properties of algebraic and linear generators. We show that the algebraic language E generated by the grammar: S aSbSc + d dominates every algebraic language by faithful sequential mappings. We deduce that, for every algebraic language L and every algebraic generator L, there exists a faithful rational function such that L=(L). This result, which does not hold for the family of linear languages, permits us to show that no algebraic generator belongs to the family EDTOL. Also, we prove if L is a linear generator then L # is a sequential generator for Lin.

     

On characterizations of recursively enumerable languages

Summary Geffert has shown that earch recursively enumerable languageL over can be expressed in the formL{h(x) ^–1 g(x)x in ⁺} ^* where is an alphabet andg, h is a pair of morphisms. Our purpose is to give a simple proof for Geffert's result and then sharpen it into the form where both of the morphisms are nonerasing. In our method we modify constructions used in a representation of recursively enumerable languages in terms of equality sets and in a characterization of simple transducers in terms of morphisms. As direct consequences, we get the undecidability of the Post correspondence problem and various representations ofL. For instance,L =(L ₀) ^* whereL ₀ is a minimal linear language and is the Dyck reductiona, A.     

A unary representation result for systemT

After an introduction to the syntax of Gödel systemT, we present its naive denotational semantics in the domain of lazy natural numbers and show an adequacy property relating syntax and semantics. We recall the natural restrictions of systemT delineating primitive recursion as a subsystem. We discuss the weakness of primitive recursion by exhibiting a simple unary algorithm whose denotation is not the semantics of a primitive recursive algorithm. This algorithm can nevertheless be programmed in systemT by using the power of higher-order (functional) definitions. Generalizing this example, we obtain a representation theorem, asserting that every reasonable algorithm of typeN N can be programmed in systemT. We conclude by discussing what is known in the case of higher arities.     

An extension of the theory of learning systems

Summary The author's inquiry [1] on learning systems is generalized in the following respects: The process of learning, instead of coming to an end when the learning goal has been reached, is supposed to last for ever, so that the above definitive learning as well as phenomena such as forgetting, re-learning, changing the goal etc. become describable.We take over the notion of semi-uniform solvability of a set of learning problems (2.2), but now (trivial cases excluded) the whole capacity of a learning system is never s. u. solvable. Finite such sets are. The notion of a solving-basis of some is introduced and we can state necessary conditions that possess such a basis (2.14), so that examples of sets without a basis can be provided. On the other hand, any s. u. solvable has as basis. The notion of uniform solvability (3.1) reinforces that of s. u. solvability, and there are given sufficient conditions for to be uniformly solvable (3.6). In some finite cases, s. u. solvability, existence of a basis and uniform solvability coincide (3.7–3.9). At last we give the construction for the weakest learning system solving a uniformly solvable problem set (3.12–3.19).Eine deutsche Fassung wurde am 30. Mai 1972 eingereicht.     

Randomness in interactive proofs

This paper initiates a study of the quantitative aspects of randomness in interactive proofs. Our main result, which applies to the equivalent form of IP known as Arthur-Merlin (AM) games, is a randomness-efficient technique for decreasing the error probability. Given an AM proof system forL which achieves error probability 1/3 at the cost of Arthur sendingl(n) random bits per round, and given a polynomialk=k(n), we show how to construct an AM proof system forL which, in the same number of rounds as the original proof system, achieves error 2 ^–k(n) at the cost of Arthur sending onlyO(l+k) random bits per round.Underlying the transformation is a novel sampling method for approximating the average value of an arbitrary functionf:{0,1} ^l [0,1]. The method evaluates the function onO(^–2 log ^–1) sample points generated using onlyO(l + log ^–1) coin tosses to get an estimate which with probability at least 1- is within of the average value of the function.     

Unique reconstruction of piecewise-smooth images by minimizing strictly convex nonquadratic functionals

We propose the minimization of a nonquadratic functional or, equivalently, a nonlinear diffusion model to smooth noisy image functionsg: R ⁿ R while preserving significant transitions of the data. The model is chosen such that important properties of the conventional quadratic-functional approach still hold: (1) existence of a unique solution continuously depending on the datag and (2) stability of approximations using the standard finite-element method. Relations with other global approaches for the segmentation of image data are discussed. Numerical experiments with real data illustrate this approach.This work was supported by the ESPRIT project SUBSYM.     

Pushing Convertible Constraints in Frequent Itemset Mining

Recent work has highlighted the importance of the constraint-based mining paradigm in the context of frequent itemsets, associations, correlations, sequential patterns, and many other interesting patterns in large databases. Constraint pushing techniques have been developed for mining frequent patterns and associations with antimonotonic, monotonic, and succinct constraints. In this paper, we study constraints which cannot be handled with existing theory and techniques in frequent pattern mining. For example, avg(S)v, median(S)v, sum(S)v (S can contain items of arbitrary values, {<, <, , } and v is a real number.) are customarily regarded as tough constraints in that they cannot be pushed inside an algorithm such as Apriori. We develop a notion of convertible constraints and systematically analyze, classify, and characterize this class. We also develop techniques which enable them to be readily pushed deep inside the recently developed FP-growth algorithm for frequent itemset mining. Results from our detailed experiments show the effectiveness of the techniques developed.     

Interval Computation of Viswanath's Constant

Viswanath has shown that the terms of the random Fibonacci sequences defined by t ₁ = t ₂ = 1, and t _n–1 ± t _n–2 for n > 2, where each ± sign is chosen randomly, increase exponentially in the sense that 1.13198824... as n with probability 1. Viswanath computed this approximation for this limit with floating-point arithmetic and provided a rounding-error analysis to validate his computer calculation. In this note, we show how to avoid this rounding-error analysis by using interval arithmetic.     

Comparative complexity of the representation of languages by probabilistic automata

We analyze the effect of the degree of isolation of a cut point on the number of states P(U, ) of a probabilistic automaton representing the language U. We give an example of a language Uⁿ consisting of words of length n such that there exist numbers < for which P(Uⁿ, )/P(Uⁿ, )0 as n.Translated from Kibernetika, No. 3, pp. 21–25, May–June, 1989.     

The conjoinability relation in Lambek calculus and linear logic

In 1958 J. Lambek introduced a calculusL of syntactic types and defined an equivalence relation on types: x y means that there exists a sequence x=x₁,...,x_n=y (n 1), such thatx _i x _i+1 or x_i+ x _i (1 i n). He pointed out thatx y if and only if there is joinz such thatx z andy z. This paper gives an effective characterization of this equivalence for the Lambeck calculiL andLP, and for the multiplicative fragments of Girard's and Yetter's linear logics. Moreover, for the non-directed Lambek calculusLP and the multiplicative fragment of Girard's linear logic, we present linear time algorithms deciding whether two types are equal, and finding a join for them if they are.The author was sponsored by project NF 102/62-356 (Structural and Semantic Parallels in Natural Languages and Programming Languages), funded by the Netherlands Organization for the Advancement of Research (N.W.O.).     

Representation theorems for fuzzy orders and quasi-metrics

Given a complete residuated lattice (L,,,*,,0,1), we show that any *-preorder can be represented both by an implication-based graded inclusion as defined [1] and by a similarity-based graded inclusion as defined in [2]. Also, in accordance with a duality between fuzzy orders and quasi-metrics, we obtain two corresponding representation theorems for quasi-metrics.     

Generating Boolean \mu-expressions

In this paper, we consider the class of Boolean -functions, which are the Boolean functions definable by -expressions (Boolean expressions in which no variable occurs more than once). We present an algorithm which transforms a Boolean formulaE into an equivalent -expression-if possible-in time linear in E times , where E is the size ofE andn _m is the number of variables that occur more than once inE. As an application, we obtain a polynomial time algorithm for Mundici's problem of recognizing -functions fromk-formulas [17]. Furthermore, we show that recognizing Boolean -functions is co-NP-complete for functions essentially dependent on all variables and we give a bound close to co-NP for the general case.     

A regularity test for dual bordered OS systems

Summary A dual bordered OS system is a triple (, P, S) where is a finite alphabet, S a finite subset of ^*, the set of axioms, and P a finite set of rules of the form aa × a, where a and x ^*. Using well-quasi-order theory, we show that the regularity problem for such systems is decidable. Whether such a system generates a regular language essentially only depends on the set of rules but not on the axioms.