An optimal lower bound for nonregular languages

DOI10.1016/0020-0190(94)00056-5zbMATH Open0810.68089OpenAlexW2076413258WikidataQ61677537 ScholiaQ61677537MaRDI QIDQ1330656FDOQ1330656

Authors: Alberto Bertoni, Carlo Mereghetti, Giovanni Pighizzini 

Publication date: 21 July 1994

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(94)00056-5

Recommendations

• Strong optimal lower bounds for Turing machines that accept nonregular languages
• Corrigendum to ``An optimal lower bound for nonregular languages
• On approximating non-regular languages by regular languages
• Developments in Language Theory
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• On the boundary of regular languages
• On the boundary of regular languages
• Exponential upper and lower bounds for the order of a regular language
• On the degree of non-regularity of context-free languages

zbMATH Keywords

computational complexitylower boundformal languagesTuring machine

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• One-tape, off-line Turing machine computations
• Some Results on Tape-Bounded Turing Machines

Cited In (17)

• A space lower bound for acceptance by one-way \(\Pi_2\)-alternating machines
• Algorithms for determining the smallest number of nonterminals (states) sufficient for generating (accepting) a regular language \(R \) with \(R_{1}\subseteq R\subseteq R_{2}\) for given regular languages \(R_{1},R_{2}\).
• Bridging across the \(\log(n)\) space frontier
• Non-regular Maximal Prefix-Free Subsets of Regular Languages
• Magic numbers in the state hierarchy of finite automata
• TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES
• Binary coded unary regular languages
• TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE
• Corrigendum to ``An optimal lower bound for nonregular languages
• Strong optimal lower bounds for Turing machines that accept nonregular languages
• Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines
• New results on the minimum amount of useful space
• Push complexity: optimal bounds and unary inputs
• On languages accepted with simultaneous complexity bounds and their ranking problem
• Hyper-minimizing minimized deterministic finite state automata
• The magic number problem for subregular language families
• Preface

This page was built for publication: An optimal lower bound for nonregular languages

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