Search results for "CTD"
showing 10 items of 101 documents
Automata and forbidden words
1998
Abstract Let L ( M ) be the (factorial) language avoiding a given anti-factorial language M . We design an automaton accepting L ( M ) and built from the language M . The construction is effective if M is finite. If M is the set of minimal forbidden words of a single word ν, the automaton turns out to be the factor automaton of ν (the minimal automaton accepting the set of factors of ν). We also give an algorithm that builds the trie of M from the factor automaton of a single word. It yields a nontrivial upper bound on the number of minimal forbidden words of a word.
On the Hierarchy Classes of Finite Ultrametric Automata
2015
This paper explores the language classes that arise with respect to the head count of a finite ultrametric automaton. First we prove that in the one-way setting there is a language that can be recognized by a one-head ultrametric finite automaton and cannot be recognized by any k-head non-deterministic finite automaton. Then we prove that in the two-way setting the class of languages recognized by ultrametric finite k-head automata is a proper subclass of the class of languages recognized by (k + 1)-head automata. Ultrametric finite automata are similar to probabilistic and quantum automata and have only just recently been introduced by Freivalds. We introduce ultrametric Turing machines an…
Descriptional and Computational Complexity of the Circuit Representation of Finite Automata
2018
In this paper we continue to investigate the complexity of the circuit representation of DFA—BC-complexity. We compare it with nondeterministic state complexity, obtain upper and lower bounds which differ only by a factor of 4 for a Binary input alphabet. Also we prove that many simple operations (determining if a state is reachable or if an automaton is minimal) are PSPACE-complete for DFA given in circuit representation.
Deciding properties of integral relational automata
1994
This paper investigates automated model checking possibilities for CTL* formulae over infinite transition systems represented by relational automata (RA). The general model checking problem for CTL* formulae over RA is shown undecidable, the undecidability being observed already on the class of Restricted CTL formulae. The decidability result, however, is obtained for another substantial subset of the logic, called A-CTL*+, which includes all ”linear time” formulae.
The set of conjugacy class sizes of a finite group does not determine its solvability
2014
Abstract We find a pair of groups, one solvable and the other non-solvable, with the same set of conjugacy class sizes.
Finite automata with advice tapes
2013
We define a model of advised computation by finite automata where the advice is provided on a separate tape. We consider several variants of the model where the advice is deterministic or randomized, the input tape head is allowed real-time, one-way, or two-way access, and the automaton is classical or quantum. We prove several separation results among these variants, demonstrate an infinite hierarchy of language classes recognized by automata with increasing advice lengths, and establish the relationships between this and the previously studied ways of providing advice to finite automata.
The computational power of continuous time neural networks
1997
We investigate the computational power of continuous-time neural networks with Hopfield-type units. We prove that polynomial-size networks with saturated-linear response functions are at least as powerful as polynomially space-bounded Turing machines.
Technical Aspects for the Evaluation of Circulating Nucleic Acids (CNAs): Circulating Tumor DNA (ctDNA) and Circulating MicroRNAs
2017
Circulating nucleic acids (CNAs), for example, circulating tumor DNA (ctDNA) and circulating microRNA (miRNA), represent promising biomarkers in several diseases including cancer. They can be isolated from many body fluids, such as blood, saliva, and urine. Also ascites, cerebrospinal fluids, and pleural effusion may be considered as a source of CNAs, but with several and intrinsic limitations. Therefore, blood withdrawal represents one of the best sources for CNAs due to the very simple and minimally invasive way of sampling. Moreover, it can be repeated at different time points, giving the opportunity for a real-time monitoring of the disease.
Metastatic site location influences the diagnostic accuracy of ctDNA EGFR- mutation testing in NSCLC patients: a pooled analysis
2018
Background: Recent studies evaluated the diagnostic accuracy of circulating tumor DNA (ctDNA) analysis in the detection of epidermal growth factor receptor (EGFR) mutations from plasma of NSCLC patients, overall showing a high concordance as compared to standard tissue genotyping. However it is less clear if the location of metastatic site may influence the ability to identify EGFR mutations. Objective: This pooled analysis aims to evaluate the association between the metastatic site location and the sensitivity of ctDNA analysis in detecting EGFR mutations in NSCLC patients. Methods: Data from all published studies, evaluating the sensitivity of plasma-based EGFRmutation testing, stratifi…
Minimal forbidden words and factor automata
1998
International audience; Let L(M) be the (factorial) language avoiding a given antifactorial language M. We design an automaton accepting L(M) and built from the language M. The construction is eff ective if M is finite. If M is the set of minimal forbidden words of a single word v, the automaton turns out to be the factor automaton of v (the minimal automaton accepting the set of factors of v). We also give an algorithm that builds the trie of M from the factor automaton of a single word. It yields a non-trivial upper bound on the number of minimal forbidden words of a word.