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

DOI10.14232/ACTACYB.23.1.2017.3zbMATH Open1389.68040arXiv1605.06697OpenAlexW2610921159MaRDI QIDQ5350145FDOQ5350145

Authors: Corwin W. Sinnamon, Janusz Brzozowski 

Publication date: 25 August 2017

Published in: Acta Cybernetica (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cited In (13)

• Title not available (Why is that?)
• Complexity of proper prefix-convex regular languages
• Complexity in convex languages
• Most complex non-returning regular languages
• Kleene Closure on Regular and Prefix-Free Languages
• Title not available (Why is that?)
• 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)