On the word problem for syntactic monoids of piecewise testable languages. (Q444643): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 4 users not shown) | |||
Property / review text | |||
The word \(w\) is a \textit{subword} of \(u\) if \(w\) is a subsequence of not necessary consecutive variables taken from \(u\). Given a natural number \(k\) let \(u\sim_kv\) if and only if the words \(u,v\) over the alphabet \(X\) have the same set of subwords of length at most \(k\). A language \(L\) over the alphabet \(X\) is \textit{\(k\)-piecewise testable} if and only if \(L\) is the union of classes of the equivalence relation \(\sim_k\). \textit{I. Simon} [Lect. Notes Comput. Sci. 33, 214-222 (1975; Zbl 0316.68034)] found a basis of identities for the variety of finite monoids corresponding to a class of \(k\)-piecewise testable languages if \(k=1,2\). \textit{F. Blanchet-Sadri} gave a basis of identities for \(k=3\), and proved that there is no finite basis of identities for \(k>3\) [see Theor. Comput. Sci. 123, No. 2, 239-258 (1994; Zbl 0801.68105)]. In this paper a normal form is presented for the varieties of finite monoids corresponding to a class of \(k\)-piecewise testable languages for \(k=2,3\) and a log-asypmtotic estimate is given for the number of words over these monoids. | |||
Property / review text: The word \(w\) is a \textit{subword} of \(u\) if \(w\) is a subsequence of not necessary consecutive variables taken from \(u\). Given a natural number \(k\) let \(u\sim_kv\) if and only if the words \(u,v\) over the alphabet \(X\) have the same set of subwords of length at most \(k\). A language \(L\) over the alphabet \(X\) is \textit{\(k\)-piecewise testable} if and only if \(L\) is the union of classes of the equivalence relation \(\sim_k\). \textit{I. Simon} [Lect. Notes Comput. Sci. 33, 214-222 (1975; Zbl 0316.68034)] found a basis of identities for the variety of finite monoids corresponding to a class of \(k\)-piecewise testable languages if \(k=1,2\). \textit{F. Blanchet-Sadri} gave a basis of identities for \(k=3\), and proved that there is no finite basis of identities for \(k>3\) [see Theor. Comput. Sci. 123, No. 2, 239-258 (1994; Zbl 0801.68105)]. In this paper a normal form is presented for the varieties of finite monoids corresponding to a class of \(k\)-piecewise testable languages for \(k=2,3\) and a log-asypmtotic estimate is given for the number of words over these monoids. / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 20M35 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 20M07 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 20M05 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68Q45 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68Q70 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6066635 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
semigroups | |||
Property / zbMATH Keywords: semigroups / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
piecewise testable languages | |||
Property / zbMATH Keywords: piecewise testable languages / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
pseudovarieties of finite monoids | |||
Property / zbMATH Keywords: pseudovarieties of finite monoids / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
free syntactic monoids | |||
Property / zbMATH Keywords: free syntactic monoids / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
word problem | |||
Property / zbMATH Keywords: word problem / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
bases of identities | |||
Property / zbMATH Keywords: bases of identities / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
normal form theorems | |||
Property / zbMATH Keywords: normal form theorems / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s00233-011-9357-z / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2054241966 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Games, equations and the dot-depth hierarchy / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Equations and monoid varieties of dot-depth one and two / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3123631 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3769981 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Complexity of some problems from the theory of automata / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4077455 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 14:10, 5 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the word problem for syntactic monoids of piecewise testable languages. |
scientific article |
Statements
On the word problem for syntactic monoids of piecewise testable languages. (English)
0 references
16 August 2012
0 references
The word \(w\) is a \textit{subword} of \(u\) if \(w\) is a subsequence of not necessary consecutive variables taken from \(u\). Given a natural number \(k\) let \(u\sim_kv\) if and only if the words \(u,v\) over the alphabet \(X\) have the same set of subwords of length at most \(k\). A language \(L\) over the alphabet \(X\) is \textit{\(k\)-piecewise testable} if and only if \(L\) is the union of classes of the equivalence relation \(\sim_k\). \textit{I. Simon} [Lect. Notes Comput. Sci. 33, 214-222 (1975; Zbl 0316.68034)] found a basis of identities for the variety of finite monoids corresponding to a class of \(k\)-piecewise testable languages if \(k=1,2\). \textit{F. Blanchet-Sadri} gave a basis of identities for \(k=3\), and proved that there is no finite basis of identities for \(k>3\) [see Theor. Comput. Sci. 123, No. 2, 239-258 (1994; Zbl 0801.68105)]. In this paper a normal form is presented for the varieties of finite monoids corresponding to a class of \(k\)-piecewise testable languages for \(k=2,3\) and a log-asypmtotic estimate is given for the number of words over these monoids.
0 references
semigroups
0 references
piecewise testable languages
0 references
pseudovarieties of finite monoids
0 references
free syntactic monoids
0 references
word problem
0 references
bases of identities
0 references
normal form theorems
0 references