Complexity of Suffix-Free Regular Languages

DOI10.1007/978-3-319-22177-9_12zbMath1434.68239OpenAlexW2951330448MaRDI QIDQ2947876

Marek Szykuła, Janusz A. Brzozowski

Publication date: 29 September 2015

Published in: Fundamentals of Computation Theory (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10012/12497

zbMATH Keywords

regular languagetransition semigroupstate complexitysuffix-freesyntactic complexitymost complex

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (6)

Complexity of suffix-free regular languages ⋮ Complexity of Suffix-Free Regular Languages ⋮ Complexity of Left-Ideal, Suffix-Closed and Suffix-Free Regular Languages ⋮ Complexity of atoms, combinatorially ⋮ Complexity of bifix-free regular languages ⋮ Complexity of bifix-free regular languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages
• State complexity of basic operations on suffix-free regular languages
• Succinct representation of regular languages by Boolean automata
• The state complexities of some basic operations on regular languages
• Theory of átomata
• Quotient Complexities of Atoms in Regular Ideal Languages
• Complexity of Suffix-Free Regular Languages
• Syntactic Complexity of Ideal and Closed Languages
• Quotient Complexity of Bifix-, Factor-, and Subword-free Regular Language
• IN SEARCH OF MOST COMPLEX REGULAR LANGUAGES
• Most Complex Regular Right-Ideal Languages
• Upper Bound on Syntactic Complexity of Suffix-Free Languages

This page was built for publication: Complexity of Suffix-Free Regular Languages