The store language of an automaton is the set of store configurations (state and store contents, but not the input) that can appear as an intermediate step in an accepting computation. A one-way nondeterministic finite-visit Turing machine ( fvNTM ) is a Turing machine with a one-way read-only input tape, and a single worktape, where there is some number k such that in every accepting computation, each worktape cell is visited at most k times. We show that the store language of every fvNTM is a regular language. Furthermore, we show that the store language of every fvNTM augmented by reversal-bounded counters can be accepted by a machine with only reversal-bounded counters and no worktape. Several applications are given to problems in the areas of verification and fault tolerance, and to the study of right quotients. We also continue the investigation of the store languages of one-way and two-way machine models where we present some conditions under which their store languages are recursive or non-recursive.

A language C is a code relative to L if every word in L has a unique factorization into words of C; this is a generalization of a code. We extend this notion to d-decodability (respectively, finite-decodability) for $$d \ge 1$$ , which means that every word in L has at most d (respectively, a finite number of) factorizations into words of C. We study decidability of testing this property on languages accepted (respectively, generated) by different machine (respectively, grammar) models. Then, we study applications of finite decodability towards a new notion regarding bounded languages called C-boundedness for a language C, leading to several new and general decidability results. In particular, we show that in any family with a decidable finiteness problem that is effectively closed under homomorphism, inverse homomorphism, and intersection with regular languages, it is decidable, given a language L in the family and a set $$\varSigma ^{\le l}$$ of all strings of length at most l over $$\varSigma $$ , whether there exist words $$w_1, \ldots , w_n$$ in $$\varSigma ^{\le l}$$ such that $$L \subseteq w_1^* \cdots w_n^*$$ . This can be considered as a finite analog of the boundedness problem. This also implies that the letter-boundedness problem is always decidable in these families.

Predicting and tracking objects in real-world scenarios is a critical challenge in Video Object Segmentation (VOS) tasks. Unsupervised VOS (UVOS) has the additional challenge of finding an initial segmentation of salient objects, which affects the entire process and keeps a permanent uncertainty about the object proposals. Moreover, deformation and fast motion can lead to temporal inconsistencies. To address these problems, we propose Frequent Temporally Integrated Objects (FTIO), a post-processing framework with two key components. First, we introduce a combined criterion to improve object selection, mitigating failures common in UVOS—particularly when objects are small or structurally complex—by extracting frequently appearing salient objects. Second, we present a three-stage method to correct temporal inconsistencies by integrating missing object mask regions. Experimental results demonstrate that FTIO achieves state-of-the-art performance in multi-object UVOS. Code is available at: https://github.com/MohammadMohammadzadehKalati/FTIO.

A new model of multicounter machines is introduced where testing the counter status of a counter is optional, rather than existing models where they are always either required (traditional multicounter machines) or no status can be checked (partially-blind multicounter machines). If, in every accepting computation, each counter has a bounded number of occurrences where its status is tested and verified to be zero, then the machine is called finite-testable . One-way nondeterministic finite-testable multicounter machines are shown to be equivalent to partially-blind multicounter machines. However, one-way deterministic finite-testable multicounter machines are strictly more powerful than deterministic partially-blind machines. Interestingly, one-way deterministic finite-testable multicounter machines are shown to have a decidable containment problem. This makes it the most general known model where this problem is decidable, making the class important in the areas of model checking and formal verification. We also study properties of their reachability sets.

The notions of stability, anti-stability, and error-correctability of a language that is modified by making contextual insertions in the words of the language were introduced in a previous paper by Bottoni et al. in 2011, where it was shown that these properties are decidable for regular languages. The authors proposed investigating the decidability of these properties for other classes of languages. Here, we derive necessary and sufficient conditions for a class of languages to have decidable stable, anti-stable, and error-correctable properties, and use these conditions to exhibit general classes of languages (strictly greater than the regular languages) for which the properties are decidable, and also simple classes (the first such classes) for which the properties are undecidable. We obtain identical results for the case when contextual deletions (instead of insertions) are made in the words of the language, and also with mixes of insertions and deletions . Our constructions also demonstrate that certain general problems involving nondeterministic generalized sequential machines ( GSM s) applied to languages accepted by deterministic machine models are decidable, which is surprising as the deterministic language families do not need to be closed under GSM mappings.

This paper proposes a whole genome alignment-based structural variant (SV) identification method that uses chromosome-level genome assemblies. The method detects the presence of SVs between two genomes by scanning whole genome alignments for patterns corresponding to different SV types. The process is implemented as a software pipeline named Structural Variant Pattern Evidence Scan, or SVPS, made with the Snakemake [1] workflow management system. For validation, SVPS was assessed through two case studies on two plant genomes – Brassica nigra and Arabidopsis thaliana. Alignment sensitivity significantly impacted SVPS’s results, causing differences in the number, locations, and sizes of SVs reported. SVPS detected significantly more SVs than other whole genome alignment SV tools. Still, the high accuracy of its results when evaluated with another independent aligner demonstrates that there is value in its higher sensitivity. SVPS is available publicly under MIT license at https://github.com/USask-BINFO/SVPS.

Abstract We consider a general class of decision problems concerning formal languages, called “(one-dimensional) unboundedness predicates”, for automata that feature reversal-bounded counters (RBCA). We show that each problem in this class reduces—non-deterministically in polynomial time—to the same problem for just finite automata. We also show an analogous reduction for automata that have access to both a pushdown stack and reversal-bounded counters (PRBCA). This allows us to answer several open questions: For example, we show that it is $$\textsf{coNP}$$ coNP -complete to decide whether a given (P)RBCA language L is bounded, meaning whether there exist words $$w_1,\ldots ,w_n$$ w 1 , … , w n with $$L\subseteq w_1^*\cdots w_n^*$$ L ⊆ w 1 ∗ ⋯ w n ∗ . For PRBCA, even decidability was open. Our methods also show that there is no language of a (P)RBCA of intermediate growth. This means, the number of words of each length grows either polynomially or exponentially. Part of our proof is likely of independent interest: We show that one can translate an RBCA into a machine with $$\mathbb {Z}$$ Z -counters in logarithmic space, while preserving the accepted language.

