Complexity of right-ideal, prefix-closed, and prefix-free regular languages

DOI10.14232/ACTACYB.23.1.2017.3MaRDI QIDQ5350145zbMATH OpenOpenAlexFDO

Authors Corwin W. Sinnamon, Janusz Brzozowski

Publication date 25 August 2017

Published in Acta Cybernetica (Search for Journal in Brave)

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

zbMATH Keywords

regular languagesatomsright idealsstate complexityprefix-freesyntactic semigroupprefix-closedquotient complexitycomplexity of operationsprefix-convexunrestricted alphabets

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: A language $L$ over an alphabet $Sigma$ is prefix-convex if, for any words $x,y,zinSigm{a}^{\ast }$, whenever $x$ and $xyz$ are in $L$, then so is $xy$. Prefix-convex languages include right-ideal, prefix-closed, and prefix-free languages. We study complexity properties of prefix-convex regular languages. In particular, we find the quotient/state complexity of boolean operations, product (concatenation), star, and reversal, the size of the syntactic semigroup, and the quotient complexity of atoms. For binary operations we use arguments with different alphabets when appropriate; this leads to higher tight upper bounds than those obtained with equal alphabets. We exhibit most complex prefix-convex languages that meet the complexity bounds for all the measures listed above.

Recommendations

• Complexity of proper prefix-convex regular languages
• Complexity of proper prefix-convex regular languages
• Complexity of left-ideal, suffix-closed and suffix-free regular languages
• Complexity in convex languages
• Power, positive closure, and quotients on convex languages

Cited in

(13)

• scientific article; zbMATH DE number 4078833 (Why is no real title available?)
• Complexity in convex languages
• Complexity of proper prefix-convex regular languages
• Most complex non-returning regular languages
• Kleene Closure on Regular and Prefix-Free Languages
• scientific article; zbMATH DE number 7315105 (Why is no real title available?)
• Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages
• Power, positive closure, and quotients on convex languages
• Languages convex with respect to binary relations, and their closure properties
• Complexity of left-ideal, suffix-closed and suffix-free regular languages
• Complexity of proper prefix-convex regular languages
• Most Complex Regular Right-Ideal Languages
• Complexity of suffix-free regular languages

This page was built for publication: Complexity of right-ideal, prefix-closed, and prefix-free regular languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5350145)