Quasi-Distances and Weighted Finite Automata

详细信息    查看全文

• 关键词：Regular languages ; Weighted finite automata ; State complexity ; Distance measures
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：9118
• 期：1
• 页码：209-219
• 全文大小：240 KB
• 参考文献：1.Benedikt, M., Puppis, G., Riveros, C.: Bounded repairability of word languages. J. Comput. Syst. Sci. 79, 1302鈥?321 (2013)MATH MathSciNet View Article
  2.Calude, C.S., Salomaa, K., Yu, S.: Distances and quasi-distances between words. J. Univ. Comput. Sci. 8(2), 141鈥?52 (2002)MATH MathSciNet
  3.Choffrut, C., Pighizzini, G.: Distances between languages and reflexivity of relations. Theoret. Comput. Sci. 286, 117鈥?38 (2002)MATH MathSciNet View Article
  4.Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)MATH
  5.Deza, M.M., Deza, E.: Encyclopedia of Distances. Springer, Heidelberg (2009)MATH View Article
  6.Droste, M., Kuich, W., Vogler, H. (eds.): Handbook of Weighted Automata. EATCS Monographs in Theoretical Computer Science. Springer, Heidelberg (2009)MATH
  7.Eramian, M.: Efficient simulation of nondeterministic weighted finite automata. J. Automata Lang. Comb. 9, 257鈥?67 (2004)MATH MathSciNet
  8.Han, Y.-S., Ko, S.-K., Salomaa, K.: The edit distance between a regular language and a context-free language. Int. J. Found. Comput. Sci. 24, 1067鈥?082 (2013)MATH MathSciNet View Article
  9.Holzer, M., Kutrib, M.: Descriptional and computational complexity of finite automata 鈥?a survey. Inf. Comput. 209, 456鈥?70 (2011)MATH MathSciNet View Article
  10.Kari, L., Konstantinidis, S.: Descriptional complexity of error/edit systems. J. Automata Lang. Comb. 9, 293鈥?09 (2004)MATH MathSciNet
  11.Konstantinidis, S.: Transducers and the properties of error detection, error-correction, and finite-delay decodability. J. Univ. Comput. Sci. 8, 278鈥?91 (2002)MATH MathSciNet
  12.Konstantinidis, S.: Computing the edit distance of a regular language. Inf. Comput. 205, 1307鈥?316 (2007)MATH MathSciNet View Article
  13.Levenshtein, V.I.: Binary codes capable of correcting deletions, insertions, and reversals. Sov. Phys. Dokl. 10(8), 707鈥?10 (1966)MathSciNet
  14.Ng, T., Rappaport, D., Salomaa, K.: State complexity of neighbourhoods and approximate pattern matching (March 2015, Submitted for publication)
  15.Pighizzini, G.: How hard is computing the edit distance? Inf. Comput. 165, 1鈥?3 (2001)MATH MathSciNet View Article
  16.Povarov, G.: Descriptive complexity of the Hamming neighborhood of a regular language. In: Proceedings of the 1st International Conference Language and Automata Theory and Applications, LATA 2007, pp. 509鈥?20 (2007)
  17.Salomaa, K., Schofield, P.: State complexity of additive weighted finite automata. Int. J. Found. Comput. Sci. 18(6), 1407鈥?416 (2007)MATH MathSciNet View Article
  18.Schofield, P.: Error Quantification and Recognition Using Weighted Finite Automata. MSc thesis, Queen鈥檚 University, Kingston, Canada (2006)
  19.Shallit, J.: A Second Course in Formal Languages and Automata Theory. Cambridge University Press, Cambridge (2009)MATH
  20.Yu, S.: Regular languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 1, pp. 41鈥?10. Springer, Heidelberg (1997)View Article
  
• 作者单位：Timothy Ng (15)
  David Rappaport (15)
  Kai Salomaa (15)
  
  15. School of Computing, Queen鈥檚 University, Kingston, ON, K7L 3N6, Canada
  
• 丛书名：Descriptional Complexity of Formal Systems
• ISBN：978-3-319-19225-3
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

We show that the neighbourhood of a regular language \(L\) with respect to an additive quasi-distance can be recognized by an additive weighted finite automaton (WFA). The size of the WFA is the same as the size of an NFA (nondeterministic finite automaton) for \(L\) and the construction gives an upper bound for the state complexity of a neighbourhood of a regular language with respect to a quasi-distance. We give a tight lower bound construction for the determinization of an additive WFA using an alphabet of size five. The previously known lower bound construction needed an alphabet that is linear in the number of states of the WFA.