Injection Structures Specified by Finite State Transducers

详细信息    查看全文

• 关键词：Computability theory ; Injection structures ; Automatic structures ; Finite state automata ; Finite state transducers
• 刊名：Lecture Notes in Computer Science
• 出版年：2017
• 出版时间：2017
• 年：2017
• 卷：10010
• 期：1
• 页码：394-417
• 参考文献：1.Bennett, C.H.: Logical reversibility of computation. IBM J. Res. Dev. 17, 525–532 (1973)MathSciNet CrossRef MATH
  2.Ash, C., Knight, J.: Computable Structures and the Hyperarithmetical Hierarchy. Elsevier, Amsterdam (2000)MATH
  3.Blumensath, A.: Automatic structures. Diploma Thesis, RWTH Aachen (1999)
  4.Blumensath, A., Grädel, E.: Automatic structures. In: Proceedings of the 15th LICS, pp. 51–62 (2000)
  5.Cenzer, D., Harizanov, V., Remmel, J.B.: Effective categoricity of injection structures. In: Löwe, B., Normann, D., Soskov, I., Soskova, A. (eds.) CiE 2011. LNCS, vol. 6735, pp. 51–60. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-21875-0_​6 CrossRef
  6.Cenzer, D., Harizanov, V., Remmel, J.B.: Computability-theoretic properties of injection structures. In: Algebra and Logic (to appear)
  7.Delhommé, C.: Automaticité des ordinaux et des graphes homogènes. C.R. Acadèmie des sciences Paris, Ser. I 339, 5–10 (2004)CrossRef
  8.Hodgson, B.R.: On direct products of automaton decidable theories. Theoret. Comput. Sci. 19, 331–335 (1982). North-HollandMathSciNet CrossRef MATH
  9.Khoussainov, B., Nerode, A.: Automatic presentations of structures. In: Leivant, D. (ed.) LCC 1994. LNCS, vol. 960, pp. 367–392. Springer, Heidelberg (1995). doi:10.​1007/​3-540-60178-3_​93 CrossRef
  10.Khoussainov, B., Shore, R.A.: Effective model theory: the number of models and their complexity. In: Cooper, S.B., Truss, J.K. (eds.) Models and Computability, Invited Papers from LC 1997, LMSLNS vol. 259, pp. 193–240, Cambridge University Press, Cambridge (1999)
  11.Khoussainov, B., Rubin, S., Stephan, F.: On automatic partial orders. In: Proceedings of the 18th LICS, pp. 168–177 (2003)
  12.Khoussainov, B., Nies, A., Rubin, S., Stephan, F.: Automatic structures: richness and limitations. In: Proceedings of the 19th LICS, pp. 44–53 (2004)
  13.Khoussainov, B., Rubin, S., Stephan, F.: Automatic linear orders and trees. ACM Trans. Comput. Logic 6(4), 675–700 (2005)MathSciNet CrossRef
  14.Khoussainov, B., Liu, J., Minnes, M.: Unary automatic graphs: an algorithmic perspective. In: Agrawal, M., Du, D., Duan, Z., Li, A. (eds.) TAMC 2008. LNCS, vol. 4978, pp. 542–553. Springer, Heidelberg (2008). doi:10.​1007/​978-3-540-79228-4_​47 CrossRef
  15.Rubin, S.: Automatic structures. Ph.D. Thesis, University of Auckland (2004)
  16.Soare, R.I.: Recursively Enumerable Sets and Degrees. Springer, Berlin (1987)CrossRef MATH
  
• 作者单位：Sam Buss (19)
  Douglas Cenzer (20)
  Mia Minnes (21)
  Jeffrey B. Remmel (19)
  
  19. Department of Mathematics, University of California-San Diego, La Jolla, CA, 92093-0112, USA
  20. Department of Mathematics, University of Florida, Gainesville, FL, 32611, USA
  21. Department of Computer Science and Engineering, University of California-San Diego, La Jolla, CA, 92093-0404, USA
  
• 丛书名：Computability and Complexity
• ISBN：978-3-319-50062-1
• 卷排序：10010

文摘

An injection structure \({\mathcal A}= (A,f)\) is a set A together with a one-place one-to-one function f. \({\mathcal A}\) is an FST injection structure if A is a regular set, that is, the set of words accepted by some finite automaton, and f is realized by a finite-state transducer. We initiate the study of FST injection structures. We show that the model checking problem for FST injection structures is undecidable which contrasts with the fact that the model checking problem for automatic relational structures is decidable. We also explore which isomorphisms types of injection structures can be realized by FST injections. For example, we completely characterize the isomorphism types that can be realized by FST injection structures over a unary alphabet. We show that any FST injection structure is isomorphic to an FST injection structure over a binary alphabet. We also prove a number of positive and negative results about the possible isomorphism types of FST injection structures over an arbitrary alphabet.