Descriptional Complexity of Nondeterministic Finite Automata

DOI10.1007/978-3-540-73208-2_6MaRDI QIDQ5428217zbMATH OpenOpenAlexFDO

Authors Kai Salomaa

Publication date 28 November 2007

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-73208-2_6

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cited in

(13)

• Finite transducers and nondeterministic state complexity of regular languages
• Nondeterministic state complexity of nested word automata
• On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's
• On the descriptional complexity of Watson-Crick automata
• Descriptional Complexity of Operations on Alternating and Boolean Automata
• NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
• On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
• THE LENGTH OF SUBSET REACHABILITY IN NONDETERMINISTIC AUTOMATA
• scientific article; zbMATH DE number 3982519 (Why is no real title available?)
• The tractability frontier for NFA minimization
• Incomplete operational transition complexity of regular languages
• scientific article; zbMATH DE number 7444008 (Why is no real title available?)
• Descriptional and computational complexity of finite automata -- a survey

This page was built for publication: Descriptional Complexity of Nondeterministic Finite Automata

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