State complexity of basic operations on nondeterministic finite automata

DOI10.1007/3-540-44977-9_14MaRDI QIDQ4418610zbMATH OpenFDO

Authors Markus Holzer, Martin Kutrib

Publication date 11 August 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2608/26080148.htm, http://geb.uni-giessen.de/geb/volltexte/2003/1203/

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• NFA-to-DFA trade-off for regular operations
• scientific article; zbMATH DE number 2081044
• State complexity of some operations on binary regular languages
• On the State Complexity of Complements, Stars, and Reversals of Regular Languages
• Nondeterministic State Complexity of Basic Operations for Prefix-Free Regular Languages

Cited in

(31)

• On NFAs where all states are final, initial, or both
• State complexity of reversals of deterministic finite automata with output
• On the descriptional complexity of finite automata with modified acceptance conditions
• State complexity of some operations on binary regular languages
• Finite transducers and nondeterministic state complexity of regular languages
• Operational complexity and right linear grammars
• Operational complexity and pumping lemmas
• NFA-to-DFA trade-off for regular operations
• Nondeterministic state complexity of nested word automata
• Operational state complexity of nested word automata
• State complexity of combined operations
• On the average state and transition complexity of finite languages
• State complexity of catenation combined with union and intersection
• Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
• Descriptional and Computational Complexity of Finite Automata
• State complexity of star of union and square of union on \textit{k} regular languages
• State complexity of union and intersection of star on \(k\) regular languages
• State complexity of combined operations with two basic operations
• Incomplete operational transition complexity of regular languages
• State complexity of four combined operations composed of union, intersection, star and reversal
• State complexity of unary language operations for NFAs with limited nondeterminism
• The state complexity of permutations on finite languages over binary alphabets
• Further Remarks on the Operational Nonterminal Complexity
• The nondeterministic state complexity of the site-directed deletion language operation
• Algorithms for checking intersection non-emptiness of regular expressions
• On complementation of nondeterministic finite automata without full determinization
• Operational state complexity of block languages
• Incremental algorithms for solving regular expression intersection non-emptiness
• State complexity of union and intersection of square and reversal on \(k\) regular languages
• On the complexity of multi-entry DFAs
• Operational state complexity of unary NFAs with finite nondeterminism

This page was built for publication: State complexity of basic operations on nondeterministic finite automata

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