Efficient Solution of Multi-Term Fractional Differential Equations Using P(EC)<Superscript><Emphasis Type="Italic">m</Emphasis></Superscript>E Methods

We investigate strategies for the numerical solution of the initial value problem with initial conditions where 0<₁<₂<<. Here y ⁽ _j ) denotes the derivative of order _j >0 (not necessarily _j ) in the sense of Caputo. The methods are based on numerical integration techniques applied to an equivalent nonlinear and weakly singular Volterra integral equation. The classical approach leads to an algorithm with very high arithmetic complexity. Therefore we derive an alternative that leads to lower complexity without sacrificing too much precision. Mathematics Subject Classification: Primary 65L05; Secondary 65L06, 65L20     

The Expressibility of First Order Dynamic Logic

This paper resolved an open problem proposed by A .P. Stolboushkin and M .A. Taitslin.We studied the expressibility of first order dynamic logic, and constructed infinite recursive programclasses K_1 , K_2, …, RG K_1 K_2 … RF, such that L (RG)相似文献   

Abstract Data Types Can Have Inequations<Superscript>1</Superscript>

Abstract. This work proposes a typed functional wide-spectrum language, Funiq, for both programming and specification as an extension of Cardelli-Wegners Fun enriched with the fixed-point construction on expressions and inequational refinements (as assertions) for types. The type system of our wide-spectrum Funiq language is shown to be a conservative extension of that of the original Fun and sound with respect to the complete PER semantics for types.¹ An extended abstract of an earlier version of this work appeared under the title basic properties of data types with inequational refinements (extended abstract) without any proofs and using a slightly (but non-trivially, from the technical viewpoint) different formulation of the system in Typed Lambda Calculi and Applications (ed. by M. Dezani-Ciancaglini and G. Plotkin), Lecture Notes in Computer Science 902, 279–296 (Springer-Verlag); Proceedings of the 2nd International Conference on Typed Lambda Calculi and Applications, TLCA95, held in Edinburgh, UK, 10–12 April 1995.     

Independent finite automata on Cayley graphs

In the setting of symbolic dynamics on discrete finitely generated infinite groups, we define a model of finite automata with multiple independent heads that walk on Cayley graphs, called group-walking automata, and use it to define subshifts. We characterize the torsion groups (also known as periodic groups) as those on which the group-walking automata are strictly weaker than Turing machines, and those on which the head hierarchy is infinite.     

The Expressive Power of Finitely Many Generalized Quantifiers

We consider extensions of first order logic (FO) and fixed point logic (FP) by means of generalized quantifiers in the sense of Lindström. We show that adding a finite set of such quantifiers to FP fails to capture PTIME, even over a fixed signature, strengthening earlier results. We also prove a stronger version of this result for PSPACE, which enables us to establish that PSPACE ≠ FO on any infinite class of ordered structures, a weak version of the ordered conjecture formulated by Ph. G. Kolaitis and M. Y. Vardi (Fixpoint logic vs. infinitary logic in finite-model theory, in "Proceedings, 7th IEEE Symposium on Logic in Computer Science, 1992," pp. 46-57). These results are obtained by defining a notion of element type for bounded variable logics with finitely many generalized quantifiers. Using these, we characterize the classes of finite structures over which the infinitary logic L^ω_∞ω extended by a finite aw set of generalized quantifiers Q is no more expressive than first order logic extended by the quantifiers in Q.     

The Computational Complexity of One-Dimensional Sandpiles

We prove that the one-dimensional sandpile prediction problem is in LOGDCFL, a subset of AC¹. The previously best known upper bound on the ACⁱ-scale was AC². Furthermore, we prove that the one-dimensional sandpile prediction problem is hard for TC⁰ and thus not in AC^1-ε for any constant ε > 0.     

Critical Configurations for 1-View in Projections from ℙ<Superscript>k</Superscript> → ℙ<Superscript>2</Superscript>

