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

      0 references
      0 references
      0 references
      18 May 1993
      0 references
      rational language
      0 references
      one-letter stochastic automata
      0 references
      stochastic languages
      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

      Identifiers