scientific article; zbMATH DE number 17834
From MaRDI portal
Publication:3975178
[For the entire collection see Zbl 0726.00018.] In \textit{F. Ablayev} [Lect. Notes Comp. Sci. 324, 154-161 (1986; Zbl 0652.68054)] we formulated a certain property \(F\) of the structure of regular languages in terms of property of states of \(DA\) representing them. It is proved that the probabilistic complexity of arbitrary regular language \(L\) depends upon the power of \(F\)-subset of states of DA representing \(L\) and upon required error probability. In this paper we generalize the results of [loc. cit.].
Recommendations
- scientific article; zbMATH DE number 20623
- scientific article; zbMATH DE number 1960351
- The complexity of probabilistic versus deterministic finite automata
- scientific article; zbMATH DE number 1809724
- On the Complexity of the Equivalence Problem for Probabilistic Automata
- Probabilism versus Alternation for Automata
- scientific article; zbMATH DE number 4064485
- scientific article; zbMATH DE number 3856433
- On the computational complexity of approximating distributions by probabilistic automata
- Comparisons between measures of nondeterminism on finite automata
Cited in
(12)- Lower bounds for one-way probabilistic communication complexity and their application to space complexity
- On properties and state complexity of deterministic state-partition automata
- scientific article; zbMATH DE number 1809724 (Why is no real title available?)
- scientific article; zbMATH DE number 3856433 (Why is no real title available?)
- scientific article; zbMATH DE number 3860398 (Why is no real title available?)
- scientific article; zbMATH DE number 4064485 (Why is no real title available?)
- scientific article; zbMATH DE number 20623 (Why is no real title available?)
- Lower bounds for one-way probabilistic communication complexity
- Lower bounds for the state complexity of probabilistic languages and the language of prime numbers
- The online space complexity of probabilistic languages
- Probabilism versus Alternation for Automata
- The complexity of probabilistic versus deterministic finite automata
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3975178)