Chistikov, Dmitry (2014) Notes on counting with finite machines. In: 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014), New Delhi, India, 15–17 Dec 2014, 29 pp. 339-350. ISBN 9783939897774. ISSN 1868-8969.

Preview

PDF WRAP-notes-counting-finite-machines-Chistikov-2018.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution. Download (800Kb) | Preview

Request Changes to record.

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.

Item Type:	Conference Item (Paper)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science, Engineering and Medicine > Science > Computer Science
Library of Congress Subject Headings (LCSH):	Counting, Unary algebras
Series Name:	Leibniz International Proceedings in Informatics (LIPIcs)
Publisher:	Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Place of Publication:	Dagstuhl, Germany
ISBN:	9783939897774
ISSN:	1868-8969
Official Date:	2014
Dates:	Date Event 2014 Published
Volume:	29
Page Range:	pp. 339-350
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Open Access (Creative Commons)
Date of first compliant deposit:	16 July 2018
Date of first compliant Open Access:	16 July 2018
Conference Paper Type:	Paper
Title of Event:	34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Type of Event:	Conference
Location of Event:	New Delhi, India
Date(s) of Event:	15–17 Dec 2014
Related URLs:	Publisher

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads