2010/04/12 by Udayan B. Darji, Darji, Udayan B., Steve W. Seif +1
Computer Science · #03D15. #68Q15 #68Q45 #68Q80 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #cs.FL #msc:03D15. #msc:68Q15 #msc:68Q45 #msc:68Q80
paper · pdf · doi:10.48550/arxiv.1004.1946
arxiv created 2010/04/12 · arxiv updated 2010/04/13
A regular language L is said to be cellular if there exists a 1-dimensional cellular automaton CA such that L is the language consisting of the finite blocks associated with CA. It is shown that cellularity of a regular language is decidable using a new characterization of cellular languages formulated by Freiling, Goldstein and Moews and implied by a deep result of Boyle in symbolic dynamics.