4 results
Search Results
2. REDUCTION OF DISCRETE DYNAMICAL SYSTEMS OVER GRAPHS.
- Author
-
Mortveit, H. S. and Reidys, C. M.
- Subjects
- *
MORPHISMS (Mathematics) , *SET theory , *CATEGORIES (Mathematics) , *GRAPHIC methods , *MATHEMATICS - Abstract
In this paper we study phase space relations in a certain class of discrete dynamical systems over graphs. The systems we investigate are called Sequential Dynamical Systems (SDSs), which are a class of dynamical systems that provide a framework for analyzing computer simulations. Specifically, an SDS consists of (i) a finite undirected graph Y with vertex set {1,2,…,n} where each vertex has associated a binary state, (ii) a collection of Y-local functions (Fi,Y)i∈v[Y] with $F_{i,Y}: \mathbb{F}_2^n\to \mathbb{F}_2^n$ and (iii) a permutation π of the vertices of Y. The SDS induced by (i)–(iii) is the map \[ [F_Y,\pi] = F_{\pi(n),Y} \circ \cdots \circ F_{\pi(1),Y}\,. \] The paper is motivated by a general reduction theorem for SDSs which guarantees the existence of a phase space embedding induced by a covering map between the base graphs of two SDSs. We use this theorem to obtain information about phase spaces of certain SDSs over binary hypercubes from the dynamics of SDSs over complete graphs. We also investigate covering maps over binary hypercubes, $Q_2^n$, and circular graphs, Circn. In particular we show that there exists a covering map $\phi: Q_2^n\to K_{n+1}$ if and only if 2n≡0 mod n+1. Furthermore, we provide an interpretation of a class of invertible SDSs over circle graphs as right-shifts of length n-2 over {0,1}2n-2. The paper concludes with a brief discussion of how we can extend a given covering map to a covering map over certain extended graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2004
- Full Text
- View/download PDF
3. SOME WORD ORDER BIASES FROM LIMITED BRAIN RESOURCES:: A MATHEMATICAL APPROACH.
- Author
-
FERRER-I-CANCHO, RAMON
- Subjects
- *
WORD order (Grammar) , *SYNTAX (Grammar) , *MATHEMATICAL optimization , *MATHEMATICS , *LINGUISTICS - Abstract
In this paper, we propose a mathematical framework for studying word order optimization. The framework relies on the well-known positive correlation between cognitive cost and the Euclidean distance between the elements (e.g. words) involved in a syntactic link. We study the conditions under which a certain word order is more economical than an alternative word order by proposing a mathematical approach. We apply our methodology to two different cases: (a) the ordering of subject (S), verb (V) and object (O), and (b) the covering of a root word by a syntactic link. For the former, we find that SVO and its symmetric, OVS, are more economical than OVS, SOV, VOS and VSO at least 2/3 of the time. For the latter, we find that uncovering the root word is more economical than covering it at least 1/2 of the time. With the help of our framework, one can explain some Greenbergian universals. Our findings provide further theoretical support for the hypothesis that the limited resources of the brain introduce biases toward certain word orders. Our theoretical findings could inspire or illuminate future psycholinguistics or corpus linguistics studies. [ABSTRACT FROM AUTHOR]
- Published
- 2008
- Full Text
- View/download PDF
4. SCALE-FREE EVOLVING NETWORKS WITH ACCELERATED ATTACHMENT.
- Author
-
Sen Qin, Guanzhong Dai, Lin Wang, and Ming Fan
- Subjects
- *
NUMERICAL analysis , *MATHEMATICAL models , *DISTRIBUTION (Probability theory) , *MATHEMATICS , *MATHEMATICAL analysis - Abstract
A new evolving network based on the scale-free network of Barabási and Albert (BA) is studied, and the accelerated attachment of new edges is considered in its evolving process. The accelerated attachment is different from the previous accelerated growth of edges and has two particular meanings in this paper. One is that a new vertex with the edges is inserted into the network with acceleration at each time step; the other is that, with a given probability, some additional edges are linked with the vertices in proportion to the number of their obtained edges in the latest evolving periods. The new model describes the cases of those complex networks with a few exceptional vertices. The attachment mechanism of the new adding edges for these vertices does not follow the preferential attachment rule. Comparing with the linear edge growth model, the characteristics of the accelerated growth model are studied theoretically and numerically. We show that the degree distributions of these models have a power law decay and the exponents are larger than that of the BA model. We point out that the characteristics of the exceptional vertices and the aging vertices in an aging network are not identical. The reasons for neglecting this attachment in most of evolving networks are also summarized. [ABSTRACT FROM AUTHOR]
- Published
- 2007
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.