Nondeterministic multicounter machines and complementation (Q1825044)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Nondeterministic multicounter machines and complementation |
scientific article; zbMATH DE number 4119649
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Nondeterministic multicounter machines and complementation |
scientific article; zbMATH DE number 4119649 |
Statements
Nondeterministic multicounter machines and complementation (English)
0 references
1989
0 references
For any polynomial f, the class of languages accepted by nondeterministic one-way multicounter automata within f(n) steps is not closed under complement. This is shown by exhibiting a witness set using a counting argument. The same is true if multicounter is replaced with k counter for arbitrary natural \(k>0\).
0 references
counter machines
0 references
closure under complement
0 references
counting arguments
0 references
0 references
