The word problem distinguishes counter languages

MaRDI QIDQ6477376zbMATH OpenFDO

Authors Sean Cleary, Murray Elder, Gretchen Ostheimer

Publication date 16 June 2006

Mathematics Subject Classification ID

Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Formal languages and automata (68Q45)

Abstract: Counter automata are more powerful versions of finite-state automata where addition and subtraction operations are permitted on a set of n integer registers, called counters. We show that the word problem of $$ is accepted by a nondeterministic $m$-counter automaton if and only if $mgeqn$.

This page was built for publication: The word problem distinguishes counter languages

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