An optimal lower bound for nonregular languages
From MaRDI portal
(Redirected from Publication:1330656)
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
Cites work
- scientific article; zbMATH DE number 3657869 (Why is no real title available?)
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 3428547 (Why is no real title available?)
- scientific article; zbMATH DE number 3363526 (Why is no real title available?)
- One-tape, off-line Turing machine computations
- Some Results on Tape-Bounded Turing Machines
Cited in
(17)- Hyper-minimizing minimized deterministic finite state automata
- A space lower bound for acceptance by one-way \(\Pi_2\)-alternating machines
- Strong optimal lower bounds for Turing machines that accept nonregular languages
- Corrigendum to ``An optimal lower bound for nonregular languages
- Magic numbers in the state hierarchy of finite automata
- Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines
- TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES
- Non-regular Maximal Prefix-Free Subsets of Regular Languages
- 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}\).
- TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE
- Binary coded unary regular languages
- The magic number problem for subregular language families
- Bridging across the \(\log(n)\) space frontier
- New results on the minimum amount of useful space
- On languages accepted with simultaneous complexity bounds and their ranking problem
- Push complexity: optimal bounds and unary inputs
- 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)
