Search

Patients who do not show up for scheduled appointments are a considerable cost and concern in healthcare. In this study, we predict patient noshows for outpatient surgery at the endoscopy ward of a hospital in Denmark. The predictions are made by training machine leaning (ML) models on available data, which have been recorded for purposes other than ML, and by doing situated work in the hospital setting to understand local data practices and fine-tune the models. The best performing model (XGBoost with oversampling) predicts no-shows at sensitivity = 0.97, specificity = 0.66, and accuracy = 0.95. Importantly, the situated work engaged local hospital staff in the design process and led to substantial quantitative improvements in the performance of the models. We consider the results promising but acknowledge that they are from a single ward. To transfer the no-show models to other wards and hospitals, the situated work must be redone. [ABSTRACT FROM AUTHOR]

In the cons-free programming paradigm, we eschew constructors and program using only destructors. Cons-free programs in a simple first-order language with string data capture exactly P, the class of polynomial-time relations. By varying the underlying language and considering other data types, we can capture several other complexity classes. However, no cons-free programming language captures any functional complexity class for fundamental reasons. In this paper, we cleanly extend the cons-free paradigm to encompass functional complexity classes. Namely, we introduce programs with data that can either only be destructed or only be constructed, which we enforce by a type system on the program variables. We call the resulting programs read/write - (or RW -)factorizable, show that RW-factorizable string programs capture exactly the class FP of polynomial-time functions, and that tail-recursive RW-factorizable programs capture exactly the class FL of logarithmic-space functions. Finally, we state and solve the nontrivial problem of syntactic composition of two RW-factorizable programs. [ABSTRACT FROM AUTHOR]

The |${\lambda }$| -calculus enjoys the property that each |${\lambda }$| -term has at least one fixed point, which is due to the existence of a fixed point combinator. It is unknown whether it enjoys the 'fixed point property' stating that each |${\lambda }$| -term has either one or infinitely many pairwise distinct fixed points. We show that the fixed point property holds when considering possibly open fixed points. The problem of counting fixed points in the closed setting remains open, but we provide sufficient conditions for a |${\lambda }$| -term to have either one or infinitely many fixed points. In the main result of this paper we prove that in every sensible |${\lambda }$| -theory there exists a |${\lambda }$| -term that violates the fixed point property. We then study the open problem concerning the existence of a double fixed point combinator and propose a proof technique that could lead towards a negative solution. We consider interpretations of the |${\lambda } {\mathtt{Y}}$| -calculus into the |${\lambda }$| -calculus together with two reduction extension properties, whose validity would entail the non-existence of any double fixed point combinators. We conjecture that both properties hold when typed |${\lambda } {\mathtt{Y}}$| -terms are interpreted by arbitrary fixed point combinators. We prove reduction extension property I for a large class of fixed point combinators. Finally, we prove that the |${\lambda }{\mathtt{Y}}$| -theory generated by the equation characterizing double fixed point combinators is a conservative extension of the |${\lambda }$| -calculus. [ABSTRACT FROM AUTHOR]

We define computable infinitary rewriting by introducing computability to the study of strongly convergent infinite reductions over infinite first-order terms. Given computable infinitary reductions, we show that descendants and origins—essential to proving fundamental properties such as compression and confluence—are computable across such reductions. [ABSTRACT FROM AUTHOR]

Several properties of information retrieval (IR) data, such as query frequency or document length, are widely considered to be approximately distributed as a power law. This common assumption aims tofocus on specific characteristics of the empirical probability distribution of such data (e.g., its scale-free nature or its long/fat tail). This assumption, however, may not be always true. Motivated by recent work in the statistical treatment of power law claims, we investigate two research questions: (i) To what extent do power law approximations hold for term frequency, document length, query frequency, query length, citation frequency, and syntactic unigram frequency? And (ii) what is the computational cost of replacing ad hoc power law approximations with more accurate distribution fitting? We study 23 TREC and 5 non-TREC datasets and compare the fit of power laws to 15 other standard probability distributions. We find that query frequency and 5 out of 24 term frequency distributions are best approximated by a power law. All remaining properties are better approximated by the Inverse Gaussian, Generalized Extreme Value, Negative Binomial, or Yule distribution. We also find the overhead of replacing power law approximations by more informed distribution fitting to be negligible, with potential gains to IR tasks like index compression or test collection generation for IR evaluation. [ABSTRACT FROM AUTHOR]

Before using an interactive product, people form expectations about what the experience of use will be like. These expectations may affect both the use of the product and users’ attitudes toward it. This article briefly reviews existing theories of expectations to design and perform two crowdsourced experiments that investigate how expectations affect user experience measures. In the experiments, participants saw a primed or neutral review of a simple online game, played it, and rated it on various user experience measures. Results suggest that when expectations are confirmed, users tend to assimilate their ratings with their expectations; conversely, if the product quality is inconsistent with expectations, users tend to contrast their ratings with expectations and give ratings correlated with the level of disconfirmation. Results also suggest that expectation disconfirmation can be used more widely in analyses of user experience, even when the analyses are not specifically concerned with expectation disconfirmation. [ABSTRACT FROM AUTHOR]

