Chistikov, Dmitry
Notes on Counting with Finite Machines
Abstract
We determine the descriptional complexity (smallest number of states, up to constant factors) of recognizing languages {1^n} and {1^{t n} : t = 0, 1, 2, ...} with statebased finite machines of various kinds. This task is understood as counting to n and modulo n, respectively, and was previously studied for classes of finitestate automata by Kupferman, TaShma, and Vardi (2001). We show that for Turing machines it requires log(n)/log(log(n)) states in the worst case, and individual values are related to Kolmogorov complexity of the binary encoding of n. For deterministic pushdown and counter automata, the complexity is log(n) and sqrt(n), respectively; for alternating counter automata, we show an upper bound of log(n). For visibly pushdown automata, i.e., if the stack movements are determined by input symbols, we consider languages {a^n b^n} and {a^{t n} b^{t n} : n t = 0, 1, 2, ...} and determine their complexity, of sqrt(n) and min(n_1 + n_2), respectively, with minimum over all factorizations n = n_1 n_2.
BibTeX  Entry
@InProceedings{chistikov:LIPIcs:2014:4854,
author = {Dmitry Chistikov},
title = {{Notes on Counting with Finite Machines}},
booktitle = {34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
pages = {339350},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897774},
ISSN = {18688969},
year = {2014},
volume = {29},
editor = {Venkatesh Raman and S. P. Suresh},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4854},
URN = {urn:nbn:de:0030drops48547},
doi = {10.4230/LIPIcs.FSTTCS.2014.339},
annote = {Keywords: State complexity, Unary languages, Counting}
}
2014
Keywords: 

State complexity, Unary languages, Counting 
Seminar: 

34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)

Issue date: 

2014 
Date of publication: 

2014 