Search

Your search keyword '"Archibald, Margaret"' showing total 96 results
Start Over Author "Archibald, Margaret"
96 results on '"Archibald, Margaret"'

3. The number of distinct adjacent pairs in geometrically distributed words

Author

Archibald, Margaret, Blecher, Aubrey, Brennan, Charlotte, Knopfmacher, Arnold, Wagner, Stephan, and Ward, Mark

Subjects
Mathematics - Combinatorics, 05A15, 05A05
Abstract

A sequence of geometric random variables of length $n$ is a sequence of $n$ independent and identically distributed geometric random variables ($\Gamma_1, \Gamma_2, \dots, \Gamma_n$) where $\mathbb{P}(\Gamma_j=i)=pq^{i-1}$ for $1~\leq~j~\leq~n$ with $p+q=1.$ We study the number of distinct adjacent two letter patterns in such sequences. Initially we directly count the number of distinct pairs in words of short length. Because of the rapid growth of the number of word patterns we change our approach to this problem by obtaining an expression for the expected number of distinct pairs in words of length $n$. We also obtain the asymptotics for the expected number as $n \to \infty$., Comment: 18 pages, 1 table, 1 figure. This is the final version for publication

Published
2018
Full Text
View/download PDF

4. Determining the defect type in a graphene lattice

Author

Archibald, Margaret, Currie, Sonja, Nowaczyk, Marlena, Archibald, Margaret, Currie, Sonja, and Nowaczyk, Marlena

Abstract

We consider four common defects that appear in an infinite single-layer graphene lattice, i.e. single vacancy V1(5-9), Stone-Wales SW (55-77), and double vacancies V2(5-8-5) and V2(555-777). Investigating the honeycomb pattern of the graphene, we make use of the concept of shortest closed paths (periodic orbits) in the underlying topological structure. Using properties of the shortest closed paths of odd length we present and prove mathematically an algorithm that classifies which one of these defects occurs. © 2023 Taylor & Francis Group, LLC., Funding: The National Research Foundation of South Africa under grant no.s 89147 and 103530.

Published
2024
Full Text
View/download PDF

7. COLUMNS OF FIXED HEIGHT IN BARGRAPHS.

Author

ARCHIBALD, MARGARET, BLECHER, AUBREY, and KNOPFMACHER, ARNOLD

Subjects
*GENERATING functions, *CONTINUED fractions
Abstract

We obtain the generating function for the number of columns of fixed height r in a bargraph (classified according to semi-perimeter). As initial case for two distinct methods we first find the generating function for columns of height 1. Then using a first-return-to-level-1 decomposition, we obtain the rational function version of the continued fraction generating function which allows us to derive separate recursions for its numerator and denominator. This then allows us to get the asymptotic average number of columns for each r. We also obtain an equivalent generating function by exploiting a sequential decomposition for bargraphs in terms of columns of height r. [ABSTRACT FROM AUTHOR]

Published
2024
Full Text
View/download PDF

10. SHEDDING LIGHT ON WORDS

Author

Archibald, Margaret, Blecher, Aubrey, Brennan, Charlotte, Knopfmacher, Arnold, and Mansour, Toufik

Published
2017

11. Finding the V2(555 − 777) Double Vacancy Defect in Graphene Using Rotational Symmetry

Author

Archibald, Margaret Lyn, Currie, Sonja, Nowaczyk, Marlena, Archibald, Margaret Lyn, Currie, Sonja, and Nowaczyk, Marlena

Abstract

We use the underlying hexagonal structure of graphene to identify uniquely the position pertaining to a divacancy defect of type V2(555 - 777). This is achieved by considering at most three closed path readings and the symmetry of the defective structure. We work in the corresponding rectangular model but still rely on the rotational symmetry of the original hexagonal grid. Our approach is purely mathematical and therefore there is no need for imaging technologies © 2023 University of Kashan Press. All rights reserved

Published
2023
Full Text
View/download PDF

12. Parameters in Inversion Sequences.

Author

Archibald, Margaret, Blecher, Aubrey, and Knopfmacher, Arnold

Subjects
*GENERATING functions, *CATALAN numbers
Abstract

We study various combinatorial parameters in the set of inversion sequences of length n. First, we provide generating functions for 1-successions and then generalise this to p-successions. Thereafter we find the formulae for the total number of successions by extracting coefficients. We then do the same for runs of length r and the length of the ith run. Next, we derive a generating function for the number of inversions in inversion sequences themselves and show that inversion sequences with no inversions are counted by the Catalan numbers. Finally, viewing inversion sequences as bargraphs, we develop a generating function for their area. [ABSTRACT FROM AUTHOR]

Published
2023
Full Text
View/download PDF

