License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2014.339
URN: urn:nbn:de:0030-drops-48547
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4854/
Go to the corresponding LIPIcs Volume Portal

Chistikov, Dmitry

Notes on Counting with Finite Machines

pdf-format:
30.pdf (0.5 MB)

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 state-based finite machines of various kinds. This task is understood as counting to n and modulo n, respectively, and was previously studied for classes of finite-state automata by Kupferman, Ta-Shma, 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 =	{339--350},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-77-4},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{29},
  editor =	{Venkatesh Raman and S. P. Suresh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4854},
  URN =		{urn:nbn:de:0030-drops-48547},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.339},
  annote =	{Keywords: State complexity, Unary languages, Counting}
}

Keywords: State complexity, Unary languages, Counting
Collection: 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Issue Date: 2014
Date of publication: 12.12.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI