2018/12/06 by Ryoma Sin’ya, Sin'ya, Ryoma
Biochemistry, Genetics and Molecular Biology · Computer Science · #DNA and Biological Computing #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic, programming, and type systems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1812.02600
openalex publication_date 2018/12/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this note we provide a (decidable) graph-structural characterisation of the infiniteness of L(w1, ..., wk), where L(w1, ..., wk) = \w ∈ A^* | |w|w1 = ⋯ = |w|wk\ is the set of all words that contain the same number of subword occurrences of parameter words w1, ..., wk. We also provide the decidable characterisation of the equivalence for those languages. Although those two decidability results are also obtained from more general known decidability results on unambiguous constrained automata, this note tries to give a self-contained (without the knowledge about constrained automata) proof of the decidability.