An Algebraic Characterization of Prefix-Strict Languages
Let <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msup><mi mathvariant="sans-serif">Σ</mi><mo>+</mo></msup></semantics></math></inline-formula> be the...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-09-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/10/19/3416 |
| _version_ | 1827654051272065024 |
|---|---|
| author | Jing Tian Yizhi Chen Hui Xu |
| author_facet | Jing Tian Yizhi Chen Hui Xu |
| author_sort | Jing Tian |
| collection | DOAJ |
| description | Let <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msup><mi mathvariant="sans-serif">Σ</mi><mo>+</mo></msup></semantics></math></inline-formula> be the set of all finite words over a finite alphabet <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi mathvariant="sans-serif">Σ</mi></semantics></math></inline-formula>. A word <i>u</i> is called a strict prefix of a word <i>v</i>, if <i>u</i> is a prefix of <i>v</i> and there is no other way to show that <i>u</i> is a subword of <i>v</i>. A language <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>L</mi><mo>⊆</mo><msup><mi mathvariant="sans-serif">Σ</mi><mo>+</mo></msup></mrow></semantics></math></inline-formula> is said to be prefix-strict, if for any <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>∈</mo><mi>L</mi></mrow></semantics></math></inline-formula>, <i>u</i> is a subword of <i>v</i> always implies that <i>u</i> is a strict prefix of <i>v</i>. Denote the class of all prefix-strict languages in <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msup><mi mathvariant="sans-serif">Σ</mi><mo>+</mo></msup></semantics></math></inline-formula> by <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="script">P</mi><mo>(</mo><msup><mi mathvariant="sans-serif">Σ</mi><mo>+</mo></msup><mo>)</mo></mrow></semantics></math></inline-formula>. This paper characterizes <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="script">P</mi><mo>(</mo><msup><mi mathvariant="sans-serif">Σ</mi><mo>+</mo></msup><mo>)</mo></mrow></semantics></math></inline-formula> as a universe of a model of the free object for the ai-semiring variety satisfying the additional identities <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>x</mi><mo>+</mo><mi>y</mi><mi>x</mi><mo>≈</mo><mi>x</mi></mrow></semantics></math></inline-formula> and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>x</mi><mo>+</mo><mi>y</mi><mi>x</mi><mi>z</mi><mo>≈</mo><mi>x</mi></mrow></semantics></math></inline-formula>. Furthermore, the analogous results for so-called suffix-strict languages and infix-strict languages are introduced. |
| first_indexed | 2024-03-09T21:29:06Z |
| format | Article |
| id | doaj.art-002b5ea64ee84458ac0894619090a149 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-09T21:29:06Z |
| publishDate | 2022-09-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-002b5ea64ee84458ac0894619090a1492023-11-23T21:01:08ZengMDPI AGMathematics2227-73902022-09-011019341610.3390/math10193416An Algebraic Characterization of Prefix-Strict LanguagesJing Tian0Yizhi Chen1Hui Xu2School of Economics and Finance, Xi’an International Studies University, Xi’an 710128, ChinaSchool of Mathematics and Statistics, Huizhou University, Huizhou 516007, ChinaSchool of Science, Air Force Engineering University, Xi’an 710051, ChinaLet <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msup><mi mathvariant="sans-serif">Σ</mi><mo>+</mo></msup></semantics></math></inline-formula> be the set of all finite words over a finite alphabet <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi mathvariant="sans-serif">Σ</mi></semantics></math></inline-formula>. A word <i>u</i> is called a strict prefix of a word <i>v</i>, if <i>u</i> is a prefix of <i>v</i> and there is no other way to show that <i>u</i> is a subword of <i>v</i>. A language <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>L</mi><mo>⊆</mo><msup><mi mathvariant="sans-serif">Σ</mi><mo>+</mo></msup></mrow></semantics></math></inline-formula> is said to be prefix-strict, if for any <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>∈</mo><mi>L</mi></mrow></semantics></math></inline-formula>, <i>u</i> is a subword of <i>v</i> always implies that <i>u</i> is a strict prefix of <i>v</i>. Denote the class of all prefix-strict languages in <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msup><mi mathvariant="sans-serif">Σ</mi><mo>+</mo></msup></semantics></math></inline-formula> by <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="script">P</mi><mo>(</mo><msup><mi mathvariant="sans-serif">Σ</mi><mo>+</mo></msup><mo>)</mo></mrow></semantics></math></inline-formula>. This paper characterizes <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="script">P</mi><mo>(</mo><msup><mi mathvariant="sans-serif">Σ</mi><mo>+</mo></msup><mo>)</mo></mrow></semantics></math></inline-formula> as a universe of a model of the free object for the ai-semiring variety satisfying the additional identities <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>x</mi><mo>+</mo><mi>y</mi><mi>x</mi><mo>≈</mo><mi>x</mi></mrow></semantics></math></inline-formula> and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>x</mi><mo>+</mo><mi>y</mi><mi>x</mi><mi>z</mi><mo>≈</mo><mi>x</mi></mrow></semantics></math></inline-formula>. Furthermore, the analogous results for so-called suffix-strict languages and infix-strict languages are introduced.https://www.mdpi.com/2227-7390/10/19/3416free algebraformal languagesembedding orderai-semirings variety |
| spellingShingle | Jing Tian Yizhi Chen Hui Xu An Algebraic Characterization of Prefix-Strict Languages Mathematics free algebra formal languages embedding order ai-semirings variety |
| title | An Algebraic Characterization of Prefix-Strict Languages |
| title_full | An Algebraic Characterization of Prefix-Strict Languages |
| title_fullStr | An Algebraic Characterization of Prefix-Strict Languages |
| title_full_unstemmed | An Algebraic Characterization of Prefix-Strict Languages |
| title_short | An Algebraic Characterization of Prefix-Strict Languages |
| title_sort | algebraic characterization of prefix strict languages |
| topic | free algebra formal languages embedding order ai-semirings variety |
| url | https://www.mdpi.com/2227-7390/10/19/3416 |
| work_keys_str_mv | AT jingtian analgebraiccharacterizationofprefixstrictlanguages AT yizhichen analgebraiccharacterizationofprefixstrictlanguages AT huixu analgebraiccharacterizationofprefixstrictlanguages AT jingtian algebraiccharacterizationofprefixstrictlanguages AT yizhichen algebraiccharacterizationofprefixstrictlanguages AT huixu algebraiccharacterizationofprefixstrictlanguages |