Notes on counting with finite machines

DOI10.4230/LIPICS.FSTTCS.2014.339MaRDI QIDQ2978526zbMATH OpenOpenAlexFDO

Authors Dmitry Chistikov

Publication date 25 April 2017

Full work available at URL https://doi.org/10.4230/lipics.fsttcs.2014.339

zbMATH Keywords

countingstate complexityunary languages

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 4092773
• scientific article; zbMATH DE number 4209603
• Automaticity. II: Descriptional complexity in the unary case
• On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata
• The state complexity of alternating automata

Cited in

(6)

• Arithmetization of register machines with counters
• scientific article; zbMATH DE number 4209603 (Why is no real title available?)
• ON COUNTER MACHINES, REACHABILITY PROBLEMS, AND DIOPHANTINE EQUATIONS
• scientific article; zbMATH DE number 4092773 (Why is no real title available?)
• On a conjecture by Christian Choffrut
• Weight-reducing Hennie machines and their descriptional complexity

This page was built for publication: Notes on counting with finite machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2978526)