On the determinization blowup for finite automata recognizing equal-length languages

DOI10.1007/978-3-319-13350-8_6MaRDI QIDQ2944880zbMATH OpenOpenAlexFDO

Authors Juhani Karhumäki, Alexander Okhotin

Publication date 8 September 2015

Published in Computing with New Resources (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-13350-8_6

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Deterministic blow-ups of minimal NFA's
• Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs
• scientific article; zbMATH DE number 1156489
• Deterministic Blow-Ups of Minimal Nondeterministic Finite Automata over a Fixed Alphabet
• DETERMINISTIC BLOW-UPS OF MINIMAL NONDETERMINISTIC FINITE AUTOMATA OVER A FIXED ALPHABET

Cites work

• scientific article; zbMATH DE number 194082 (Why is no real title available?)
• scientific article; zbMATH DE number 1156489 (Why is no real title available?)
• scientific article; zbMATH DE number 2081039 (Why is no real title available?)
• scientific article; zbMATH DE number 2081052 (Why is no real title available?)
• scientific article; zbMATH DE number 3254905 (Why is no real title available?)
• Converting two-way nondeterministic unary automata into simpler automata.
• DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
• Finite Automata Computing Real Functions
• Finite automata and unary languages
• Finite automata, image manipulation, and automatic real functions
• Mathematical Foundations of Computer Science 2005
• On continuous functions computed by finite automata
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
• Rational and affine expressions for image description
• STATE COMPLEXITY OF UNION AND INTERSECTION OF FINITE LANGUAGES
• The complexity of compressing subsegments of images described by finite automata
• Unambiguous finite automata over a unary alphabet
• Weighted finite automata: Computing with different topologies
• \(\Delta \)-clearing restarting automata and CFL

Cited in

(5)

• Lengths of words accepted by nondeterministic finite automata
• Approximate NFA universality and related problems motivated by information theory
• Block languages and their bitmap representations
• Asymptotics of Minimal Deterministic Finite Automata Recognizing a Finite Binary Language
• VC-dimensions of nondeterministic finite automata for words of equal length

This page was built for publication: On the determinization blowup for finite automata recognizing equal-length languages

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