STATE COMPLEXITY OF UNION AND INTERSECTION OF FINITE LANGUAGES

DOI10.1142/S0129054108005838zbMath1155.68037MaRDI QIDQ3538851

Kai Salomaa, Yo-Sub Han

Publication date: 24 November 2008

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

finite-state automata

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

State Complexity of k-Union and k-Intersection for Prefix-Free Regular Languages, Operational State Complexity of Subtree-Free Regular Tree Languages, The State Complexity of Permutations on Finite Languages over Binary Alphabets, State complexity of finite partial languages, State complexity of combined operations for suffix-free regular languages, Incomplete operational transition complexity of regular languages, State complexity of basic operations on suffix-free regular languages, Descriptional complexity of regular languages, State complexity of finite partial languages, Complexity of suffix-free regular languages, On the Determinization Blowup for Finite Automata Recognizing Equal-Length Languages, State Complexity of Insertion, State Complexity of Boundary of Prefix-Free Regular Languages, State Complexity of Combined Operations for Prefix-Free Regular Languages

Uses Software

• Vaucanson

Cites Work

• Unnamed Item
• The state complexities of some basic operations on regular languages
• \textit{Grail}: A C++ library for automata and expressions
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
• STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• IMPROVED BOUNDS ON THE NUMBER OF AUTOMATA ACCEPTING FINITE LANGUAGES