Search

Background: Ad hoc parsers are pieces of code that use common string functions like split, trim, or slice to effectively perform parsing. Whether it is handling command-line arguments, reading configuration files, parsing custom file formats, or any number of other minor string processing tasks, ad hoc parsing is ubiquitous -- yet poorly understood. Objective: This study aims to reveal the common syntactic and semantic characteristics of ad hoc parsing code in real world Python projects. Our goal is to understand the nature of ad hoc parsers in order to inform future program analysis efforts in this area. Method: We plan to conduct an exploratory study based on large-scale mining of open-source Python repositories from GitHub. We will use program slicing to identify program fragments related to ad hoc parsing and analyze these parsers and their surrounding contexts across 9 research questions using 25 initial syntactic and semantic metrics. Beyond descriptive statistics, we will attempt to identify common parsing patterns by cluster analysis., Comment: 5 pages, accepted as a registered report for MSR 2023 with Continuity Acceptance (CA)

Ad hoc parsers are everywhere: they appear any time a string is split, looped over, interpreted, transformed, or otherwise processed. Every ad hoc parser gives rise to a language: the possibly infinite set of input strings that the program accepts without going wrong. Any language can be described by a formal grammar: a finite set of rules that can generate all strings of that language. But programmers do not write grammars for ad hoc parsers -- even though they would be eminently useful. Grammars can serve as documentation, aid program comprehension, generate test inputs, and allow reasoning about language-theoretic security. We propose an automatic grammar inference system for ad hoc parsers that would enable all of these use cases, in addition to opening up new possibilities in mining software repositories and bi-directional parser synthesis.

The interactive command line, also known as the shell, is a prominent mechanism used extensively by a wide range of software professionals (engineers, system administrators, data scientists, etc.). Shell customizations can therefore provide insight into the tasks they repeatedly perform, how well the standard environment supports those tasks, and ways in which the environment could be productively extended or modified. To characterize the patterns and complexities of command-line customization, we mined the collective knowledge of command-line users by analyzing more than 2.2 million shell alias definitions found on GitHub. Shell aliases allow command-line users to customize their environment by defining arbitrarily complex command substitutions. Using inductive coding methods, we found three types of aliases that each enable a number of customization practices: Shortcuts (for nicknaming commands, abbreviating subcommands, and bookmarking locations), Modifications (for substituting commands, overriding defaults, colorizing output, and elevating privilege), and Scripts (for transforming data and chaining subcommands). We conjecture that identifying common customization practices can point to particular usability issues within command-line programs, and that a deeper understanding of these practices can support researchers and tool developers in designing better user experiences. In addition to our analysis, we provide an extensive reproducibility package in the form of a curated dataset together with well-documented computational notebooks enabling further knowledge discovery and a basis for learning approaches to improve command-line workflows.

Retrieval and ranking models are the backbone of many applications such as web search, open domain QA, or text-based recommender systems. The latency of neural ranking models at query time is largely dependent on the architecture and deliberate choices by their designers to trade-off effectiveness for higher efficiency. This focus on low query latency of a rising number of efficient ranking architectures make them feasible for production deployment. In machine learning an increasingly common approach to close the effectiveness gap of more efficient models is to apply knowledge distillation from a large teacher model to a smaller student model. We find that different ranking architectures tend to produce output scores in different magnitudes. Based on this finding, we propose a cross-architecture training procedure with a margin focused loss (Margin-MSE), that adapts knowledge distillation to the varying score output distributions of different BERT and non-BERT passage ranking architectures. We apply the teachable information as additional fine-grained labels to existing training triples of the MSMARCO-Passage collection. We evaluate our procedure of distilling knowledge from state-of-the-art concatenated BERT models to four different efficient architectures (TK, ColBERT, PreTT, and a BERT CLS dot product model). We show that across our evaluated architectures our Margin-MSE knowledge distillation significantly improves re-ranking effectiveness without compromising their efficiency. Additionally, we show our general distillation method to improve nearest neighbor based index retrieval with the BERT dot product model, offering competitive results with specialized and much more costly training methods. To benefit the community, we publish the teacher-score training files in a ready-to-use package., Comment: Updated paper with dense retrieval results and query-level analysis

