STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION

DOI10.1142/S0129054105003133zbMath1097.68062MaRDI QIDQ5462121

No author found.

Publication date: 1 August 2005

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

zbMATH Keywords

Regular languagesState complexityNondeterministic state complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (42)

A Study of a Simple Class of Modifiers: Product Modifiers ⋮ State Complexity of Catenation Combined with a Boolean Operation: A Unified Approach ⋮ Operational State Complexity of Subtree-Free Regular Tree Languages ⋮ State Complexity of Boundary of Prefix-Free Regular Languages ⋮ COMPLEXITY IN UNION-FREE REGULAR LANGUAGES ⋮ STATE COMPLEXITY OF TWO COMBINED OPERATIONS: CATENATION-STAR AND CATENATION-REVERSAL ⋮ State complexity of combined operations ⋮ Complementing two-way finite automata ⋮ Quotient complexity of closed languages ⋮ State complexity of star of union and square of union on \textit{k} regular languages ⋮ State complexity of combined operations for suffix-free regular languages ⋮ STATE COMPLEXITY OF TWO COMBINED OPERATIONS: CATENATION-UNION AND CATENATION-INTERSECTION ⋮ ON THE STATE COMPLEXITY OF COMBINED OPERATIONS AND THEIR ESTIMATION ⋮ Nondeterministic operational complexity in subregular languages ⋮ State complexity of union and intersection of star on \(k\) regular languages ⋮ Operational state complexity revisited: the contribution of monsters and modifiers ⋮ Concatenation of regular languages and descriptional complexity ⋮ State complexity of combined operations with two basic operations ⋮ Unnamed Item ⋮ On the State Complexity of Complements, Stars, and Reversals of Regular Languages ⋮ STATE COMPLEXITY OF UNION AND INTERSECTION OF FINITE LANGUAGES ⋮ THE RANGES OF STATE COMPLEXITIES FOR COMPLEMENT, STAR, AND REVERSAL OF REGULAR LANGUAGES ⋮ Estimation of state complexity of combined operations ⋮ State complexity of union and intersection of square and reversal on \(k\) regular languages ⋮ Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity ⋮ State Complexity of Four Combined Operations Composed of Union, Intersection, Star and Reversal ⋮ State complexity of deletion and bipolar deletion ⋮ State Complexity of Catenation Combined with Union and Intersection ⋮ MAGIC NUMBERS AND TERNARY ALPHABET ⋮ State complexity of power ⋮ The complexity of concatenation on deterministic and alternating finite automata ⋮ Magic Numbers and Ternary Alphabet ⋮ Concatenation of Regular Languages and Descriptional Complexity ⋮ NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY ⋮ Unnamed Item ⋮ The Complexity of Languages Resulting from the Concatenation Operation ⋮ Descriptional complexity of regular languages ⋮ State complexity of combined operations involving catenation and binary Boolean operations: beyond the Brzozowski conjectures ⋮ State complexity of unambiguous operations on finite automata ⋮ Undecidability of state complexity ⋮ State Complexity of k-Union and k-Intersection for Prefix-Free Regular Languages ⋮ Combination of roots and Boolean operations: an application to state complexity

Cites Work

• Unnamed Item
• A lower bound technique for the size of nondeterministic finite automata
• Partial orders on words, minimal elements of regular languages, and state complexity
• Finite automata and unary languages
• Succinct representation of regular languages by Boolean automata
• Intersection and union of regular languages and state complexity
• The state complexities of some basic operations on regular languages
• State complexity of some operations on binary regular languages
• Communication complexity method for measuring nondeterminism in finite automata
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES

This page was built for publication: STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION