Syntactic complexity of regular ideals
From MaRDI portal
Publication:722210
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
upper boundregular languagetransition semigroupleft idealright idealsyntactic complexityfactor-closedprefix-closedsuffix-closedtwo-sided ideal
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