Unrestricted State Complexity of Binary Operations on Regular Languages

DOI10.1007/978-3-319-41114-9_5zbMath1476.68126arXiv1602.01387OpenAlexW2430843852MaRDI QIDQ2829970

Janusz A. Brzozowski

Publication date: 9 November 2016

Published in: Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1602.01387

zbMATH Keywords

streamproductregular languagestate complexityconcatenationBoolean operationdifferent alphabetsquotient complexityunrestricted complexitymost complex languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (4)

Complexity of suffix-free regular languages ⋮ Complexity of Left-Ideal, Suffix-Closed and Suffix-Free Regular Languages ⋮ Most Complex Non-Returning Regular Languages ⋮ Primitivity, uniform minimality, and state complexity of Boolean operations

Cites Work

• Unnamed Item
• Unnamed Item
• Incomplete operational transition complexity of regular languages
• The state complexities of some basic operations on regular languages
• Theory of átomata
• Transition Complexity of Incomplete DFAs
• Symmetric Groups and Quotient Complexity of Boolean Operations
• IN SEARCH OF MOST COMPLEX REGULAR LANGUAGES
• COMPLEXITY OF ATOMS OF REGULAR LANGUAGES
• Complexity of atoms, combinatorially

This page was built for publication: Unrestricted State Complexity of Binary Operations on Regular Languages