Lower bounds for the transition complexity of NFAs
type: Item
instance of: scholarly article
title: Lower bounds for the transition complexity of NFAs
zbMATH Open document ID: 1152.68028
author: Michael Domaratzki
author: Kai Salomaa
published in: Journal of Computer and System Sciences
publication date: 2008-11-19T00:00:00Z
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 5369041
zbMATH Keywords: regular languages
zbMATH Keywords: descriptional complexity
zbMATH Keywords: nondeterministic finite automata
zbMATH Keywords: finite projective planes
MaRDI profile type: Publication
full work available at URL: j.jcss.2008.02.007
OpenAlex ID: W2091741450
cites work: Q3996173
cites work: Q4313087
cites work: Transition complexity of language operations
cites work: Lower Bounds for the Transition Complexity of NFAs
cites work: A lower bound technique for the size of nondeterministic finite automata
cites work: Q5422234
cites work: Minimizing nfa's and regular expressions
cites work: Finding Lower Bounds for Nondeterministic State Complexity Is Hard
cites work: On the average state and transition complexity of finite languages
cites work: Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
cites work: Computingϵ-Free NFA from Regular Expressions inO(nlog2(n)) Time
cites work: Q4412108
cites work: NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
cites work: Q4337605
cites work: Q4465337
cites work: Comparing the size of NFAs with and without \(\epsilon\)-transitions
cites work: Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata
cites work: Minimal NFA Problems are Hard
cites work: Q4255576
cites work: Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
cites work: A lower bound on the size of \(\varepsilon\)-free NFA corresponding to a regular expression
cites work: Minimizing finite automata is computationally hard
cites work: Regular Expressions and NFAs Without ε-Transitions
cites work: Q4002255
cites work: Q4714446
cites work: State complexity of regular languages
cites work: Q3152811
DOI: 10.1016/J.JCSS.2008.02.007
description: scientific article; zbMATH DE number 5369041