Most complex non-returning regular languages

DOI10.1142/S0129054119400239zbMATH Open1427.68139OpenAlexW2973337972WikidataQ127227328 ScholiaQ127227328MaRDI QIDQ5205037FDOQ5205037

Authors: Sylvie Davies, Janusz Brzozowski 

Publication date: 10 December 2019

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

Full work available at URL: https://doi.org/10.1142/s0129054119400239

Recommendations

• Most complex non-returning regular languages
• State complexity of basic operations on non-returning regular languages
• State complexity of basic operations on non-returning regular languages
• In Search of Most Complex Regular Languages
• State complexity of some operations on binary regular languages

zbMATH Keywords

regular languagestaratomconcatenationtransition semigroupstate complexityreversalBoolean operationsyntactic semigroupdifferent alphabetsmost complexunrestricted complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Semigroups in automata theory, linguistics, etc. (20M35)

Cites Work

• Title not available (Why is that?)
• The state complexities of some basic operations on regular languages
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
• Title not available (Why is that?)
• Theory of átomata
• Complexity of atoms, combinatorially
• Quotient complexities of atoms in regular ideal languages
• Reversal of binary regular languages
• Complexity of suffix-free regular languages
• Complexity of right-ideal, prefix-closed, and prefix-free regular languages
• Implementation and Application of Automata
• On deterministic finite automata and syntactic monoid size
• In search of most complex regular languages
• Syntactic complexity of regular ideals
• On the State Complexity of the Shuffle of Regular Languages
• A new technique for reachability of states in concatenation automata
• State complexity of basic operations on non-returning regular languages
• Complexity of atoms of regular languages
• Unrestricted state complexity of binary operations on regular languages
• Most complex regular ideal languages
• Title not available (Why is that?)
• Symmetric groups and quotient complexity of Boolean operations
• Complexity of left-ideal, suffix-closed and suffix-free regular languages

Cited In (5)

• In Search of Most Complex Regular Languages
• State complexity of basic operations on non-returning regular languages
• State complexity of basic operations on non-returning regular languages
• Most Complex Regular Right-Ideal Languages
• Most complex non-returning regular languages

This page was built for publication: Most complex non-returning regular languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5205037)