Syntactic complexity of regular ideals

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

Janusz Brzozowski, Yuli Ye, Marek Szykuła

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
• Title not available (Why is that?)
• Syntactic Complexity of Ideal and Closed Languages
• On deterministic finite automata and syntactic monoid size
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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 (4)

• Complexity of Left-Ideal, Suffix-Closed and Suffix-Free Regular Languages
• Operational complexity: NFA-to-DFA trade-off
• Most Complex Non-Returning Regular Languages
• Title not available (Why is that?)

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)