BACKGROUND: Gene co-expression networks (GCNs) are not easily comparable due to their complex structure. In this paper, we propose a tool, Juxtapose, together with similarity measures that can be utilized for comparative transcriptomics between a set of organisms. While we focus on its application to comparing co-expression networks across species in evolutionary studies, Juxtapose is also generalizable to co-expression network comparisons across tissues or conditions within the same species. METHODS: A word embedding strategy commonly used in natural language processing was utilized in order to generate gene embeddings based on walks made throughout the GCNs. Juxtapose was evaluated based on its ability to embed the nodes of synthetic structures in the networks consistently while also generating biologically informative results. Evaluation of the techniques proposed in this research utilized RNA-seq datasets from GTEx, a multi-species experiment of prefrontal cortex samples from the Gene Expression Omnibus, as well as synthesized datasets. Biological evaluation was performed using gene set enrichment analysis and known gene relationships in literature. RESULTS: We show that Juxtapose is capable of globally aligning synthesized networks as well as identifying areas that are conserved in real gene co-expression networks without reliance on external biological information. Furthermore, output from a matching algorithm that uses cosine distance between GCN embeddings is shown to be an informative measure of similarity that reflects the amount of topological similarity between networks. CONCLUSIONS: Juxtapose can be used to align GCNs without relying on known biological similarities and enables post-hoc analyses using biological parameters, such as orthology of genes, or conserved or variable pathways. AVAILABILITY: A development version of the software used in this paper is available at https://github.com/klovens/juxtapose.

Lindenmayer Systems (L-systems) are formal grammars that use rewriting rules to replace, in parallel, every symbol in a string with a replacement string. By iterating, a sequence of strings is produced whose symbols can model temporal processes by interpreting them as simulation instructions. Among the types of L-systems, parametric L-systems are considered useful for simulating mechanisms that change based on different influences as the parameters change. Typically, L-systems are found by taking precise measurements and using existing knowledge, which can be addressed by automatic inference. This paper presents the Plant Model Inference Tool for Parametric L-systems (PMIT-PARAM) that can automatically learn parametric L-systems from a sequence of strings generated, where at least one parameter represents time. PMIT-PARAM is evaluated on a test suite of 20 known parametric L-systems, and is found to be able to infer the correct rewriting rules for the 18 L-systems containing only non-erasing productions; however, it can find appropriate parametric equations for all 20 of the L-systems. Inferring L-systems algorithmically not only can automatically learn models and simulations of a process with potentially less effort than doing so by hand, but it may also help reveal the scientific principles governing how the process' mechanisms change over time.

Stochastic context-free Lindenmayer systems (S0L-systems) are a formal grammar system that produce sequences of strings based on parallel rewriting rules over a probability distribution. The resulting words can be treated as symbolic instructions to create visual models by simulation software. S0L-system have been used to model different natural and engineered processes. One issue with S0L-systems is the difficulty in determining an S0L-systems to model a process. Current approaches either infer S0L-systems based on aesthetics or rely on a priori expert knowledge. This work introduces PMIT-S0L, a tool for inferring S0L-systems from a sequence of strings generated by a (hidden) L-system, using a greedy algorithm hybridized with search algorithms. PMIT-S0L was evaluated using 3600 procedurally generated S0L-systems and is able to infer the test set with 100% success so long as there are 12 or less rewriting rules in total in the L-system. This makes PMIT-S0L applicable for many practical applications.

As the most abundant active transposable elements, Alu elements have 1.1 million copies and occupy 6% of the human genome. Recent evidence indicates that 22 AluY and 6 AluS subfamilies have been the most active Alu elements in recent human history, whose transposition has been implicated in several inherited human diseases and in various forms of cancer by integrating into genes; therefore, understanding the transpositional activity and factors that change the activity level of these TEs is very important. There has been some work done to quantify and analyze the transposition of active Alu transposable elements in mobile assays. Based on this activity data, a method/simulation was created in this paper to computationally identify the regions on a TE consensus sequence that may change the transpositional activity. This method was applied to AluY, the youngest and most active Alu subfamily, to identify the harmful regions laying in its consensus. Mutations occurring within these regions have crucial effects in decreasing the elements' transposition. The identified regions were then verified by the secondary structure of the AluY RNA, where the harmful regions overlapped with the AluY RNA major SRP9/14 contact sites. An additional simulation also showed that the identified harmful regions covering the AluY RNA functional regions is not by chance. Therefore, we conclude that mutations occurring within the harmful regions identified alter the mobile activity levels of active AluY elements.

This paper presents the design of a new web browser, the Tree Trailblazer, which allows users to browse the web while maintaining a visual record of their exploration path, or trail, through the information space. This design enhances the backtracking aspects of web browsing over current designs by providing visual cues regarding the pages related to the page being viewed, providing users with an understanding of their position in the trail. This design also helps users blaze new trails off a page by allowing them to open previews of pages off of the currently viewed page. The scenario based design process that was used to construct the browser is discussed in conjunction with the initial prototype implementation. A formative user evaluation of this prototype showed this browser design to be very easy to learn and highly usable, with particular attention being paid to aspects of the tree visualization.