Syntactic complexity of regular ideals

DOI10.1007/S00224-017-9803-8zbMATH Open1398.68301DBLPjournals/mst/BrzozowskiSY18arXiv1509.06032OpenAlexW2962904359WikidataQ59523060 ScholiaQ59523060MaRDI QIDQ722210FDOQ722210

Authors: Janusz Brzozowski, Marek Szykuła, Yuli Ye 

Publication date: 23 July 2018

Published in: Theory of Computing Systems (Search for Journal in Brave)

Abstract: The state complexity of a regular language is the number of states in a minimal deterministic finite automaton accepting the language. The syntactic complexity of a regular language is the cardinality of its syntactic semigroup. The syntactic complexity of a subclass of regular languages is the worst-case syntactic complexity taken as a function of the state complexity $n$ of languages in that class. We prove that $n^{n-1}$, $n^{n-1}+n-1$, and $n^{n-2}+(n-2)2^{n-2}+1$ are tight upper bounds on the syntactic complexities of right ideals and prefix-closed languages, left ideals and suffix-closed languages, and two-sided ideals and factor-closed languages, respectively. Moreover, we show that the transition semigroups meeting the upper bounds for all three types of ideals are unique, and the numbers of generators (4, 5, and 6, respectively) cannot be reduced.

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

Recommendations

• Syntactic complexity of ideal and closed languages
• Upper bounds on syntactic complexity of left and two-sided ideals
• Syntactic complexity of prefix-, suffix-, and bifix-free regular languages
• Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages
• Syntactic complexity of \({\mathcal R}\)- and \({\mathcal J}\)-trivial regular languages

zbMATH Keywords

regular languageupper boundleft idealright idealtransition semigroupsyntactic complexityfactor-closedprefix-closedsuffix-closedtwo-sided ideal

Mathematics Subject Classification ID

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

Cites Work

• State complexity of regular languages
• Title not available (Why is that?)
• Title not available (Why is that?)
• Theory of átomata
• Operational state complexity of prefix-free regular languages
• State complexity of basic operations on suffix-free regular languages
• Title not available (Why is that?)
• Quotient complexity of closed languages
• Syntactic complexity of bifix-free languages
• Quotient complexity of regular languages
• Linear Automaton Transformations
• Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages
• Syntactic complexities of six classes of star-free languages
• Syntactic complexity of ideal and closed languages
• On deterministic finite automata and syntactic monoid size
• Title not available (Why is that?)
• Languages convex with respect to binary relations, and their closure properties
• Ultimate-Definite and Symmetric-Definite Events and Automata
• Decision problems for convex languages
• STATE COMPLEXITY AND THE MONOID OF TRANSFORMATIONS OF A FINITE SET
• Quotient complexity of ideal languages
• Upper bounds on syntactic complexity of left and two-sided ideals
• In search of most complex regular languages
• Upper bound on syntactic complexity of suffix-free languages
• Large aperiodic semigroups
• Sur les bases du groupe symétrique et du groupe alternant

Cited In (9)

• Most complex non-returning regular languages
• Operational complexity: NFA-to-DFA trade-off
• Syntactic complexity of \({\mathcal R}\)- and \({\mathcal J}\)-trivial regular languages
• Upper bounds on syntactic complexity of left and two-sided ideals
• Complexity of left-ideal, suffix-closed and suffix-free regular languages
• Syntactic complexity of ideal and closed languages
• Syntactic complexity of \(\mathcal{R}\)- and \(\mathcal{J}\)-trivial regular languages
• Title not available (Why is that?)
• Most complex regular ideal languages

This page was built for publication: Syntactic complexity of regular ideals

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