Stochastic automata and length distributions of rational languages (Q4035239)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 176138
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Stochastic automata and length distributions of rational languages |
scientific article; zbMATH DE number 176138 |
Statements
18 May 1993
0 references
rational language
0 references
one-letter stochastic automata
0 references
stochastic languages
0 references
0.7834032773971558
0 references
0.7789997458457947
0 references
0.7607259750366211
0 references
Stochastic automata and length distributions of rational languages (English)
0 references
[For the entire collection see Zbl 0753.00030.] \textit{D. Niwinski} [in ``Logics and recognizable sets'', Report on the Workshop ESPRIT-ASMICS N\(^{\circ}\) 3166, Dersau, Germany, 24 (1990)] raised to two following questions: \((Q1)\) Does the set \(\{n\in N\mid | L\cap \{a,b\}^ n| >2^{n- 1}\}\) belong to \(Rat(N)\)? \((Q2)\) Does the set \(\{w\in \{a,b\}^*\mid | w^{-1}L\cap \{a,b\}^{p(| w|)}| >2^{p(| w|)-1}\}\) belong to Rat\((\{a,b\}^*)\)? We will see here that the two questions (Q1) and (Q2) are related, that their answers are positive for ``almost'' every rational language, but that counterexamples to both assertions can be found. Moreover it appears that question (Q1) is related to the theory of one-letter stochastic automata that was developed by \textit{P. Turakainen} [On probabilistic automata and their generalizations, Ann. Acad. Scient. Fennicae, Series A, 429, 7-53, Helsinki (1969)]. We give a new and more concise presentation of Turakainen's results concerning this class of stochastic languages. We then address the two questions of Niwinski. With any rational language \(L\), we associate a stochastic automaton that computes the length frequencies of \(L\). Then, applying Turakainen's results, we obtain general classes of rational languages for which question (Q1) has a positive answer. Finally we show how to reduce question (Q2) to the first one.
0 references