In this paper we describe, from a theoretical point of view, critical configurations for the projective reconstruction of a set of points, for a single view, i.e. for calibration of a camera, in the case of projections from ℙ^k to ℙ² for k ≥ 4. We give first a general result describing these critical loci in ℙ^k, which, if irreducible, are algebraic varieties of dimension k−2 and degree 3. If k=4 they can be either a smooth ruled surface or a cone and if k = 5 they can be a smooth three dimensional variety, ruled in planes, or a cone. If k≥ 6, the variety is always a cone, the vertex of which has dimension at least k − 6. The reducible cases are studied in Appendix A. These results are then applied to determine explicitly the critical loci for the projections from ℙ^k which arise from the dynamic scenes in ℙ³ considered in [13]. Marina Bertolini is currently Associate Professor of Geometry at the Department of Mathematics at the Università degli Studi di Milano, Italy. Her main field of research is Complex Projective Algebraic Geometry, with particular interest for the classification of projective varieties and for the geometry of Grassmann varieties. On these topics M. Bertolini has published more than twenty reviewed papers on national and international journals. She has been for some years now interested also in applications of Algebraic Geometry to Computer Vision problems. Cristina Turrini is Associate Professor of Geometry at the Department of Mathematics of Università degli Studi di Milano, Italy. Her main research interest is Complex Projective Algebraic Geometry: subvarieties of Grassmannians, special varieties, automorphisms, classification. In the last two years she has started to work on applications of Algebraic Geometry to problems of Computer Vision. She is author or co-author of about thirty reviewed papers. She is also involved in popularization of Mathematics, and on this subject she is co-editor of some books.     

Equivalence of <Emphasis Type="Italic">ε</Emphasis> -Approximate Separation and Optimization in Fixed Dimensions<Superscript><Emphasis Type="Italic">1</Emphasis></Superscript>

Given a closed, convex set X\subseteq \bbR ⁿ , containing the origin, we consider the problem (P) : max {c^\T x\colon x ∈ X} . We show that, for a fixed dimension, n , and fixed \eps , 0 <\eps<1 , the existence of a combinatorial, strongly polynomial \eps -approximation separation algorithm for the set X is equivalent to the existence of a combinatorial, strongly polynomial \eps -approximation optimization algorithm for the problem (P) . Received June 5, 1996; revised September 25, 1997.     

De Bruijn''s syntax and reductional behaviour of λ-terms: the typed case

In this paper, we consider the typed versions of the λ-calculus written in a notation which helps describe canonical forms more elegantly than the classical notation, and enables to divide terms into classes according to their reductional behaviour. In this notation, β-reduction can be generalised from a relation on terms to one on equivalence classes. This class reduction covers many known notions of generalised reduction. We extend the Barendregt cube with our class reduction and show that the subject reduction property fails but that this is not unique to our class reduction. We show that other generalisations of reduction (such as the σ-reduction of Regnier) also behave badly in typed versions of the λ-calculus. Nevertheless, solution is at hand for these generalised reductions by adopting the useful addition of definitions in the contexts of type derivations. We show that adding such definitions enables the extensions of type systems with class reduction and σ-reduction to satisfy all the desirable properties of type systems, including subject reduction and strong normalisation. Our proposed typing relation ^c is the most general relation in the literature that satisfies all the desirable properties of type systems. We show that classes contain all the desirable information related to a term with respect to typing, strong normalisation, subject reduction, etc.     

Distance automata having large finite distance or finite ambiguity

A distance automaton is a (nondeterministic finite) automaton which is equipped with a nonnegative cost function on its transitions. The distance of a word recognized by such a machine quantifies the expenses associated with the recognition of this word. The distance of a distance automaton is the maximal distance of a word recognized by this machine or is infinite, depending on whether or not a maximum exists. We present distance automata havingn states and distance 2 ⁿ – 2. As a by-product we obtain regular languages having exponential finite order. Given a finitely ambiguous distance automaton withn states, we show that either its distance is at most 3 ⁿ – 1, or the growth of the distance in this machine is linear in the input length. The infinite distance problem for these distance automata is NP-hard and solvable in polynomial space. The infinite-order problem for regular languages is PSPACE-complete.A preliminary version of this article appeared in theProceedings of the 15th Symposium on Mathematical Foundations of Computer Science, 1990.     

