2021/05/22 by A. N. Trahtman, Trahtman, A. N.
Biochemistry, Genetics and Molecular Biology · Computer Science · #68W32 68R10 05C20 05C85 #DNA and Biological Computing #F.2.2 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #I.2.7 #acm:05C20 #acm:05C85 #acm:68R10 #acm:68W32 #cs.FL #msc:05C20 #msc:05C85 #msc:68R10 #msc:68W32 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2105.10654
8 pages, 6 figures, PTSD conference, Lecture notes of computer science
openalex created_date 2016/07/22 · arxiv created 2021/05/22 · openalex publication_date 2021/05/22 · arxiv updated 2021/05/25 · openalex updated_date 2026/07/28
A locally threshold testable language L is a language with the property that for some non negative integers k and l, whether or not a word u is in the language L depends on (1) the prefix and suffix of the word u of length k > 1 and (2) the set of intermediate substrings of length k of the word u where the sets of substrings occurring at least j times are the same, for j <= L. For given k and L the language is called l-threshold k-testable. A finite deterministic automaton is called l-threshold k-testable if the automaton accepts a l-threshold k-testable language. In this paper, the necessary and sufficient conditions for an automaton to be locally threshold testable are found. We introduce the first polynomial time algorithm to verify local threshold testability of the automaton based on this characterization. New version of polynomial time algorithm to verify the local testability will be presented too.