20. The number of distinct adjacent pairs in geometrically distributed words

Author

Archibald, Margaret, Blecher, Aubrey, Brennan, Charlotte, Knopfmacher, Arnold, Wagner, Stephan, and Ward, Mark

Subjects
generating function, asymptotics, 05A05, geometric random variables, Combinatorics, 05A15, 05A05, pairs, FOS: Mathematics, Mathematics - Combinatorics, Sannolikhetsteori och statistik, Combinatorics (math.CO), 05A15, Probability Theory and Statistics
Abstract

Discrete Mathematics & Theoretical Computer Science ; vol. 22 no. 4 ; Analysis of Algorithms ; 1365-8050, A sequence of geometric random variables of length $n$ is a sequence of $n$ independent and identically distributed geometric random variables ($\Gamma_1, \Gamma_2, \dots, \Gamma_n$) where $\P(\Gamma_j=i)=pq^{i-1}$ for $1~\leq~j~\leq~n$ with $p+q=1.$ We study the number of distinct adjacent two letter patterns in such sequences. Initially we directly count the number of distinct pairs in words of short length. Because of the rapid growth of the number of word patterns we change our approach to this problem by obtaining an expression for the expected number of distinct pairs in words of length $n$. We also obtain the asymptotics for the expected number as $n \to \infty$., Comment: 18 pages, 1 table, 1 figure. This is the final version for publication

Published
2021
Full Text
View/download PDF

25. Durfee squares in compositions

Author

Archibald, Margaret, primary, Blecher, Aubrey, additional, Brennan, Charlotte, additional, Knopfmacher, Arnold, additional, and Mansour, Toufik, additional

Published
2018
Full Text
View/download PDF

30. The Hiring Problem and Permutations

Author

Archibald, Margaret, Martínez, Conrado, Department of Mathematics and Applied Mathematics [Cape Town], University of Cape Town, Departament Llenguatges i Sistemes Informatics, Universitat Politècnica de Catalunya [Barcelona] (UPC), Krattenthaler, Christian and Strehl, Volker and Kauers, and Manuel

Subjects
Current (mathematics), ComputingMilieux_THECOMPUTINGPROFESSION, General Computer Science, hiring problem, permutations, Rank (computer programming), Sigma, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Theoretical Computer Science, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], Combinatorics, secretary problem, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Permutation, Simple (abstract algebra), On-line decision making, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], generating functions, 8. Economic growth, Quality Score, analytic combinatorics, Discrete Mathematics and Combinatorics, Analytic combinatorics, Secretary problem, Mathematics
Abstract

The $\textit{hiring problem}$ has been recently introduced by Broder et al. in last year's ACM-SIAM Symp. on Discrete Algorithms (SODA 2008), as a simple model for decision making under uncertainty. Candidates are interviewed in a sequential fashion, each one endowed with a quality score, and decisions to hire or discard them must be taken on the fly. The goal is to maintain a good rate of hiring while improving the "average'' quality of the hired staff. We provide here an alternative formulation of the hiring problem in combinatorial terms. This combinatorial model allows us the systematic use of techniques from combinatorial analysis, e. g., generating functions, to study the problem. Consider a permutation $\sigma :[1,\ldots, n] \to [1,\ldots, n]$. We process this permutation in a sequential fashion, so that at step $i$, we see the score or quality of candidate $i$, which is actually her face value $\sigma (i)$. Thus $\sigma (i)$ is the rank of candidate $i$; the best candidate among the $n$ gets rank $n$, while the worst one gets rank $1$. We define $\textit{rank-based}$ strategies, those that take their decisions using only the relative rank of the current candidate compared to the score of the previous candidates. For these strategies we can prove general theorems about the number of hired candidates in a permutation of length $n$, the time of the last hiring, and the average quality of the last hired candidate, using techniques from the area of analytic combinatorics. We apply these general results to specific strategies like hiring above the best, hiring above the median or hiring above the $m$th best; some of our results provide a complementary view to those of Broder et al., but on the other hand, our general results apply to a large family of hiring strategies, not just to specific cases.

Published
2009

40. Randomness with Respect to the Signed-Digit Representation.

Author

Archibald, Margaret, Brattka, Vasco, and Heuberger, Clemens

Subjects
*REAL numbers, *LEBESGUE integral, *MEASURE theory, *KOLMOGOROV complexity, *FAREY sequences
Abstract