<Emphasis Type="Italic">k</Emphasis>-Nearest-Neighbor Clustering and Percolation Theory

Let P be a realization of a homogeneous Poisson point process in ℝ ^d with density 1. We prove that there exists a constant k _d , 1<k _d <∞, such that the k-nearest neighborhood graph of P has an infinite connected component with probability 1 when k≥k _d . In particular, we prove that k ₂≤213. Our analysis establishes and exploits a close connection between the k-nearest neighborhood graphs of a Poisson point set and classical percolation theory. We give simulation results which suggest k ₂=3. We also obtain similar results for finite random point sets. Part of the work was done while S.-H. Teng was at Xerox Palo Alto Research Center and MIT. The work of F.F. Yao was supported in part by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China [Project No. CityU 1165/04E].     

Probability Logic of Finitely Additive Beliefs

Probability logics have been an active topic of investigation of beliefs in type spaces in game theoretical economics. Beliefs are expressed as subjective probability measures. Savage’s postulates in decision theory imply that subjective probability measures are not necessarily countably additive but finitely additive. In this paper, we formulate a probability logic Σ₊ that is strongly complete with respect to this class of type spaces with finitely additive probability measures, i.e. a set of formulas is consistent in Σ₊ iff it is satisfied in a finitely additive type space. Although we can characterize Σ₊-theories satisfiable in the class as maximally consistent sets of formulas, we prove that any canonical model of maximally consistent sets is not universal in the class of type spaces with finitely additive measures, and, moreover, it is not a type space. At the end of this paper, we show that even a minimal use of probability indices causes the failure of compactness in probability logics.     

Postures,typing strategies,and gender differences in mobile device usage: An observational study

Mobile device text messaging and other typing is rapidly increasing worldwide. A checklist was utilized to characterize joint postures and typing styles in individuals appearing to be of college age (n = 859) while typing on their mobile devices in public. Gender differences were also ascertained. Almost universally, observed subjects had a flexed neck (91.0%, n = 782), and a non-neutral typing-side wrist (90.3%, n = 776). A greater proportion of males had protracted shoulders (p < 0.01, χ² test), while a greater proportion of females had a typing-side inner elbow angle of <90°, particularly while standing (p = 0.03, χ² test). 46.1% of subjects typed with both thumbs (two hands holding the mobile device). Just over one-third typed with their right thumb (right hand holding the mobile device). No difference in typing styles between genders was found. Future research should determine whether the non-neutral postures identified may be associated with musculoskeletal disorders.     

On properties not inherited by monoids from their Schützenberger groups

We give an example of a monoid with finitely many left and right ideals, all of whose Schützenberger groups are presentable by finite complete rewriting systems, and so each have finite derivation type, but such that the monoid itself does not have finite derivation type, and therefore does not admit a presentation by a finite complete rewriting system. The example also serves as a counterexample to several other natural questions regarding complete rewriting systems and finite derivation type. Specifically it allows us to construct two finitely generated monoids M and N with isometric Cayley graphs, where N has finite derivation type (respectively, admits a presentation by a finite complete rewriting system) but M does not. This contrasts with the case of finitely generated groups for which finite derivation type is known to be a quasi-isometry invariant. The same example is also used to show that neither of these two properties is preserved under finite Green index extensions.     

Approximation by Bézier type of Meyer–König and Zeller operators

In this paper, we give direct, inverse and equivalence approximation theorems for the Bézier type of Meyer–König and Zeller operator with unified Ditzian–Totik modulus ω_φ^λ(f,t) (0≤λ≤1).     

Meta-modelling and graph grammars for multi-paradigm modelling in AToM<Superscript>3</Superscript>

