Navegar

Colección

Datos Estadísticas

Artículo

Bedregal, B.R.C.; Figueira, S. "Classical computability and fuzzy Turing machines" (2006) LATIN 2006: Theoretical Informatics - 7th Latin American Symposium. 3887 LNCS:154-165
La versión final de este artículo es de uso interno. El editor solo permite incluir en el repositorio el artículo en su versión post-print. Por favor, si usted la posee enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

We work with fuzzy Turing machines (FTMS) and we study the relationship between this computational model and classical recursion concepts such as computable functions, r.e. sets and universality. FTMS are first regarded as acceptors. It has recently been shown in [23] that these machines have more computational power than classical Turing machines. Still, the context in which this formulation is valid has an unnatural implicit assumption, We settle necessary and sufficient conditions for a language to be r.e., by embedding it in a fuzzy language recognized by a FTM and we do the same thing for difference r.e. sets, a class of "harder" sets in terms of computability. It is also shown that there is no universal FTM. We also argue for a definition of computable fuzzy function, when FTMS are understood as transducers. It is shown that, in this case, our notion of computable fuzzy function coincides with the classical one. © Springer-Verlag Berlin Heidelberg 2006.

Registro:

Documento: Artículo
Título:Classical computability and fuzzy Turing machines
Autor:Bedregal, B.R.C.; Figueira, S.
Ciudad:Valdivia
Filiación:Federal University of Rio Grande do Norte, Department of Informatics and Applied Mathematics, Laboratory of Logic and Computational Intelligence, Natal-RN, Brazil
University of Buenos Aires, Department of Computer Science, FCEyN, Buenos Aires, Argentina
Palabras clave:Computational complexity; Mathematical models; Recursive functions; Set theory; Transducers; Classical recursion concepts; Computable fuzzy function; Computational power; Fuzzy Turing machines; Fuzzy sets
Año:2006
Volumen:3887 LNCS
Página de inicio:154
Página de fin:165
DOI: http://dx.doi.org/10.1007/11682462_18
Título revista:LATIN 2006: Theoretical Informatics - 7th Latin American Symposium
Título revista abreviado:Lect. Notes Comput. Sci.
ISSN:03029743
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v3887LNCS_n_p154_Bedregal

Referencias:

  • Alsina, C., Trillas, E., Valverde, L., On non-distributive logical connectives for fuzzy set theory (1980) Busefal, 3, pp. 18-29
  • Biacino, L., Gerla, G., Fuzzy subsets: A constructive approach (1992) Fuzzy Sets and Systems, 45, pp. 161-168
  • Clares, B., Delgado, M., Introduction of the concept of recursiveness of fuzzy functions (1987) Fuzzy Sets and Systems, 21, pp. 301-310
  • Demirci, M., Fuzzy functions and their applications (2000) Journal of Mathematical Analysis and Appliactions, 252 (1), pp. 495-517
  • Deutsch, D., Quantum theory, the Church-Turing principle and the universal quantum computer (1985) Proc. Roy. Soc. London Ser. A, 400, pp. 97-117
  • Fenner, S.A., Fortnow, L., Naik, A.V., Rogers, J.D., Inverting onto functions (2003) Information and Computation, 186 (1), pp. 90-103
  • Gerla, G., (2001) Fusszy Logic: Mathematical Tools for Approximate Reasoning, , Springer-Verlag, Berlin Heidelberg New York
  • Goldin, D.Q., Smolka, S.A., Attie, P.C., Sonderegger, E.L., Turing machines, transition systems and interaction (2004) Information and Computation, 194, pp. 101-128
  • Harkleroad, L., Fuzzy recursion, ret's and isols (1984) Zeitschrift fur Math. Logik und Grundlagen der Mathematik, 30, pp. 425-436
  • Harrison, M.A., (1978) Introduction to Formal Language Theory, , Addison-Wesley publishing, Reading, Massachusetts
  • Hopcroft, J.E., Ullman, J.D., (1979) Introduction to Automata Theory, Languages and Computation, , Addison-Wesley publishing, Reading, Massachusetts
  • Lee, E.T., Zadeh, L.A., Note on fuzzy languages (1969) Information Sciences, 1 (4), pp. 421-434
  • Linz, P., (2001) An Introduction to Formal Language and Automata, , Jones and Bartlett Publisher
  • Moraga, C., Towards a fuzzy computability? (1999) Mathware & Soft Computing, 6, pp. 163-172
  • Morales-Bueno, R., Conejo, R., Prez-De-La-Cruz, J.L., Triguero-Ruiz, F., On a class of fuzzy computable functions (2001) Fuzzy Sets and Systems, 121, pp. 505-522
  • Porfilieva, I., Fuzzy function as an approximate solution to a system of fuzzy relation equations (2004) Fuzzy Sets and Systems, 147, pp. 363-383
  • Santos, E., Fuzzy algorithms (1970) Information and Control, 17, pp. 326-339
  • Santos, E., Fuzzy and probabilistic programs (1976) Information Sciences, 10, pp. 331-335
  • Schweizer, B., Sklar, A., Associative functions and abstract semigroups (1963) Publ. Math. Debrecen, 10, pp. 69-81
  • Soare, R., (1987) Recursively Enumerable Sets and Degrees, , Springer-Verlag, Berlin Heidelberg New York
  • Weihrauch, K., (2000) Computable Analysis - An Introduction, , Springer Verlag, Berlin Heildelberg New York
  • Wiedermann, J., Fuzzy Turing machines revised (2002) Computating and Informatics, 21 (3), pp. 1-13
  • Wiedermann, J., Characterizing the super-Turing computing power and efficiency of classical fuzzey Turing machines (2004) Theoretical Computer Science, 317, pp. 61-69
  • Zadeh, L.A., Fuzzy algorithms (1968) Information and Control, 2, pp. 94-102
  • Zimmermann, H.J., (2001) Fuzzy Set Theory and Its Applications. 4th Edition, , Kluwer Academic Publishers, Dorbrecht Boston LondonA4 - Centro Latinoamericano de Estudios en Informatica, CLEI; U. Chile, Centro de Modelamiento Matematico; CONICYT via grant Anillo en Redes; International Federation for Information Processing, IFIP

Citas:

---------- APA ----------
Bedregal, B.R.C. & Figueira, S. (2006) . Classical computability and fuzzy Turing machines. LATIN 2006: Theoretical Informatics - 7th Latin American Symposium, 3887 LNCS, 154-165.
http://dx.doi.org/10.1007/11682462_18
---------- CHICAGO ----------
Bedregal, B.R.C., Figueira, S. "Classical computability and fuzzy Turing machines" . LATIN 2006: Theoretical Informatics - 7th Latin American Symposium 3887 LNCS (2006) : 154-165.
http://dx.doi.org/10.1007/11682462_18
---------- MLA ----------
Bedregal, B.R.C., Figueira, S. "Classical computability and fuzzy Turing machines" . LATIN 2006: Theoretical Informatics - 7th Latin American Symposium, vol. 3887 LNCS, 2006, pp. 154-165.
http://dx.doi.org/10.1007/11682462_18
---------- VANCOUVER ----------
Bedregal, B.R.C., Figueira, S. Classical computability and fuzzy Turing machines. Lect. Notes Comput. Sci. 2006;3887 LNCS:154-165.
http://dx.doi.org/10.1007/11682462_18