We posit that progress in Optical Music Recognition (OMR) has been held up for years by the absence of anything resembling the standard testbeds in use in other fields that face difficult evaluation problems. One example of such a field is text information retrieval (IR), where the Text Retrieval Conference (TREC) has annually-renewed IR tasks with accompanying data sets. In music informatics, the Music Information Retrieval Exchange (MIREX), with its annual tests and meetings held during the ISMIR conference, is a close analog to TREC; but MIREX has never had an OMR track or a collection of music such a track could employ. We describe why the absence of an OMR testbed is a problem and how this problem may be mitigated. To aid in the establishment of a standard testbed, we provide (1) a set of definitions for the complexity of music notation; (2) a set of performance metrics for OMR tools that gauge score complexity and graphical quality; and (3) a small corpus of music for use as a baseline for a proper OMR testbed. [ABSTRACT FROM AUTHOR]

A full and finitely generated Church-Rosser term rewriting system is presented that has no computable onestep, normalizing strategy; the system is both left- and right-linear. The result provides a negative answer to a question posed by Kennaway in 1989: Number 10 on the List of Open Problems in Rewriting. [ABSTRACT FROM AUTHOR]

We study confluence and the Church-Rosser property in term rewriting and λ-calculus with explicit bounds on term sizes and reduction lengths. Given a system R, we are interested in the lengths of the reductions in the smallest valleys t →* s' *← t' expressed as a function: for confluence a function vsR(m, n) where the valleys are for peaks t *← s →* t' with s of size at most m and the reductions of maximum length n, and for the Church-Rosser property a function cvsR(m, n) where the valleys are for conversions t ↔* t' with t and t' of size at most mand the conversion of maximum length n. For confluent Term Rewriting Systems (TRSs), we prove that vsR is a total computable function, and for linear such systems that cvsR is a total computable function. Conversely, we show that every total computable function is the lower bound on the functions vsR(m, n) and cvsR(m, n) for some TRS R: In particular, we show that for every total computable function φ : N -→ N there is a TRS R with a single term s such that vsR(|s|, n) ≥ φ(n) and cvsR(n, n) ≥ φ(n) for all n. For orthogonal TRSs R we prove that there is a constant k such that: (a) vsR(m, n) is bounded from above by a function exponential in k and (b) cvsR(m, n) is bounded from above by a function in the fourth level of the Grzegorczyk hierarchy. Similarly, for λ-calculus, we show that vsR(m, n) is bounded from above by a function in the fourth level of the Grzegorczyk hierarchy. [ABSTRACT FROM AUTHOR]

We investigate the distribution of digits of large prefixes of the expansion of irrational algebraic numbers to different bases. We compute 2.318 bits of the binary expansions (corresponding to 2.33.108 decimals) of the 39 least Pisot-Vijayaraghavan numbers, the 47 least known Salem numbers, the least 20 square roots of positive integers that are not perfect squares, and 15 randomly generated algebraic irrationals. We employ these to compute the generalized serial statistics (roughly, the variant of the χ2-statistic apt for distribution of sequences of characters) of the distributions of digit blocks for each number to bases 2, 3, 5, 7 and 10, as well as the maximum relative frequency deviation from perfect equidistribution. We use the two statistics to perform tests at significance level α = 0.05, respectively, maximum deviation threshold α = 0.05. Our results suggest that if Borel's conjecture-that all irrational algebraic numbers are normal-is true, then it may have an empirical base: The distribution of digits in algebraic numbers appears close to equidistribution for large prefixes of their expansion. Of the 121 algebraic numbers studied, all numbers passed the maximum relative frequency deviation test in all considered bases for digit block sizes 1, 2, 3, and 4; furthermore, 92 numbers passed all tests up to block size 4 in all bases considered. [ABSTRACT FROM AUTHOR]

Our goal is to provide a top-down approach to biomolecular computation. In spite of widespread discussion about connections between biology and computation, one question seems notable by its absence: Where are the programs? We identify a number of common features in programming that seem conspicuously absent from the literature on biomolecular computing; to partially redress this absence, we introduce a model of computation that is evidently programmable, by programs reminiscent of low-level computer machine code; and at the same time biologically plausible: its functioning is defined by a single and relatively small set of chemical-like reaction rules. Further properties: the model is stored-program: programs are the same as data, so programs are not only executable, but are also compilable and interpretable. It is universal: all computable functions can be computed (in natural ways and without arcane encodings of data and algorithm); it is also uniform: new \hardware" is not needed to solve new problems; and (last but not least) it is Turing complete in a strong sense: a universal algorithm exists, that is able to execute any program, and is not asymptotically inefficient. [ABSTRACT FROM AUTHOR]

We prove that the topological entropy of subshifts having decidable language is uncomputable in the following sense: For no error bound less than 1/4 does there exists a program that, given a decision procedure for the language of a subshift as input, will approximate the entropy of the subshift within the error bound. In addition, we prove that not only is the topological entropy of sofic shifts computable to arbitary precision (a well-known fact), but all standard comparisons of the topological entropy with rational numbers are decidable. [ABSTRACT FROM AUTHOR]

We prove that the topological entropy of subshifts having decidable language is uncomputable in the following sense: For no error bound less than ¼ does there exists a program that, given a decision procedure for the language of a subshift as input, will approximate the entropy of the subshift within the error bound. In addition, we prove that not only is the topological entropy of sofic shifts computable to arbitary precision (a well-known fact), but all standard comparisons of the topological entropy with rational numbers are decidable. [ABSTRACT FROM AUTHOR]