6533b852fe1ef96bd12ab52f

RESEARCH PRODUCT

Nonstochastic languages as projections of 2-tape quasideterministic languages

Janis LapinsAntra LukjanskaRichard F. BonnerRusins Freivalds

subject

AlgebraClass (set theory)TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESFinite-state machineRegular languageProjection (mathematics)Deterministic automatonComputer scienceProbabilistic automatonCharacterization (mathematics)AlgorithmAutomaton

description

A language L (n) of n-tuples of words which is recognized by a n-tape rational finite-probabilistic automaton with probability 1-e, for arbitrary e > 0, is called quasideterministic. It is proved in [Fr 81], that each rational stochastic language is a projection of a quasideterministic language L (n) of n-tuples of words. Had projections of quasideterministic languages on one tape always been rational stochastic languages, we would have a good characterization of the class of the rational stochastic languages. However we prove the opposite in this paper. A two-tape quasideterministic language exists, the projection of which on the first tape is a nonstochastic language.

yearjournalcountryeditionlanguage
1998-01-01
https://doi.org/10.1007/bfb0055770