On nonstochastic languages and homomorphic images of stochastic languages

DOI10.1016/0020-0255(81)90033-5zbMath0483.68069OpenAlexW2056590739WikidataQ122981488 ScholiaQ122981488MaRDI QIDQ1163382

Paavo Turakainen

Publication date: 1981

Published in: Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0255(81)90033-5

zbMATH Keywords

recursively enumerable setsbounded languages regarded as graphs of recursive functionsclosure of classes of stochastic languages under homomorphismslanguages recognized by stochastic automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Recursive functions and relations, subrecursive hierarchies (03D20) Recursively (computably) enumerable sets and degrees (03D25)

Related Items (5)

Affine automata verifiers ⋮ Computational limitations of affine automata and generalized affine automata ⋮ A new family of nonstochastic languages ⋮ On the Computational Power of Affine Automata ⋮ Debates with Small Transparent Quantum Verifiers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• One counter languages and the IRS condition
• On some bounded semiAFLs and AFLs
• Langages à un compteur
• On complements of some bounded context-sensitive languages
• Some remarks on multistochastic automata
• On homomorphic images of rational stochastic languages
• Word-functions of stochastic and pseudo stochastic automata
• Linear Languages and the Intersection Closures of Classes of Languages
• Elementary bounded languages
• Generalized Automata and Stochastic Languages
• Studies in abstract families of languages
• On stochastic languages
• Some closure properties of the family of stochastic languages
• On the Languages Representable by Finite Probabilistic Automata
• On Languages Accepted in Polynomial Time
• On multistochastic automata

This page was built for publication: On nonstochastic languages and homomorphic images of stochastic languages