Syntactic complexity of regular ideals

DOI10.1007/s00224-017-9803-8zbMath1398.68301arXiv1509.06032OpenAlexW2962904359WikidataQ59523060 ScholiaQ59523060MaRDI QIDQ722210

Janusz A. Brzozowski, Yuli Ye, Marek Szykuła

Publication date: 23 July 2018

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

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

zbMATH Keywords

upper boundregular languagetransition semigroupleft idealright idealsyntactic 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)

Related Items

Operational complexity: NFA-to-DFA trade-off, Complexity of Left-Ideal, Suffix-Closed and Suffix-Free Regular Languages, Most Complex Non-Returning Regular Languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages
• Decision problems for convex languages
• On deterministic finite automata and syntactic monoid size
• State complexity of basic operations on suffix-free regular languages
• Quotient complexity of closed languages
• Quotient complexity of ideal languages
• Syntactic complexity of bifix-free languages
• Theory of átomata
• Upper Bounds on Syntactic Complexity of Left and Two-Sided Ideals
• Linear Automaton Transformations
• Syntactic Complexity of Ideal and Closed Languages
• Ultimate-Definite and Symmetric-Definite Events and Automata
• IN SEARCH OF MOST COMPLEX REGULAR LANGUAGES
• STATE COMPLEXITY AND THE MONOID OF TRANSFORMATIONS OF A FINITE SET
• Upper Bound on Syntactic Complexity of Suffix-Free Languages
• Large Aperiodic Semigroups
• Sur les bases du groupe symétrique et du groupe alternant