Information rate of some classes of non-regular languages: An automata-theoretic approach

We show that the information rate of the language accepted by a reversal-bounded deterministic counter machine is computable. For the nondeterministic case, we provide computable upper bounds. For the class of languages accepted by multi-tape deterministic finite automata, the information rate is co...

Full description

Saved in:
Bibliographic Details
Published in:Information and computation 2017-10, Vol.256, p.45-61
Main Authors: Cui, Cewei, Dang, Zhe, Fischer, Thomas R., Ibarra, Oscar H.
Format: Article
Language:English
Subjects:
Automata
Formal languages
Shannon information
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We show that the information rate of the language accepted by a reversal-bounded deterministic counter machine is computable. For the nondeterministic case, we provide computable upper bounds. For the class of languages accepted by multi-tape deterministic finite automata, the information rate is computable as well.
ISSN:0890-5401
1090-2651
DOI:10.1016/j.ic.2017.04.008