On the descriptional power of heads, counters, and pebbles
type: Item
instance of: scholarly article
title: On the descriptional power of heads, counters, and pebbles
zbMATH Open document ID: 1078.68090
author: Martin Kutrib
published in: Theoretical Computer Science
publication date: 2005-02-22T00:00:00Z
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 2136578
zbMATH Keywords: Descriptional complexity
zbMATH Keywords: State complexity
zbMATH Keywords: Non-recursive trade-offs
zbMATH Keywords: Finite automata
MaRDI profile type: Publication
full work available at URL: j.tcs.2004.04.013
OpenAlex ID: W2082543289
cites work: State-complexity of finite-state devices, state compressibility and incompressibility
cites work: Finite automata and unary languages
cites work: Q5422234
cites work: On non-determinacy in simple computing devices
cites work: On the Succinctness of Different Representations of Languages
cites work: Q5592246
cites work: Q4449194
cites work: A note on rebound automata
cites work: Tight lower bounds on the size of sweeping automata
cites work: Q4465339
cites work: Q4503152
cites work: Optimal simulations between unary automata
cites work: Transformational methods and their application to complexity problems
cites work: Transformational methods and their application to complexity problems. Corrigenda
cites work: Q4941906
cites work: Q4536395
cites work: Language recognition by marking automata
cites work: Nondeterminism and the size of two way finite automata
cites work: A note on multihead automata and context-sensitive languages
cites work: Succinctness of Descriptions of Unambiguous Context-Free Languages
cites work: Relating refined space complexity classes
cites work: Halting space-bounded computations
cites work: Lower bounds on the size of sweeping automata
cites work: A note on the succinctness of descriptions of deterministic languages
DOI: 10.1016/J.TCS.2004.04.013
description: scientific article; zbMATH DE number 2136578