On nonstochastic languages and homomorphic images of stochastic languages

DOI10.1016/0020-0255(81)90033-5MaRDI QIDQ1163382zbMATH OpenOpenAlexWikidataFDO

Authors 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

bounded languages regarded as graphs of recursive functionsclosure of classes of stochastic languages under homomorphismslanguages recognized by stochastic automatarecursively enumerable sets

Mathematics Subject Classification ID

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

Cites work

• Elementary bounded languages
• Generalized Automata and Stochastic Languages
• scientific article; zbMATH DE number 3860421 (Why is no real title available?)
• scientific article; zbMATH DE number 3765173 (Why is no real title available?)
• scientific article; zbMATH DE number 3509706 (Why is no real title available?)
• scientific article; zbMATH DE number 3531303 (Why is no real title available?)
• scientific article; zbMATH DE number 3532865 (Why is no real title available?)
• scientific article; zbMATH DE number 3535999 (Why is no real title available?)
• scientific article; zbMATH DE number 3539209 (Why is no real title available?)
• scientific article; zbMATH DE number 3582249 (Why is no real title available?)
• scientific article; zbMATH DE number 3588051 (Why is no real title available?)
• scientific article; zbMATH DE number 3440485 (Why is no real title available?)
• scientific article; zbMATH DE number 3278278 (Why is no real title available?)
• scientific article; zbMATH DE number 3305982 (Why is no real title available?)
• scientific article; zbMATH DE number 3336816 (Why is no real title available?)
• scientific article; zbMATH DE number 3371972 (Why is no real title available?)
• Langages à un compteur
• Linear Languages and the Intersection Closures of Classes of Languages
• On complements of some bounded context-sensitive languages
• On homomorphic images of rational stochastic languages
• On Languages Accepted in Polynomial Time
• On multistochastic automata
• On some bounded semiAFLs and AFLs
• On stochastic languages
• On the Languages Representable by Finite Probabilistic Automata
• One counter languages and the IRS condition
• Some closure properties of the family of stochastic languages
• Some remarks on multistochastic automata
• Studies in abstract families of languages
• Word-functions of stochastic and pseudo stochastic automata

Cited in

(6)

• Affine automata verifiers
• On the computational power of affine automata
• Debates with small transparent quantum verifiers
• Computational limitations of affine automata and generalized affine automata
• A new family of nonstochastic languages
• Classical and quantum Merlin-Arthur automata

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1163382)