This paper presents the combined use of meta-modelling and graph grammars for the generation of visual modelling tools for simulation formalisms. In meta-modelling, formalisms are described at a meta-level. This information is used by a meta-model processor to generate modelling tools for the described formalisms. We combine meta-modelling with graph grammars to extend the model manipulation capabilities of the generated modelling tools: edit, simulate, transform into another formalism, optimize and generate code. We store all (meta-)models as graphs, and thus, express model manipulations as graph grammars.We present the design and implementation of these concepts in AToM³ (A_To_ol for M_ulti-formalism, M_eta-M_odelling). AToM³ supports modelling of complex systems using different formalisms, all meta-modelled in their own right. Models in different formalisms may be transformed into a single common formalism for further processing. These transformations are specified by graph grammars. Mosterman and Vangheluwe [18] introduced the term multi-paradigm modelling to denote the combination of multiple formalisms, multiple abstraction levels, and meta-modelling. As an example of multi-paradigm modelling we present a meta-model for the Object-Oriented Continuous Simulation Language OOCSMP, in which we combine ideas from UML class diagrams (to express the OOCSMP model structure), Causal Block Diagrams (CBDs), and Statecharts (to specify the methods of the OOCSMP classes). A graph grammar is able to generate OOCSMP code, and then a compiler for this language (C-OOL) generates Java applets for the simulation execution.     

Approximation of functions by perceptrons: a new approach

We provide a constructive proof of the theorem of function approximation by perceptrons (cf Leshno et al. [1], Hornik [2]) when the activation function ψ isC∞ with all its derivatives non 0 at 0. We deal with uniform approximation on compact sets of continuous functions on ℜ ^d ,d≥1. This approach is elementary and provides some approximation results for the derivatives along with some bounds for the hidden layer.     

Corrigendum to “Uniform constant-depth threshold circuits for division and iterated multiplication” [J. Comput. System Sci. 65 (4) (2002) 695–716]

In this corrigendum, we retract part of our Corollary 6.6, which was presented as an immediate and obvious consequence of our main theorem, which showed that division lies in Dlogtime-uniform TC⁰${\mathrm{TC}}^0$.     

Tree Structure for Contractible Regions in ℝ<Superscript>3</Superscript>

For contractible regions ωin ℝ³ with generic smooth boundary, we determine the global structure of the Blum medial axis M. We give an algorithm for decomposing M into “irreducible components” which are attached to each other along “fin curves”. The attaching cannot be described by a tree structure as in the 2D case. However, a simplified but topologically equivalent medial structure ̂ M with the same irreducible components can be described by a two level tree structure. The top level describes the simplified form of the attaching, and the second level tree structure for each irreducible component specifies how to construct the component by attaching smooth medial sheets to the network of Y-branch curves. The conditions for these structures are complete in the sense that any region whose Blum medial axis satisfies the conditions is contractible.     

On-Line Construction of Two-Dimensional Suffix Trees in O(n<Superscript>2</Superscript> log n) Time

The two-dimensional suffix tree of an n × n square matrix A is a compacted trie that represents all square submatrices of A[11]. For the off-line case, i.e., A is given in advance to the algorithm, it is known how to build it in optimal time, for any type of alphabet size [11],[18]. Motivated by applications in Image Compression[22[, Giancarlo and Guaiana [14] considered the on-line version of the two-dimensional suffix tree and presented an O(n² log² n)-time algorithm, which we refer to as GG. That algorithm is a nontrivial generalization of Ukkonen's on-line algorithm for standard suffix trees [23]. The main contribution in this paper is an O(log n) factor improvement in the time complexity of the GG algorithm, making it optimal for unbounded alphabets [9]. Moreover, the ideas presented here also lead to a major simplification of the GG algorithm. Technically, we are able to preserve most of the structure of the original GG algorithm, by reducing a computational bottleneck to a primitive operation, i.e., comparison of Lcharacters, which is here implemented in constant time rather than O(log n) time as in GG. However, preserving that structure comes at a price. Indeed, in order to make everything work, we need a careful reorganization of another fundamental algorithm: Weiner's algorithm for the construction of standard suffix trees [24]. Specifically, here we provide a version of that algorithm which takes linear time and works on-line and concurrently over a set of strings.