An optimal lower bound for nonregular languages
type: Item
instance of: scholarly article
title: An optimal lower bound for nonregular languages
zbMATH Open document ID: 0810.68089
DOI: 10.1016/0020-0190(94)00056-5
author: Alberto Bertoni
author: Carlo Mereghetti
author: Giovanni Pighizzini
published in: Information Processing Letters
publication date: 1994-07-21T00:00:00Z
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 609765
zbMATH Keywords: computational complexity
zbMATH Keywords: formal languages
zbMATH Keywords: lower bound
zbMATH Keywords: Turing machine
Wikidata QID: Q61677537
MaRDI profile type: Publication
full work available at URL: 0020-0190(94)00056-5
OpenAlex ID: W2076413258
cites work: Q3856819
cites work: Q5636862
cites work: One-tape, off-line Turing machine computations
cites work: Some Results on Tape-Bounded Turing Machines
cites work: Q3862379
cites work: Q5180413
Recommended article: Strong optimal lower bounds for Turing machines that accept nonregular languages
Recommended article: Corrigendum to ``An optimal lower bound for nonregular languages''
Recommended article: On Approximating Non-regular Languages by Regular Languages
Recommended article: Developments in Language Theory
Recommended article: NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
Recommended article: On the boundary of regular languages
Recommended article: On the Boundary of Regular Languages
Recommended article: Exponential upper and lower bounds for the order of a regular language
Recommended article: On the degree of non-regularity of context-free languages
description: scientific article; zbMATH DE number 609765