The DOI matches its Crossref record; 68 of the 68 references it cites were found in a registry or an index.
Probabilistic finite-state machines - part I
Open accessAbstract
Probabilistic finite-state machines are used today in a variety of areas in pattern recognition, or in fields to which pattern recognition is linked: computational linguistics, machine learning, time series analysis, circuit testing, computational biology, speech recognition, and machine translation are some of them. In Part I of this paper, we survey these generative objects and study their definitions and properties. In Part II, we will study the relation of probabilistic finite-state automata with other well-known devices that generate strings as hidden Markov models and n-grams and provide theorems, algorithms, and properties that represent a current state of the art of these objects.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Elements of Information Theory
Cover, T. M., & Thomas, J. A. (2001) · Wiley eBooks · doi:10.1002/0471200611 · Cited by 36,808
A tutorial on hidden Markov models and selected applications in speech recognition
Rabiner, L. R. (1989) · Proceedings of the IEEE · doi:10.1109/5.18626 · Cited by 22,743
Breiman, L. (1996) · Machine Learning · doi:10.1007/bf00058655 · Cited by 16,325
Elements of Information Theory
Cover, T. M., & Thomas, J. A. (2005) · doi:10.1002/047174882x · Cited by 13,791
Forney, G. D. (1973) · Proceedings of the IEEE · doi:10.1109/proc.1973.9030 · Cited by 5,647
The EM Algorithm and Extensions
Kushary, D. (1998) · Technometrics · doi:10.1080/00401706.1998.10485534 · Cited by 5,417
Language identification in the limit
Gold, E. M. (1967) · Information and Control · doi:10.1016/s0019-9958(67)91165-5 · Cited by 3,572
On the Convergence Properties of the EM Algorithm
Wu, C. F. J. (1983) · The Annals of Statistics · doi:10.1214/aos/1176346060 · Cited by 3,269
(1992) · doi:10.5555/176313.176316 · Cited by 2,892
Statistical Methods for Speech Recognition
Sun, D. X., & Jelinek, F. (1999) · Journal of the American Statistical Association · doi:10.2307/2670189 · Cited by 1,946
Automata, Languages, and Machines
(1974) · Pure and applied mathematics · doi:10.1016/s0079-8169(08)x6055-6 · Cited by 1,897
An Introduction to Computational Learning Theory
Kearns, M. J., & Vazirani, U. (1994) · doi:10.7551/mitpress/3897.001.0001 · Cited by 1,697
Estimation of probabilities from sparse data for the language model component of a speech recognizer
Katz, S. (1987) · IEEE Transactions on Acoustics, Speech, and Signal Processing · doi:10.1109/tassp.1987.1165125 · Cited by 1,637
Improved backing-off for M-gram language modeling
Kneser, R., & Ney, H. (2002) · 1995 International Conference on Acoustics, Speech, and Signal Processing · doi:10.1109/icassp.1995.479394 · Cited by 1,473
Baum, L. E. (1972) · Medical Entomology and Zoology · Cited by 1,405
Introduction to formal language theory
(1980) · Computer Languages · doi:10.1016/0096-0551(80)90068-5 · Cited by 1,254
Syntactic pattern recognition and applications
Fu, K. (1968) · Medical Entomology and Zoology · Cited by 1,015
(1997) · Cited by 914
Weighted finite-state transducers in speech recognition
Mohri, M., Pereira, F., & Riley, M. (2002) · Computer Speech & Language · doi:10.1006/csla.2001.0184 · Cited by 885
Complexity of automaton identification from given data
Gold, E. M. (1978) · Information and Control · doi:10.1016/s0019-9958(78)90562-4 · Cited by 771
Syntactic pattern recognition and applications
Firschein, O. (1983) · Proceedings of the IEEE · doi:10.1109/proc.1983.12755 · Cited by 753
Witten, I. H., & Bell, T. C. (1991) · IEEE Transactions on Information Theory · doi:10.1109/18.87000 · Cited by 729
Gallager, R. G. (1997) · Journal of the Operational Research Society · doi:10.1038/sj.jors.2600329 · Cited by 691
Applications of stochastic context-free grammars using the Inside-Outside algorithm
Lari, K., & Young, S. J. (1991) · Computer Speech & Language · doi:10.1016/0885-2308(91)90009-f · Cited by 639
An Empirical Study of Smoothing Techniques for Language Modeling
Chen, S. F., & Goodman, J. (1996) · arXiv (Cornell University) · doi:10.48550/arxiv.cmp-lg/9606011 · Cited by 612
Syntactic Methods in Pattern Recognition
Fu, K., & Айзерман, М. А. (1976) · IEEE Transactions on Systems Man and Cybernetics · doi:10.1109/tsmc.1976.4309556 · Cited by 497
Gallager, R. G. (1996) · doi:10.1007/978-1-4615-2329-1 · Cited by 494
A bit of progress in language modeling
Goodman, J. T. (2001) · Computer Speech & Language · doi:10.1006/csla.2001.0174 · Cited by 469
Stochastic context-free grammers for tRNA modeling
Sakakibara, Y., Brown, M., Hughey, R., Mian, I. S., Sjölander, K., Underwood, R. C., & Haussler, D. (1994) · Nucleic Acids Research · doi:10.1093/nar/22.23.5112 · Cited by 383
On the learnability of discrete distributions
Kearns, M., Mansour, Y., Ron, D., Rubinfeld, R., Schapire, R. E., & Sellie, L. (1994) · Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 · doi:10.1145/195058.195155 · Cited by 273
Grammatical Inference: Introduction and Survey - Part I
Fu, K.-S., & Booth, T. L. (1975) · IEEE Transactions on Systems, Man, and Cybernetics · doi:10.1109/tsmc.1975.5409159 · Cited by 270
Crytographic limitations on learning Boolean formulae and finite automata
Kearns, M., & Valiant, L. G. (1989) · Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 · doi:10.1145/73007.73049 · Cited by 266
Inducing probabilistic grammars by Bayesian model merging
Stolcke, A., & Omohundro, S. (1994) · Lecture Notes in Computer Science · doi:10.1007/3-540-58473-0_141 · Cited by 230
An omnifont open-vocabulary OCR system for English and Arabic
Bazzi, I., Schwartz, R. M., & Makhoul, J. (1999) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.771314 · Cited by 220
Learning subsequential transducers for pattern recognition interpretation tasks
Oncina, J., Garcia, P., & Vidal, E. (1993) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.211465 · Cited by 198
Self-citationImproved clustering techniques for class-based statistical language modelling
Kneser, R., & Ney, H. (1993) · European Conference on Speech Communication and Technology (Eurospeech) · doi:10.21437/eurospeech.1993-229 · Cited by 193
Parameter estimation for probabilistic finite-state transducers
Eisner, J. M. (2001) · Proceedings of the conference - Association for Computational Linguistics. Meeting · doi:10.3115/1073083.1073085 · Cited by 172
Continuous speech recognition using hidden Markov models
Picone, J. (1990) · IEEE ASSP Magazine · doi:10.1109/53.54527 · Cited by 168
The minimum consistent DFA problem cannot be approximated within any polynomial
Pitt, L., & Warmuth, M. K. (1993) · Journal of the ACM · doi:10.1145/138027.138042 · Cited by 153
Machine Translation with Inferred Stochastic Finite-State Transducers
Casacuberta, F., & Vidal, E. (2004) · Computational Linguistics · doi:10.1162/089120104323093294 · Cited by 148
Self-citationAggregate and mixed-order Markov models for statistical language processingPreprint
Saul, L. K., & Pereira, F. M. B. (1997) · arXiv (Cornell University) · doi:10.48550/arxiv.cmp-lg/9706007 · Cited by 148
ON THE COMPUTATIONAL COMPLEXITY OFAPPROXIMATING DISTRIBUTIONS BY PROBABILISTIC AUTOMATA
Abe, N., & Warmuth, M. K. (1990) · doi:10.5555/92571.92587 · Cited by 147
Dupont, P., Denis, F., & Esposito, Y. (2005) · Pattern Recognition · doi:10.1016/j.patcog.2004.03.020 · Cited by 143
Probabilistic Languages: A Review and Some Open Questions
Wetherell, C. S. (1980) · ACM Computing Surveys · doi:10.1145/356827.356829 · Cited by 143
A Polynomial-Time Algorithm for the Equivalence of Probabilistic Automata
Tzeng, W.-G. (1992) · SIAM Journal on Computing · doi:10.1137/0221017 · Cited by 140
Learning Dependency Translation Models as Collections of Finite-State Head Transducers
Alshawi, H., Bangalore, S., & Douglas, S. (2000) · Computational Linguistics · doi:10.1162/089120100561629 · Cited by 140
On the Convergence Rate of Good-Turing Estimators
McAllester, D., & Schapire, R. E. (2000) · Cited by 130
On the learnability and usage of acyclic probabilistic finite automata
Ron, D., Singer, Y., & Tishby, N. (1995) · Conference on Learning Theory · doi:10.1145/225298.225302 · Cited by 124
Structural Methods in Pattern Recognition
Miclet, L. (1986) · Medical Entomology and Zoology · Cited by 101
Learning probabilistic automata with variable memory length
Ron, D., Singer, Y., & Tishby, N. (1994) · Conference on Learning Theory · doi:10.1145/180139.181006 · Cited by 87
Probabilistic finite-state machines - part II
Vidal, E., Thollard, F., de la Higuera, C., Casacuberta, F., & Carrasco, R. C. (2005) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2005.148 · Cited by 81
Self-citationComputational Complexity of Problems on Probabilistic Grammars and Transducers
Casacuberta, F., & de la Higuera, C. (2000) · Lecture notes in computer science · doi:10.1007/978-3-540-45257-7_2 · Cited by 79
Self-citationPAC-learnability of Probabilistic Deterministic Finite State Automata
Clark, A., & Thollard, F. (2004) · Research Portal (King's College London) · doi:10.5555/1005332.1005349 · Cited by 79
Self-citationMemory-Based Shallow ParsingPreprint
Sang, E. T. K. (2002) · arXiv (Cornell University) · doi:10.48550/arxiv.cs/0204049 · Cited by 77
On the Computational Complexity of Approximating Distributions by Probabilistic Automata
Abe, N., & Warmuth, M. K. (1992) · Machine Learning · doi:10.1007/bf00992677 · Cited by 75
Some approaches to statistical and finite-state speech-to-speech translation
Casacuberta, F., Ney, H., Och, F. J., Vidal, E., Vilar, J. M., Barrachina, S., García-Varea, I., Llorens, D., Martínez-Hinarejos, C.-D., Molau, S., et al. (2003) · Computer Speech & Language · doi:10.1016/s0885-2308(03)00028-7 · Cited by 73
Self-citationLearning DFA from Simple Examples
Parekh, R. G., & Honavar, V. (2001) · Machine Learning · doi:10.1023/a:1010822518073 · Cited by 49
A finite-state approach to machine translation
Bangalore, S., & Riccardi, G. (2005) · IEEE Workshop on Automatic Speech Recognition and Understanding (ASRU) · doi:10.1109/asru.2001.1034665 · Cited by 47
Hidden Markov Models in Speech and Language Processing
Knill, K. M., & Young, S. (1997) · Text, speech and language technology · doi:10.1007/978-94-017-1183-8_2 · Cited by 44
Experiments on the application of IOHMMs to model financial returns series
Bengio, Y., Lauzon, V., & Ducharme, R. (2001) · IEEE Transactions on Neural Networks · doi:10.1109/72.896800 · Cited by 35
A Procedure for Grammatical Inference.
Horning, J. J. (1971) · IFIP Congress · Cited by 25
Learning Fallible Deterministic Finite Automata
Ron, D., & Rubinfeld, R. (1995) · Machine Learning · doi:10.1007/bf00993409 · Cited by 24
Complexity of Comparing Hidden Markov Models
Lyngsø, R. B., & Pedersen, C. N. S. (2001) · Lecture notes in computer science · doi:10.1007/3-540-45678-3_36 · Cited by 16
Head-Transducer Models for Speech Translation and Their Automatic Acquisition from Bilingual Data
Alshawi, H., Bangalore, S., & Douglas, S. (2000) · Machine Translation · doi:10.1023/a:1011187330969 · Cited by 15
Bréhélin, L., Gascuel, O., & Caraux, G. (2001) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.955112 · Cited by 14
PAC learning under helpful distributions
Denis, F., & Gilleron, R. (1997) · Lecture notes in computer science · doi:10.1007/3-540-63577-7_40 · Cited by 11
Properties of stochastic syntax-directed translation schemata
Maryanski, F. J., & Thomason, M. G. (1979) · International Journal of Parallel Programming · doi:10.1007/bf00989665 · Cited by 11
Valiant, L. G. (2026) · Foundations of Computation and Machine Learning · doi:10.1145/3749740.3749746
Metadata
- Authors
- Vidal, E., Thollard, F., de la Higuera, C., Casacuberta, F., & Carrasco, R. C.
- Venue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Published
- 2005-07
- Volume
- 27
- Issue
- 7
- Pages
- 1013-1025
- ISSN
- 0162-8828 (ISSN-L)
- OpenAlex
- W2122092249
- Cited by
- 301
- References
- 68
- FWCI
- 15.06
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.
