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

Formal languages and automata (68Q45)

Related Items (14)

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

This page was built for publication: STATE COMPLEXITY OF UNION AND INTERSECTION OF FINITE LANGUAGES