Dataset Information

Dynamic Data Structures for Timed Automata Acceptance.

ABSTRACT: We study a variant of the classical membership problem in automata theory, which consists of deciding whether a given input word is accepted by a given automaton. We do so through the lenses of parameterized dynamic data structures: we assume that the automaton is fixed and its size is the parameter, while the input word is revealed as in a stream, one symbol at a time following the natural order on positions. The goal is to design a dynamic data structure that can be efficiently updated upon revealing the next symbol, while maintaining the answer to the query on whether the word consisting of symbols revealed so far is accepted by the automaton. We provide complexity bounds for this dynamic acceptance problem for timed automata that process symbols interleaved with time spans. The main contribution is a dynamic data structure that maintains acceptance of a fixed one-clock timed automaton A with amortized update time 2O(|A|) per input symbol.

SUBMITTER: Grez A

PROVIDER: S-EPMC9596569 | biostudies-literature | 2022

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

Dynamic Data Structures for Timed Automata Acceptance.

Grez Alejandro A Mazowiecki Filip F Pilipczuk Michał M Puppis Gabriele G Riveros Cristian C

Algorithmica 20220905 11

We study a variant of the classical membership problem in automata theory, which consists of deciding whether a given input word is accepted by a given automaton. We do so through the lenses of parameterized dynamic data structures: we assume that the automaton is fixed and its size is the parameter, while the input word is revealed as in a stream, one symbol at a time following the natural order on positions. The goal is to design a dynamic data structure that can be efficiently updated upon re ...[more]

PMID: 36313790

Similar Datasets

Project description:Dynamic control of gene expression mainly relies on inducible systems, which require supplementation of (costly) inducer molecules. In contrast, synthetic regulatory circuits, which allow the timed shutdown of gene expression, are rarely available and therefore represent highly attractive tools for metabolic engineering. To achieve this, we utilized the VanR/P vanABK * regulatory system of Corynebacterium glutamicum, which consists of the transcriptional repressor VanR and a modified promoter of the vanABK operon (P vanABK *). VanR activity is modulated by one of the phenolic compounds ferulic acid, vanillin or vanillic acid, which are co-metabolized with d-glucose. Thus, gene expression in the presence of d-glucose is turned off if one of the effector molecules is depleted from the medium. To dynamically control the expression of the aceE gene, encoding the E1 subunit of the pyruvate dehydrogenase complex that is essential for growth on d-glucose, we replaced the native promoter by vanR/P vanABK * yielding C. glutamicum ΔP aceE ::vanR-P vanABK *. The biomass yield of this strain increased linearly with the supplemented amount of effector. After consumption of the phenolic compounds growth ceased, however, C. glutamicumΔP aceE ::vanR-P vanABK * continued to utilize the residual d-glucose to produce significant amounts of pyruvate, l-alanine, and l-valine. Interestingly, equimolar concentrations of the three phenolic compounds resulted in different biomass yields; and with increasing effector concentration, the product spectrum shifted from pyruvate over l-alanine to l-valine. To further test the suitability of the VanR/P vanABK * system, we overexpressed the l-valine biosynthesis genes ilvBNCE in C. glutamicum ΔP aceE ::vanR-P vanABK *, which resulted in efficient l-valine production with a yield of about 0.36 mol l-valine per mol d-glucose. These results demonstrate that the VanR/P vanABK * system is a valuable tool to control gene expression in C. glutamicum in a timed manner by the cheap and abundant phenolic compounds ferulic acid, vanillin, and vanillic acid.

Project description:We argue in favor of representing living cells as automata and review demonstrations that autonomous cells can form patterns by responding to local variations in the strain fields that arise from their individual or collective motions. An autonomous cell's response to strain stimuli is assumed to be effected by internally-generated, internally-powered forces, which generally move the cell in directions other than those implied by external energy gradients. Evidence of cells acting as strain-cued automata have been inferred from patterns observed in nature and from experiments conducted in vitro. Simulations that mimic particular cases of pattern forming share the idealization that cells are assumed to pass information among themselves solely via mechanical boundary conditions, i.e., the tractions and displacements present at their membranes. This assumption opens three mechanisms for pattern formation in large cell populations: wavelike behavior, kinematic feedback in cell motility that can lead to sliding and rotational patterns, and directed migration during invasions. Wavelike behavior among ameloblast cells during amelogenesis (the formation of dental enamel) has been inferred from enamel microstructure, while strain waves in populations of epithelial cells have been observed in vitro. One hypothesized kinematic feedback mechanism, "enhanced shear motility", accounts successfully for the spontaneous formation of layered patterns during amelogenesis in the mouse incisor. Directed migration is exemplified by a theory of invader cells that sense and respond to the strains they themselves create in the host population as they invade it: analysis shows that the strain fields contain positional information that could aid the formation of cell network structures, stabilizing the slender geometry of branches and helping govern the frequency of branch bifurcation and branch coalescence (the formation of closed networks). In simulations of pattern formation in homogeneous populations and network formation by invaders, morphological outcomes are governed by the ratio of the rates of two competing time dependent processes, one a migration velocity and the other a relaxation velocity related to the propagation of strain information. Relaxation velocities are approximately constant for different species and organs, whereas cell migration rates vary by three orders of magnitude. We conjecture that developmental processes use rapid cell migration to achieve certain outcomes, and slow migration to achieve others. We infer from analysis of host relaxation during network formation that a transition exists in the mechanical response of a host cell from animate to inanimate behavior when its strain changes at a rate that exceeds 10-4-10-3s-1. The transition has previously been observed in experiments conducted in vitro.

Dataset Information

Dynamic Data Structures for Timed Automata Acceptance.

Publications

Dynamic Data Structures for Timed Automata Acceptance.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets