State complexity of basic operations on suffix-free regular languages

DOI10.1016/J.TCS.2008.12.054zbMath1172.68033OpenAlexW2109036808MaRDI QIDQ1029324

Yo-Sub Han, Kai Salomaa

Publication date: 10 July 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.12.054

zbMATH Keywords

state complexitysuffix-free regular languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (32)

Operations on Permutation Automata ⋮ Networks of evolutionary processors: the power of subregular filters ⋮ 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 CODE OPERATORS ⋮ THE MAGIC NUMBER PROBLEM FOR SUBREGULAR LANGUAGE FAMILIES ⋮ The cut operation in subclasses of convex languages (extended abstract) ⋮ Complexity of suffix-free regular languages ⋮ Quotient complexity of closed languages ⋮ State complexity of combined operations for suffix-free regular languages ⋮ Complexity of Suffix-Free Regular Languages ⋮ STATE COMPLEXITY OF TWO COMBINED OPERATIONS: CATENATION-UNION AND CATENATION-INTERSECTION ⋮ The cut operation in subclasses of convex languages ⋮ Operational complexity in subregular classes ⋮ State Complexity of Insertion ⋮ Syntactic complexity of suffix-free languages ⋮ Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages ⋮ On external contextual grammars with subregular selection languages ⋮ QUOTIENT COMPLEXITY OF STAR-FREE LANGUAGES ⋮ Complexity of Left-Ideal, Suffix-Closed and Suffix-Free Regular Languages ⋮ Syntactic complexity of regular ideals ⋮ Power, positive closure, and quotients on convex languages ⋮ Syntactic Complexity of Prefix-, Suffix-, and Bifix-Free Regular Languages ⋮ State complexity of deletion and bipolar deletion ⋮ Kuratowski Algebras Generated by Prefix-, Suffix-, Factor-, and Subword-Free Languages Under Star and Complementation ⋮ State Complexity of Catenation Combined with Union and Intersection ⋮ Descriptional complexity of regular languages ⋮ Upper Bound on Syntactic Complexity of Suffix-Free Languages ⋮ State complexity of unambiguous operations on finite automata ⋮ State Complexity of k-Union and k-Intersection for Prefix-Free Regular Languages ⋮ Closure properties of subregular languages under operations

Cites Work

• On the state complexity of reversals of regular languages
• Succinct representation of regular languages by Boolean automata
• The state complexities of some basic operations on regular languages
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
• STATE COMPLEXITY OF UNION AND INTERSECTION OF FINITE LANGUAGES
• A Survey of Regular Expressions and Their Applications
• THE GENERALIZATION OF GENERALIZED AUTOMATA: EXPRESSION AUTOMATA
• Implementation and Application of Automata
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: State complexity of basic operations on suffix-free regular languages