There are many existing retrieval and question answering datasets. However, most of them either focus on ranked list evaluation or single-candidate question answering. This divide makes it challenging to properly evaluate approaches concerned with ranking documents and providing snippets or answers for a given query. In this work, we present FiRA: a novel dataset of Fine-Grained Relevance Annotations. We extend the ranked retrieval annotations of the Deep Learning track of TREC 2019 with passage and word level graded relevance annotations for all relevant documents. We use our newly created data to study the distribution of relevance in long documents, as well as the attention of annotators to specific positions of the text. As an example, we evaluate the recently introduced TKL document ranking model. We find that although TKL exhibits state-of-the-art retrieval results for long documents, it misses many relevant passages., Comment: Accepted at CIKM 2020 (Resource Track)

Combinatorial batch codes were defined by Paterson, Stinson, and Wei as purely combinatorial versions of the batch codes introduced by Ishai, Kushilevitz, Ostrovsky, and Sahai. There are $n$ items and $m$ servers, each of which stores a subset of the items. A batch code is an arrangement for storing items on servers so that, for prescribed integers $k$ and $t$, any $k$ items can be retrieved by reading at most $t$ items from each server. Silberstein defined an erasure batch code (with redundancy $r$) as a batch code in which any $k$ items can be retrieved by reading at most $t$ items from each server, while any $r$ servers are unavailable (failed). In this paper, we investigate erasure batch codes with $t=1$ (each server can read at most one item) in a combinatorial manner. We determine the optimal (minimum) total storage of an erasure batch code for several ranges of parameters. Additionally, we relate optimal erasure batch codes to maximum packings. We also identify a necessary lower bound for the total storage of an erasure batch code, and we relate parameters for which this trivial lower bound is achieved to the existence of graphs with appropriate girth.

We consider a sorting machine consisting of two stacks in series where the first stack has the added restriction that entries in the stack must be in decreasing order from top to bottom. The class of permutations sortable by this machine are known to be enumerated by the Schr\"oder numbers. In this paper, we give a bijection between these sortable permutations of length $n$ and Schr\"oder paths -- the lattice paths from $(0,0)$ to $(n-1,n-1)$ composed of East steps $(1,0)$, North steps $(0,1)$, and Diagonal steps $(1,1)$ that travel weakly below the line $y=x$.

This paper studies Brownian motion subject to the occurrence of a minimal length excursion below a given excursion level. The law of this process is determined. The characterization is explicit and shows by a layer construction how the law is built up over time in terms of the laws of sums of a given set of independent random variables., Comment: 17 pages

We define the cyclic matching sequencibility of a graph to be the largest integer $d$ such that there exists a cyclic ordering of its edges so that every $d$ consecutive edges in the cyclic ordering form a matching. We show that the cyclic matching sequencibility of $K_{2m}$ and $K_{2m+1}$ equal $m-1$.

For a compact locally symmetric space $\XG$ of non-positive curvature, we consider sequences of normalized joint eigenfunctions which belong to the principal spectrum of the algebra of invariant differential operators. Using an $h$-\psdiff\ calculus on $\XG$, we define and study lifted quantum limits as weak$^*$-limit points of Wigner distributions. The Helgason boundary values of the eigenfunctions allow us to construct Patterson--Sullivan distributions on the space of Weyl chambers. These distributions are asymptotic to lifted quantum limits and satisfy additional invariance properties, which makes them useful in the context of quantum ergodicity. Our results generalize results for compact hyperbolic surfaces obtained by Anantharaman and Zelditch.

We initiate a study of the zero-nonzero patterns of n by n alternating sign matrices. We characterize the row (column) sum vectors of these patterns and determine their minimum term rank. In the case of connected alternating sign matrices, we find the minimum number of nonzero entries and characterize the case of equality. We also study symmetric alternating sign matrices, in particular, those with only zeros on the main diagonal. These give rise to alternating signed graphs without loops, and we determine the maximum number of edges in such graphs. We also consider n by n alternating sign matrices whose patterns are maximal within the class of all n by n alternating sign matrices., Comment: 35 pages, 2 figures

We generalize parts of a special non-Euclidean calculus of pseudodifferential operators, which was invented by S. Zelditch for hyperbolic surfaces, to symmetric spaces $X=G/K$ of the noncompact type and their compact quotients $Y=\Gamma\backslash G/K$. We sometimes restrict our results to the case of rank one symmetric spcaes. The non-Euclidean setting extends the defintion of so-called Patterson-Sullivan distributions, which were first defined by N. Anantharaman and S. Zelditch for hyperbolic systems, in a natural way to arbitrary symmetric spaces of the noncompact type. We find an explicit intertwining operator mapping Patterson-Sullivan distributions into Wigner distributions. We study the important invariance and equivariance properties of these distributions. Finally, we describe asymptotic properties of these distributions.

For t a positive integer, the t-term rank of a (0,1)-matrix A is defined to be the largest number of 1s in A with at most one 1 in each column and at most t 1s in each row. Thus the 1-term rank is the ordinary term rank. We generalize some basic results for the term rank to the t-term rank, including a formula for the maximum term rank over a nonempty class of (0,1)-matrices with the the same row sum and column sum vectors. We also show the surprising result that in such a class there exists a matrix which realizes all of the maximum terms ranks between 1 and t., Comment: 18 pages

There is a remarkable relation between two kinds of phase space distributions associated to eigenfunctions of the Laplacian of a compact hyperbolic manifold: It was observed in \cite{AZ} that for compact hyperbolic surfaces $X_{\Gamma}=\Gamma\backslash\mathbb{H}$ Wigner distributions $\int_{S^* X_{\Gamma}} a dW_{ir_j} = < \mathrm{Op}(a)\phi_{ir_j},\phi_{ir_j} >_{L^2(X_{\Gamma})}$ and Patterson--Sullivan distributions $PS_{ir_j}$ are asymptotically equivalent as $r_j\to\infty$. We generalize the definitions of these distributions to all rank one symmetric spaces of noncompact type and introduce off-diagonal elements $PS_{\lambda_j,\lambda_k}$. Further, we give explicit relations between off-diagonal Patterson--Sullivan distributions and off-diagonal Wigner distributions and describe the asymptotic relation between these distributions., Comment: 25 pages

Argumentation has proved a useful tool in defining formal semantics for assumption-based reasoning by viewing a proof as a process in which proponents and opponents attack each others arguments by undercuts (attack to an argument's premise) and rebuts (attack to an argument's conclusion). In this paper, we formulate a variety of notions of attack for extended logic programs from combinations of undercuts and rebuts and define a general hierarchy of argumentation semantics parameterised by the notions of attack chosen by proponent and opponent. We prove the equivalence and subset relationships between the semantics and examine some essential properties concerning consistency and the coherence principle, which relates default negation and explicit negation. Most significantly, we place existing semantics put forward in the literature in our hierarchy and identify a particular argumentation semantics for which we prove equivalence to the paraconsistent well-founded semantics with explicit negation, WFSX$_p$. Finally, we present a general proof theory, based on dialogue trees, and show that it is sound and complete with respect to the argumentation semantics., Comment: To appear in Theory and Practice of Logic Programming

This paper defines an argumentation semantics for extended logic programming and shows its equivalence to the well-founded semantics with explicit negation. We set up a general framework in which we extensively compare this semantics to other argumentation semantics, including those of Dung, and Prakken and Sartor. We present a general dialectical proof theory for these argumentation semantics., Comment: Workshop on Non-Monotonic Reasoning NMR'02, Special Session on Argument, Dialogue, and Decision

This paper studies the law of any power of the integral of geometric Brownian motion over any finite time interval. As its main results, two integral representations for this law are derived. This is by enhancing the Laplace transform ansatz of Yor (1992) with complex analytic methods, which is the main methodological contribution of the paper. The one of our integrals has a similar structure to that obtained by Yor, while the other is in terms of Hermite functions as those of Dufresne (2001). Performing or not performing a certain Girsanov transformation is identified as the source of these two forms of the laws. While our results specialize for exponents equal to 1 to those obtained by Yor, they yield on specialization representations for the exponent equal to minus 1 laws which are markedly different from those obtained by Dufresne., Comment: 18 pages, 2 figures

This note re-addresses the Paris barrier options proposed by Yor and collaborators and their valuation using the Laplace transform approach. The notion of Paris barrier options, based on excursion theory and using the Brownian meander, is extended such that their valuation is now possible at any point during their lifespan. The pertinent Laplace transforms are modified when necessary., Comment: 10 pages

Averaging problems are ubiquitous in Finance with the valuation of the so-called Asian options on arithmetic averages as their most conspicuous form. There is an abundance of numerical work on them, and their stochastic structure has been extensively studied by Yor and his school. However, the analytical structure of these problems is largely unstudied. Our philosophy now is that such valuation problems should be considered as an extension of the theory of special functions: they lead to new problems about new classes of special functions which should be studied in terms of and using of the methods of special functions and their theory. This is exemplified by deriving integral representations for the Black-Scholes prices based on Yor's Laplace transform ansatz to their valuation. They are obtained by analytic Laplace inversion using complex analytic methods. The analysis ultimately rests on the gamma function which in this sense is found to be at the base of Asian options. The results improve on those of Yor and have served us a as starting point for deriving first time benchmark prices for these options., Comment: 23 pages, 2 figures