The ordinary notion of algorithmic randomness of reals can be characterised as Martin-Löf randomness with respect to the Lebesgue measure or as Kolmogorov randomness with respect to the binary representation. In this paper we study the question of how the notion of algorithmic randomness induced by the signed-digit representation of the real numbers is related to the ordinary notion of algorithmic randomness. We first consider the image measure on real numbers induced by the signed-digit representation. We call this measure the signed-digit measure and using the Fourier transform of this measure and the Riemann-Lebesgue Lemma we prove that this measure is not absolutely continuous with respect to the Lebesgue measure. We also show that the signed-digit measure can be obtained as a weakly convergent convolution of discrete measures and therefore, by the classical Theorem of Jessen and Wintner the Lebesgue measure is not absolutely continuous with respect to the signed-digitmeasure. Finally, we provide an invariance theoremwhich shows that if a computable map preserves Martin-Löf randomness, then its induced image measure has to be absolutely continuous with respect to the target space measure. This theorem can be considered as a loose analog for randomness of the Banach-Mazur theorem for computability. Using this Invariance Theorem we conclude that the notion of randomness induced by the signed-digit representation is incomparable with the ordinary notion of randomness. [ABSTRACT FROM AUTHOR]

Published
2008

42. YOUR SAY….

Author

ARCHIBALD, MARGARET, SARGEANT, KIM, and SOUL, PETER

Abstract

Several letters to the editor are presented in response to articles in previous issues including one about streaming live concerts in the July 16, 2011 issue, one about the European Community Youth Orchestra and another about relays of live opera, theatre and concerts in the July 16, 2011 issue.

Published
2011

43. Representations of Numbers as :A Saddle Point Approach

Author

Louchard, Guy, Prodinger, Helmut, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Goebel, Randy, editor, Siekmann, Jörg, editor, Wahlster, Wolfgang, editor, Archibald, Margaret, editor, Brattka, Vasco, editor, Goranko, Valentin, editor, and Löwe, Benedikt, editor

Published
2009
Full Text
View/download PDF

44. Fine-Continuous Functions and Fractals Defined by Infinite Systems of Contractions

Author

Tsujii, Yoshiki, Mori, Takakazu, Yasugi, Mariko, Tsuiki, Hideki, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Goebel, Randy, editor, Siekmann, Jörg, editor, Wahlster, Wolfgang, editor, Archibald, Margaret, editor, Brattka, Vasco, editor, Goranko, Valentin, editor, and Löwe, Benedikt, editor

Published
2009
Full Text
View/download PDF

45. Is P = PSPACE for Infinite Time Turing Machines?

Author

Winter, Joost, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Goebel, Randy, editor, Siekmann, Jörg, editor, Wahlster, Wolfgang, editor, Archibald, Margaret, editor, Brattka, Vasco, editor, Goranko, Valentin, editor, and Löwe, Benedikt, editor

Published
2009
Full Text
View/download PDF

46. Sets of Infinite Words Recognized by Deterministic One-Turn Pushdown Automata

Author

Mihoubi, Douadi, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Goebel, Randy, editor, Siekmann, Jörg, editor, Wahlster, Wolfgang, editor, Archibald, Margaret, editor, Brattka, Vasco, editor, Goranko, Valentin, editor, and Löwe, Benedikt, editor

Published
2009
Full Text
View/download PDF

47. A Playful Glance at Hierarchical Questions for Two-Way Alternating Automata

Author

Duparc, Jacques, Facchini, Alessandro, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Goebel, Randy, editor, Siekmann, Jörg, editor, Wahlster, Wolfgang, editor, Archibald, Margaret, editor, Brattka, Vasco, editor, Goranko, Valentin, editor, and Löwe, Benedikt, editor

Published
2009
Full Text
View/download PDF

48. Probabilistic Systems with LimSup and LimInf Objectives

Author

Chatterjee, Krishnendu, Henzinger, Thomas A., Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Goebel, Randy, editor, Siekmann, Jörg, editor, Wahlster, Wolfgang, editor, Archibald, Margaret, editor, Brattka, Vasco, editor, Goranko, Valentin, editor, and Löwe, Benedikt, editor

Published
2009
Full Text
View/download PDF

49. Towards Model-Checking Programs with Lists

Author

Finkel, Alain, Lozes, Étienne, Sangnier, Arnaud, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Goebel, Randy, editor, Siekmann, Jörg, editor, Wahlster, Wolfgang, editor, Archibald, Margaret, editor, Brattka, Vasco, editor, Goranko, Valentin, editor, and Löwe, Benedikt, editor

Published
2009
Full Text
View/download PDF

50. Symbolic Model Checking of Tense Logics on Rational Kripke Models

Author

Bekker, Wilmari, Goranko, Valentin, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Goebel, Randy, editor, Siekmann, Jörg, editor, Wahlster, Wolfgang, editor, Archibald, Margaret, editor, Brattka, Vasco, editor, Goranko, Valentin, editor, and Löwe, Benedikt, editor

Published
2009
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results