Syntactic complexity of regular ideals

DOI10.1007/S00224-017-9803-8MaRDI QIDQ722210zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Janusz Brzozowski, Marek Szykuła, Yuli Ye

Publication date 23 July 2018

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

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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

Cites work

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

Cited in

(9)

• Syntactic complexity of \({\mathcal R}\)- and \({\mathcal J}\)-trivial regular languages
• Syntactic complexity of ideal and closed languages
• scientific article; zbMATH DE number 3862471 (Why is no real title available?)
• Operational complexity: NFA-to-DFA trade-off
• Most complex regular ideal languages
• Most complex non-returning regular languages
• Complexity of left-ideal, suffix-closed and suffix-free regular languages
• Upper bounds on syntactic complexity of left and two-sided ideals
• Syntactic complexity of \(\mathcal{R}\)- and \(\mathcal{J}\)-trivial regular 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)