2005/01/05 by Mircea Alexandru Popescu Moscu, Mircea Moscu, Moscu, Mircea Alexandru Popescu
Computer Science · #Advanced Algebra and Logic #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #cs.CC #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.cs/0501009
arxiv created 2005/01/05 · openalex publication_date 2005/01/05 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The present paper presents and proves a proposition concerning the time complexity of finite languages. It is shown herein, that for any finite language (a language for which the set of words composing it is finite) there is a Turing machine that computes the language in such a way that for any input of length k the machine stops in, at most, k + 1 steps.