Quotient complexity of closed languages

DOI10.1007/s00224-013-9515-7zbMath1380.68249arXiv0912.1034OpenAlexW1533036729MaRDI QIDQ1678754

Chenglong Zou, Galina Jirásková, Janusz A. Brzozowski

Publication date: 7 November 2017

Published in: Theory of Computing Systems, Computer Science – Theory and Applications (Search for Journal in Brave)

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

zbMATH Keywords

upper boundlanguageregular languagefinite automatonfactorprefixstate complexityquotientautomatonsubwordclosedclosed languagesuffixquotient complexityregular operation

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Operations on Permutation Automata, The cut operation in subclasses of convex languages (extended abstract), Nondeterministic complexity of operations on free and convex languages, The cut operation in subclasses of convex languages, Merging two hierarchies of external contextual grammars with subregular selection, Relations of contextual grammars with strictly locally testable selection languages, Operational complexity in subregular classes, Strictly Locally Testable and Resources Restricted Control Languages in Tree-Controlled Grammars, Nondeterministic state complexity of star-free languages, Reversal of binary regular languages, Unnamed Item, Complexity of Left-Ideal, Suffix-Closed and Suffix-Free Regular Languages, Syntactic complexity of regular ideals, Power, positive closure, and quotients on convex languages, Nondeterministic State Complexity of Star-Free Languages, Note on Reversal of Binary Regular Languages, Kuratowski Algebras Generated by Prefix-, Suffix-, Factor-, and Subword-Free Languages Under Star and Complementation, State Complexity of Suffix Distance, Complexity of proper prefix-convex regular languages, Complexity of proper prefix-convex regular languages, Nondeterministic Complexity of Operations on Closed and Ideal Languages, Nondeterministic complexity in subclasses of convex languages, Descriptional complexity of regular languages, Square on Ideal, Closed and Free Languages, Closure properties of subregular languages under operations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Decision problems for convex languages
• State complexity of basic operations on suffix-free regular languages
• On NFAs where all states are final, initial, or both
• A note on multiple-entry finite automata
• Some remarks on multiple-entry finite automata
• The state complexities of some basic operations on regular languages
• Multiple-entry finite automata
• Quotient complexity of ideal languages
• Predictable semiautomata
• The size of Higman-Haines sets
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
• CLOSURES IN FORMAL LANGUAGES AND KURATOWSKI'S THEOREM
• Complexity of Operations on Cofinite Languages
• Complexity in Convex Languages
• A UNIQUE DECOMPOSITION THEOREM FOR FACTORIAL LANGUAGES
• On the State Complexity of Scattered Substrings and Superstrings
• STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
• On free monoids partially ordered by embedding
• Derivatives of Regular Expressions
• More on the Size of Higman-Haines Sets: Effective Constructions