The magic number problem for subregular language families
type: Item
instance of: scholarly article
zbMATH Open document ID: 1280.68109
DOI: 10.1142/S0129054112400084
author: Markus Holzer
author: Sebastian Jakobi
author: Martin Kutrib
published in: International Journal of Foundations of Computer Science
publication date: 2012-08-30T00:00:00Z
full work available at URL: https://arxiv.org/abs/1008.1653
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 6073935
zbMATH Keywords: descriptional complexity
zbMATH Keywords: finite automata
zbMATH Keywords: magic numbers
zbMATH Keywords: subregular languages
MaRDI profile type: Publication
arXiv ID: 1008.1653
cites work: Intersection and union of regular languages and state complexity
cites work: Determination of finite automata accepting subregular languages
cites work: Roots of Star Events
cites work: Magic numbers in the state hierarchy of finite automata
cites work: A lower bound technique for the size of nondeterministic finite automata
cites work: State complexity of basic operations on suffix-free regular languages
cites work: NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
cites work: Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs
cites work: A family of NFAs which need 2\(^{n}-\alpha\) deterministic states
cites work: DETERMINISTIC BLOW-UPS OF MINIMAL NONDETERMINISTIC FINITE AUTOMATA OVER A FIXED ALPHABET
cites work: Deterministic blow-ups of minimal NFA's
cites work: MAGIC NUMBERS AND TERNARY ALPHABET
cites work: On NFAs where all states are final, initial, or both
cites work: Power-separating regular languages
OpenAlex ID: W2963305382
Recommended article: Q4964015
Recommended article: Structure and Complexity of Some Subregular Language Families
Recommended article: The equivalence problem for finite substitutions in a regular language
Recommended article: Q3777480
Recommended article: An optimal lower bound for nonregular languages
Recommended article: Q3687733
Recommended article: Counting subwords and regular languages
Recommended article: The Membership Problem for Linear and Regular Permutation Languages
Recommended article: The inclusion problem for some subclasses of context-free languages
Recommended article: Q4382098
title: The magic number problem for subregular language families
description: scientific article; zbMATH DE number 6073935