Upper Bounds on Syntactic Complexity of Left and Two-Sided Ideals

DOI10.1007/978-3-319-09698-8_2zbMath1425.68185arXiv1403.2090OpenAlexW2099109284MaRDI QIDQ2921971

Marek Szykuła, Janusz A. Brzozowski

Publication date: 14 October 2014

Published in: Developments in Language Theory (Search for Journal in Brave)

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

zbMATH Keywords

upper boundregular languagetransition semigroupleft idealsyntactic complexityfactor-closedsuffix-closedtwo-sided ideal

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Related Items

Syntactic complexity of bifix-free languages ⋮ Complexity of suffix-free regular languages ⋮ Complexity of Left-Ideal, Suffix-Closed and Suffix-Free Regular Languages ⋮ Syntactic complexity of regular ideals ⋮ Syntactic complexity of bifix-free regular languages ⋮ Descriptional complexity of regular languages ⋮ Upper Bound on Syntactic Complexity of Suffix-Free Languages