An official website of the United States government
One approach to probabilistic inference involves counting the number of models of a given Boolean formula. Here, we are interested in inferences involving higher-order objects, i.e., functions. We study the following task: Given a Boolean specification between a set of inputs and outputs, count the number of functions of inputs such that the specification is met. Such functions are called Skolem functions.We are motivated by the recent development of scalable approaches to Boolean function synthesis. This stands in relation to our problem analogously to the relationship between Boolean satisfiability and the model counting problem. Yet, counting Skolem functions poses considerable new challenges. From the complexity-theoretic standpoint, counting Skolem functions is not only #P-hard; it is quite unlikely to have an FPRAS (Fully Polynomial Randomized Approximation Scheme) as the problem of synthesizing a Skolem function remains challenging, even given access to an NP oracle.The primary contribution of this work is the first algorithm, SkolemFC, that computes the number of Skolem functions. SkolemFC relies on technical connections between counting functions and propositional model counting: our algorithm makes a linear number of calls to an approximate model counter and computes an estimate of the number of Skolem functions with theoretical guarantees. Our prototype displays impressive scalability, handling benchmarks comparably to state-of-the-art Skolem function synthesis engines, even though counting all such functions ostensibly poses a greater challenge than synthesizing a single function.
more »
« less
Middle school students' development of an understanding of the concept of function using an applet with no algebraic representations
Abstract Middle school students (n = 144) worked with an applet specially designed to introduce the concept of function without using algebraic representations. The purpose of the study was to examine whether the applet would help students understand function as a relationship between a set of inputs and a set of outputs and to begin to develop a definition of function based on that relationship. Results indicate that, by focusing on consistency of the outputs, the students, at a rate of approximately 80%, are able to distinguish functions from nonfunctions. Also, students showed some promise in recognizing constant functions as functions, a known area of common misconceptions. Students' main conceptual difficulty, likely caused by the context, was accepting nonintuitive outputs even if those outputs were consistent.
more »
« less
- Award ID(s):
- 1820998
- PAR ID:
- 10470397
- Publisher / Repository:
- Wiley-Blackwell
- Date Published:
- Journal Name:
- School Science and Mathematics
- Volume:
- 123
- Issue:
- 6
- ISSN:
- 0036-6803
- Format(s):
- Medium: X Size: p. 278-289
- Size(s):
- p. 278-289
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Understanding microbial roles in ecosystem function requires integrating microscopic processes into food webs. The carnivorous pitcher plant,Sarracenia purpurea, offers a tractable study system where diverse food webs of macroinvertebrates and microbes facilitate digestion of captured insect prey, releasing nutrients supporting the food web and host plant. However, how interactions between these macroinvertebrate and microbial communities contribute to ecosystem functions remains unclear. We examined the role of the pitcher plant mosquito,Wyeomyia smithii, in top‐down control of the composition and function of pitcher plant microbial communities. Mosquito larval abundance was enriched or depleted across a natural population ofS. purpureapitchers over a 74‐day field experiment. Bacterial community composition and microbial community function were characterized by 16S rRNA amplicon sequencing and profiling of carbon substrate use, bulk metabolic rate, hydrolytic enzyme activity, and macronutrient pools. Bacterial communities changed from pitcher opening to maturation, but larvae exerted minor effects on high‐level taxonomic composition. Higher larval abundance was associated with lower diversity communities with distinct functions and elevated nitrogen availability. Treatment‐independent clustering also supported roles for larvae in curating pitcher microbial communities through shifts in community diversity and function. These results demonstrate top‐down control of microbial functions in an aquatic microecosystem.more » « less
-
Abstract Human impacts on ecosystems are resulting in unprecedented rates of biodiversity loss worldwide. The loss of species results in the loss of the multiple roles that each species plays or functions (i.e., “ecosystem multifunctionality”) that it provides. A more comprehensive understanding of the effects of species on ecosystem multifunctionality is necessary for assessing the ecological impacts of species loss. We studied the effects of two dominant intertidal species, a primary producer (the seaweedNeorhodomela oregona) and a consumer (the shellfishMytilus trossulus), on 12 ecosystem functions in a coastal ecosystem, both in undisturbed tide pools and following the removal of the dominant producer. We modified analytical methods used in biodiversity–multifunctionality studies to investigate the potential effects of individual dominant species on ecosystem function. The effects of the two dominant species from different trophic levels tended to differ in directionality (+/−) consistently (92% of the time) across the 12 individual functions considered. Using averaging and multiple threshold approaches, we found that the dominant consumer—but not the dominant producer—was associated with ecosystem multifunctionality. Additionally, the relationship between abundance and multifunctionality differed depending on whether the dominant producer was present, with a negative relationship between the dominant consumer and ecosystem function with the dominant producer present compared to a non‐significant, positive trend where the producer had been removed. Our findings suggest that interactions among dominant species can drive ecosystem function. The results of this study highlight the utility of methods previously used in biodiversity‐focused research for studying functional contributions of individual species, as well as the importance of species abundance and identity in driving ecosystem multifunctionality, in the context of species loss.more » « less
-
Abstract We address a problem of promoting instructional transformation in early undergraduate mathematics courses, via an intervention incorporating novel digital resources (“techtivities”), in conjunction with a faculty learning community (FLC). The techtivities can serve as boundary objects, in order to bridge different communities to which instructors belong. Appealing to Etienne Wenger’s Communities of Practice theory, we theorise a role of the instructor as a broker, facilitating “boundary transitions” within, across, and beyond a set of digital resources. By “boundary transition”, we mean a transition that is also a brokering move; instructors connect different communities as they draw links between items in their instruction. To ground our argument, we provide empirical evidence from an instructor, Rachel, whose boundary transitions served three functions: (1) to position the techtivities as something that count in the classroom community and connect to topics valued by the broader mathematics community; (2) to communicate to students that their reasoning matters more than whether they provide a correct answer, a practice promoted in the FLC; (3) to connect students’ responses to mathematical ideas discussed in the FLC, in which graphs represent a relationship between variables. Instructors’ boundary transitions can serve to legitimise novel digital resources within an existing course and thereby challenge thestatus quoin courses where skills and procedures may take precedence over reasoning and sense-making.more » « less
-
Nguyen, Nhu H (Ed.)ABSTRACT Across diverse ecosystems, bacteria and their hosts engage in complex relationships having negative, neutral, or positive interactions. However, the specific effects of leaf-associated bacterial community functions on plant growth are poorly understood. Although microbes can promote plant growth through various biochemical mechanisms, investigating the community’s functional contributions to plant growth remains to be explored. To address this gap, we characterized the relationships between bacterial community function and host plant growth in the purple pitcher plant (Sarracenia purpurea). The main aim of our research was to investigate how different bacterial community functions affect the growth and nutrient content in the plant. Previous research has suggested that microbial communities aid in prey decomposition and subsequent nutrient acquisition in carnivorous plants, includingS. purpurea. However, the specific functional roles of bacterial communities in plant growth and nutrient uptake are not well known. In this study, sterile, freshly opened pitchers were inoculated with three functionally distinct, pre-assembled bacterial communities. Bacterial community composition and function were measured over 8 weeks using physiological assays, metagenomics, and metatranscriptomics. Distinct community functions affected plant traits; a bacterial community enriched in decomposition was associated with larger leaves with almost double the biomass of control pitchers. Physiological differences in bacterial communities were supported by metatranscriptomics; for example, the bacterial community with the highest chitinase activity had greater expression of transcripts associated with chitinase enzymes. The relationship between bacterial community function and plant growth observed here indicates potential mechanisms, such as chitinase activity, for host-associated bacterial functions to support pitcher plant growth. IMPORTANCEThis study addresses a gap in understanding the relationships between bacterial community function and plant growth. We inoculated sterile, freshly opened pitcher plant leaves with three functionally distinct bacterial communities to uncover potential mechanisms through which bacterial functions support plant health and growth. Our findings demonstrate that distinct community functions significantly influence plant traits, with some bacterial communities supporting more plant growth than in control pitchers. These results highlight the ecological roles of microbial communities in plants and thus ecosystems and suggest that nutrient cycling is an important pathway through which microbes support host plant health. This research provides valuable insights into plant-microbe interactions and the effects of diverse microbial community functions.more » « less
