El algoritmo de Quine-McCluskey ( QMC ), también conocido como el método de implicantes primos , es un método utilizado para la reducción al mínimo de funciones booleanas que fue desarrollado por Willard V. Quine en 1952 [1] [2] y ampliado por Edward J. McCluskey en 1956. [3] Como principio general, este enfoque ya había sido demostrado por el lógico Hugh McColl en 1878, [4] [5] [6] fue probado por Archie Blake en 1937, [7] [8] [9] [6]y fue redescubierto por Edward W. Samson y Burton E. Mills en 1954 [10] [6] y por Raymond J. Nelson en 1955. [11] [6] También en 1955, Paul W. Abrahams y John G. Nordahl [12] así como Albert A. Mullin y Wayne G. Kellner [13] [14] [15] [16] propusieron una variante decimal del método. [17] [14] [15] [16] [18] [19] [20] [21]
El algoritmo de Quine-McCluskey es funcionalmente idéntico al mapeo de Karnaugh , pero la forma tabular lo hace más eficiente para su uso en algoritmos informáticos y también proporciona una forma determinista de comprobar que se ha alcanzado la forma mínima de una función booleana. A veces se lo denomina método de tabulación.
El método consta de dos pasos:
- Encontrar todos los implicantes primos de la función.
- Utilice esos implicantes primos en un gráfico de implicantes primos para encontrar los implicantes primos esenciales de la función, así como otros implicantes primos necesarios para cubrir la función.
Complejidad
Aunque es más práctico que el mapeo de Karnaugh cuando se trata de más de cuatro variables, el algoritmo de Quine-McCluskey también tiene un rango de uso limitado ya que el problema que resuelve es NP-completo . [22] [23] [24] El tiempo de ejecución del algoritmo de Quine-McCluskey crece exponencialmente con el número de variables. Para una función de n variables, el número de implicantes primos puede ser tan grande como 3 n / ln ( n ), [ cita requerida ], por ejemplo, para 32 variables puede haber más de 534 × 10 12 implicantes primos. Las funciones con un gran número de variables deben minimizarse con métodos heurísticos potencialmente no óptimos , de los cuales el minimizador lógico heurístico de Espresso fue el estándar de facto en 1995. [ necesita actualización ] [25]
El segundo paso del algoritmo equivale a resolver el problema de cobertura del conjunto ; [26] En este paso del algoritmo pueden producirse instancias NP-difíciles de este problema. [27] [28]
Ejemplo
Aporte
En este ejemplo, la entrada es una función booleana en cuatro variables, que evalúa a en los valores y , evalúa a un valor desconocido en y , y para en cualquier otro lugar (donde estos enteros se interpretan en su forma binaria para la entrada a para la concisión de la notación). Los insumos que evalúan parase llaman 'minitérminos'. Codificamos toda esta información escribiendo
Esta expresión dice que la función de salida f será 1 para los minitérminos y (denotado por el término 'm') y que no nos importa la salida para y combinaciones (denotadas por el término 'd').
Paso 1: encontrar implicantes primos
Primero, escribimos la función como una tabla (donde 'x' significa no importa):
A B C D F m0 0 0 0 0 0 m1 0 0 0 1 0 m2 0 0 1 0 0 m3 0 0 1 1 0 m4 0 1 0 0 1 m5 0 1 0 1 0 m6 0 1 1 0 0 m7 0 1 1 1 0 m8 1 0 0 0 1 m9 1 0 0 1 X m10 1 0 1 0 1 m11 1 0 1 1 1 m12 1 1 0 0 1 m13 1 1 0 1 0 m14 1 1 1 0 X m15 1 1 1 1 1
Uno puede formar fácilmente la expresión canónica de suma de productos a partir de esta tabla, simplemente sumando los términos mínimos (dejando de lado los términos de indiferencia ) donde la función se evalúa como uno:
- f A, B, C, D = A'BC'D '+ AB'C'D' + AB'CD '+ AB'CD + ABC'D' + ABCD.
que no es mínimo. Entonces, para optimizar, todos los minitérminos que evalúan a uno se colocan primero en una tabla de minitérminos. Los términos que no importan también se agregan a esta tabla (nombres entre paréntesis), por lo que se pueden combinar con términos mínimos:
Número
de 1sMinterm
Representación binaria1 m4 0100 m8 1000 2 (m9) 1001 m10 1010 m12 1100 3 m11 1011 (m14) 1110 4 m15 1111
En este punto, uno puede comenzar a combinar minitérminos con otros minitérminos. Si dos términos difieren solo en un dígito, ese dígito se puede reemplazar con un guión que indica que el dígito no importa. Los términos que ya no se pueden combinar están marcados con un asterisco (*). Por ejemplo, 1000
y 1001
se puede combinar para dar 100-
, lo que indica que ambos términos mínimos implican que el primer dígito es 1
y los dos siguientes son 0
.
Número
de 1sMinterm 0-cubo Implicantes de tamaño 2 1 m4 0100 m (4,12) -100 * m8 1000 m (8,9) 100- - - m (8,10) 10-0 - - m (8,12) 1-00 2 m9 1001 m (9,11) 10-1 m10 1010 m (10,11) 101- - - m (10,14) 1-10 m12 1100 m (12,14) 11-0 3 m11 1011 m (11,15) 1-11 m14 1110 m (14,15) 111- 4 m15 1111 -
Al pasar del tamaño 2 al tamaño 4, trátelo -
como un tercer valor de bit. Por ejemplo, -110
y -100
puede combinarse para dar -1-0
, como puede -110
y -11-
para dar -11-
, pero -110
y 011-
no puede porque -110
está implícito en 1110
while 011-
no lo es. (Truco: empareja el -
primero).
Número
de 1sMinterm 0-cubo Implicantes de tamaño 2 Implicantes de tamaño 4 1 m4 0100 m (4,12) -100 * m (8,9,10,11) 10 - * m8 1000 m (8,9) 100- m (8,10,12,14) 1--0 * - - m (8,10) 10-0 - - - m (8,12) 1-00 - 2 m9 1001 m (9,11) 10-1 m (10,11,14,15) 1-1- * m10 1010 m (10,11) 101- - - - m (10,14) 1-10 - m12 1100 m (12,14) 11-0 - 3 m11 1011 m (11,15) 1-11 - m14 1110 m (14,15) 111- - 4 m15 1111 - -
Nota: En este ejemplo, ninguno de los términos de la tabla de implicantes de tamaño 4 se puede combinar más. En general, este proceso debe continuar (tamaños 8, 16, etc.) hasta que no se puedan combinar más términos.
Paso 2: gráfico de implicantes primos
Ninguno de los términos puede combinarse más allá de esto, por lo que en este punto construimos una tabla de implicantes primos esenciales. A un lado van los principales implicantes que se acaban de generar, y a lo largo de la parte superior van los términos mínimos especificados anteriormente. Los términos no importa no se colocan en la parte superior; se omiten en esta sección porque no son entradas necesarias.
4 8 10 11 12 15 ⇒ A B C D m (4,12) * ⇒ - 1 0 0 m (8,9,10,11) ⇒ 1 0 - - m (8,10,12,14) ⇒ 1 - - 0 m (10,11,14,15) * ⇒ 1 - 1 -
Para encontrar los implicantes primos esenciales, recorremos la fila superior. Tenemos que buscar columnas con solo una "✓". Si una columna tiene solo una "✓", esto significa que el minitérmino solo puede ser cubierto por un implicante principal. Este implicante principal es esencial .
Por ejemplo: en la primera columna, con el término mínimo 4, solo hay una "✓". Esto significa que m (4,12) es esencial. Así que colocamos una estrella a su lado. Minterm 15 también tiene solo una "✓", por lo que m (10,11,14,15) también es esencial. Ahora se cubren todas las columnas con una "✓".
El segundo implicante primo puede ser "cubierto" por el tercero y el cuarto, y el tercer implicante primo puede ser "cubierto" por el segundo y el primero, y por tanto ninguno es esencial. Si un implicante primo es esencial, entonces, como era de esperar, es necesario incluirlo en la ecuación booleana minimizada. En algunos casos, los implicantes primos esenciales no cubren todos los términos mínimos, en cuyo caso se pueden emplear procedimientos adicionales para la reducción de gráficos. El "procedimiento adicional" más simple es prueba y error, pero una forma más sistemática es el método de Petrick . En el ejemplo actual, los implicantes primos esenciales no manejan todos los términos mínimos, por lo que, en este caso, los implicantes esenciales se pueden combinar con uno de los dos no esenciales para producir una ecuación:
- f A, B, C, D = BC'D '+ AB' + AC [29]
o
- f A, B, C, D = BC'D '+ AD' + AC
Ambas ecuaciones finales son funcionalmente equivalentes a la ecuación detallada original:
- f A, B, C, D = A'BC'D '+ AB'C'D' + AB'C'D + AB'CD '+ AB'CD + ABC'D' + ABCD '+ ABCD.
Ver también
- Forma canónica de Blake [7] [6]
- Algoritmo de Buchberger: algoritmo análogo para geometría algebraica
- El método de Petrick
- Análisis comparativo cualitativo (QCA)
Referencias
- ^ Quine, Willard Van Orman (octubre de 1952). "El problema de simplificar las funciones de la verdad". The American Mathematical Monthly . 59 (8): 521–531. doi : 10.2307 / 2308219 . JSTOR 2308219 .
- ^ Quine, Willard Van Orman (noviembre de 1955). "Una forma de simplificar las funciones de la verdad". The American Mathematical Monthly . 62 (9): 627–631. doi : 10.2307 / 2307285 . hdl : 10338.dmlcz / 142789 . JSTOR 2307285 .
- ^ McCluskey, Jr., Edward Joseph (noviembre de 1956). "Minimización de funciones booleanas" . Revista técnica de Bell System . 35 (6): 1417–1444. doi : 10.1002 / j.1538-7305.1956.tb03835.x . hdl : 10338.dmlcz / 102933 . Consultado el 24 de agosto de 2014 .
- ^ McColl, Hugh (14 de noviembre de 1878). "El cálculo de declaraciones equivalentes (tercer artículo)" . Actas de la London Mathematical Society . s1-10 (1): 16-28. doi : 10.1112 / plms / s1-10.1.16 .
- ^ Ladd, Christine (1883). "Sobre el álgebra de la lógica". En Peirce, Charles Sanders (ed.). Estudios de lógica . Boston, Estados Unidos: Little, Brown & Company . págs. 17–71. pag. 23:
[...] Si la reducción [de una expresión a la forma más simple] no es evidente, se puede facilitar tomando el negativo de la expresión, reduciéndola y luego restaurándola a la forma positiva. [...]
- ^ a b c d e Brown, Frank Markham (noviembre de 2010) [2010-10-27]. "McColl y Minimización" . Historia y Filosofía de la Lógica . Taylor y Francis . 31 (4): 337–348. doi : 10.1080 / 01445340.2010.517387 . ISSN 1464-5149 . Archivado desde el original el 15 de abril de 2020 . Consultado el 15 de abril de 2020 .
- ^ a b Blake, Archie (1938) [1937]. Expresiones canónicas en álgebra booleana (disertación) (edición litografiada). Chicago, Illinois, EE.UU .: Bibliotecas de la Universidad de Chicago . pag. 36. p. 36:
[...] este método era conocido por Peirce y sus estudiantes [...] Se menciona en varios lugares en Studies in Logic, por miembros de la Universidad Johns Hopkins , 1883 [...]
(ii + 60 páginas) - ^ Blake, Archie (noviembre de 1932). "Expresiones canónicas en álgebra de Boole". Boletín de la American Mathematical Society . Resúmenes de artículos: 805.
- ^ Blake, Archie (junio de 1938). "Correcciones a expresiones canónicas en álgebra booleana " . El diario de la lógica simbólica . Asociación de Lógica Simbólica . 3 (2): 112-113. doi : 10.2307 / 2267595 . ISSN 0022-4812 . JSTOR 2267595 .
- ^ Sansón, Edward Walter; Mills, Burton E. (abril de 1954). Minimización de circuitos: álgebra y algoritmos para nuevas expresiones canónicas booleanas . Bedford, Massachusetts, EE.UU .: Centro de Investigación de Cambridge de la Fuerza Aérea . Informe técnico AFCRC TR 54-21.
- ^ Nelson, Raymond J. (junio de 1955). "Funciones de verdad normales más simples". El diario de la lógica simbólica . Asociación de Lógica Simbólica . 20 (2): 105–108. doi : 10.2307 / 2266893 . JSTOR 2266893 . (4 páginas)
- ^ "Bienvenido a la página conmemorativa de John" Jack "G Nordahl 14 de junio de 1933 ~ 20 de noviembre de 2017 (84 años)" . Servicios funerarios y de cremación de Jellison. Archivado desde el original el 5 de mayo de 2020 . Consultado el 5 de mayo de 2020 .
- ^ Mullin, Albert Alkins ; Kellner, Wayne G. (1958). Escrito en la Universidad de Illinois, Urbana, EE. UU. Y en el Departamento de Ingeniería Eléctrica, Instituto de Tecnología de Massachusetts , Massachusetts, EE. UU. "Una prueba de residuos para funciones booleanas" (PDF) . Transacciones de la Academia de Ciencias del Estado de Illinois (memorando de enseñanza). Springfield, Illinois, Estados Unidos. 51 (3-4): 14-19. S2CID 125171479 . Archivado (PDF) desde el original el 5 de mayo de 2020 . Consultado el 5 de mayo de 2020 . [1] (6 páginas) (NB. En su libro , Caldwell lo fecha en noviembre de 1955 como un memorando de enseñanza. Dado que Mullin fecha su trabajo en 1958 en otro trabajo y el memorando de clase de Abrahams / Nordahl también está fechado en noviembre de 1955, esto podría ser un error de copia.)
- ^ a b Caldwell, Samuel Hawks (1 de diciembre de 1958) [febrero de 1958]. "5.8. Operaciones con símbolos decimales". Escrito en Watertown, Massachusetts, EE. UU. Circuitos de conmutación y diseño lógico . 5a edición de septiembre de 1963 (1a ed.). Nueva York, Estados Unidos: John Wiley & Sons Inc. págs. 162–169. ISBN 0-47112969-0. LCCN 58-7896 . pag. 166:
[...] Es un placer dejar constancia de que este tratamiento se basa en el trabajo de dos estudiantes durante el período que estaban estudiando Switching Circuits en el Massachusetts Institute of Technology. Discutieron el método de forma independiente y luego colaboraron en la preparación de un memorando de clase: PW Abraham y JG Nordahl [...]
(xviii + 686 páginas) (NB. Para el primer tratado importante del método decimal en este libro, a veces se lo conoce engañosamente como "tabulación decimal de Caldwell".) - ^ a b Mullin, Albert Alkins ( 15 de marzo de 1960 ) [19 de septiembre de 1959]. Escrito en la Universidad de Illinois, Urbana, EE. UU. Fisher, Harvey I .; Ekblaw, George E .; Verde, FO; Jones, Reece; Kruidenier, Francis; McGregor, John; Silva, Paul; Thompson, Milton (eds.). "Dos aplicaciones de la teoría de números elemental" (PDF) . Transacciones de la Academia de Ciencias del Estado de Illinois . Springfield, Illinois, Estados Unidos. 52 (3–4): 102–103. Archivado (PDF) desde el original el 5 de mayo de 2020 . Consultado el 5 de mayo de 2020 . [2] [3] [4] (2 páginas)
- ^ a b McCluskey, Jr., Edward Joseph (junio de 1960). "Albert A. Mullin y Wayne G. Kellner. Una prueba de residuos para funciones booleanas. Transacciones de la Academia de Ciencias del Estado de Illinois, vol. 51 nos. 3 y 4, (1958), págs. 14-19". The Journal of Symbolic Logic (Revisión). 25 (2): 185. doi : 10.2307 / 2964263 . JSTOR 2964263 . pag. 185:
[...] Los resultados de este artículo se presentan en el libro más disponible de SH Caldwell [...]. En este libro, el autor da crédito a Mullin y Kellner por el desarrollo de las manipulaciones con los números decimales.
(1 pagina) - ^ Abrahams, Paul William; Nordahl, John "Jack" G. (noviembre de 1955). El procedimiento de reducción de Quine-McCluskey modificado (memorando de la clase). Departamento de Ingeniería Eléctrica, Instituto Tecnológico de Massachusetts , Massachusetts, EE. UU.(4 páginas) (NB. Algunas fuentes enumeran a los autores como " PW Abraham " e " IG Nordahl ", el título también se cita como " Procedimiento de reducción McCluskey-Quine modificado ".)
- ^ Fielder, Daniel C. (diciembre de 1966). "Reducción de funciones booleanas en el aula". Transacciones IEEE sobre educación . IEEE . 9 (4): 202-205. Código Bibliográfico : 1966ITEdu ... 9..202F . doi : 10.1109 / TE.1966.4321989 . eISSN 1557-9638 . ISSN 0018-9359 .
- ^ Kämmerer, Wilhelm (mayo de 1969). "I.12. Teoría: Minimierung Boolescher Funktionen". Escrito en Jena, Alemania. En Frühauf, Hans ; Kämmerer, Wilhelm; Schröder, Kurz; Winkler, Helmut (eds.). Automate digital: teoría, estructura, técnica, programación . Elektronisches Rechnen und Regeln (en alemán). 5 (1 ed.). Berlín, Alemania: Akademie-Verlag GmbH . págs. 98, 103-104. Licencia no. 202-100 / 416/69. N º de pedido. 4666 ES 20 K 3. pág. 98:
[...] 1955 wurde das Verfahren auf die bequemere dezimale Schreibweise umgestellt ( PW Abraham und IG Nordahl en [ Caldwell ]). [...]
(NB. También existe una segunda edición de 1973). - ^ Holdsworth, Brian; Woods, Clive (2002). "3.17 enfoque decimal a la simplificación de Quine-McCluskey del álgebra de Boole" . Diseño de lógica digital (4 ed.). Libros de Newnes / Ciencia de Elsevier . págs. 65–67. ISBN 0-7506-4588-2. Consultado el 19 de abril de 2020 .Mantenimiento de CS1: errores de ISBN ignorados ( enlace )(519 páginas) [5]
- ^ Majumder, Alak; Chowdhury, Barnali; Mondal, Abir J .; Jain, Kunj (30 de enero de 2015) [9 de enero de 2015]. Investigación sobre el método de Quine McCluskey: un nuevo enfoque basado en la manipulación decimal para la minimización de la función booleana . 2015 Conferencia internacional sobre diseño electrónico, redes informáticas y verificación automatizada (EDCAV), Shillong, India (documento de conferencia). Departamento de Electrónica y Comunicación, Instituto Nacional de Tecnología de Ingeniería, Arunachal Pradesh Yupia, India. págs. 18-22. doi : 10.1109 / EDCAV.2015.7060531 . Archivado desde el original el 8 de mayo de 2020 . Consultado el 8 de mayo de 2020 . [6] (NB. Este trabajo no cita el estado de la técnica sobre métodos decimales) (5 páginas)
- ^ Masek, William J. (1979). Algunos problemas de cobertura de conjunto NP-completo . inédito.
- ^ Czort, Sebastian Lukas Arne (1999). La complejidad de minimizar las fórmulas disyuntivas de forma normal (tesis de maestría). Universidad de Aarhus.
- ^ Umans, Christopher ; Villa, Tiziano; Sangiovanni-Vincentelli, Alberto Luigi (5 de junio de 2006). "Complejidad de la minimización lógica de dos niveles". Transacciones IEEE sobre diseño asistido por computadora de circuitos y sistemas integrados . 25 (7): 1230-1246. doi : 10.1109 / TCAD.2005.855944 . S2CID 10187481 .
- ^ Nelson, Victor P .; Nagle, H. Troy; Carroll, Bill D .; Irwin, J. David (1995). Análisis y diseño de circuitos lógicos digitales (2 ed.). Prentice Hall . pag. 234. ISBN 978-0-13463894-2. Consultado el 26 de agosto de 2014 .
- ^ Feldman, Vitaly (2009). "Dureza de la minimización lógica aproximada de dos niveles y aprendizaje PAC con consultas de membresía". Revista de Ciencias de la Computación y Sistemas . 75 : 13-25 [13-14]. doi : 10.1016 / j.jcss.2008.07.007 .
- ^ Gimpel, James F. (1965). "Un método para producir una función booleana que tiene una tabla implícita primaria prescrita arbitraria". Transacciones IEEE en computadoras . 14 : 485–488. doi : 10.1109 / PGEC.1965.264175 .
- ^ Paul, Wolfgang Jakob (1974). "Boolesche Minimalpolynome und Überdeckungsprobleme". Acta Informatica (en alemán). 4 (4): 321–336. doi : 10.1007 / BF00289615 . S2CID 35973949 .
- ^ Programa Logic Friday
Otras lecturas
- Curtis, Herbert Allen (1962). "Capítulo 2.3. Método de McCluskey". Un nuevo enfoque para el diseño de circuitos de conmutación . The Bell Laboratories Series (1 ed.). Princeton, Nueva Jersey, Estados Unidos: D. van Nostrand Company, Inc. págs. 90–160. ISBN 0-44201794-4. OCLC 1036797958 . S2CID 57068910 . ISBN 978-0-44201794-1 . arca: / 13960 / t56d6st0q. (viii + 635 páginas) (NB. Este libro fue reimpreso por Chin Jih en 1969.)
- Coudert, Olivier (octubre de 1994). "Minimización lógica de dos niveles: una descripción general" (PDF) . Integración, el VLSI Journal . 17–2 (2): 97–140. doi : 10.1016 / 0167-9260 (94) 00007-7 . ISSN 0167-9260 . Archivado (PDF) desde el original el 10 de mayo de 2020 . Consultado el 10 de mayo de 2020 . (47 páginas)
- Jadhav, Vitthal; Buchade, Amar (8 de marzo de 2012). "Método de Quine-McCluskey modificado". arXiv : 1203,2289 [ cs.OH ]. (4 páginas)
- Crenshaw, Jack (19 de agosto de 2004). "Todo sobre Quine-McClusky" . embedded.com . Archivado desde el original el 10 de mayo de 2020 . Consultado el 10 de mayo de 2020 .
- Tomaszewski, Sebastian P .; Celik, Ilgaz U .; Antoniou, George E. (diciembre de 2003) [2005-03-05, 2002-04-09]. "Minimización de la función booleana basada en WWW" (PDF) . Revista Internacional de Matemática Aplicada e Informática . 13 (4): 577–584. Archivado (PDF) desde el original el 10 de mayo de 2020 . Consultado el 10 de mayo de 2020 . [7] [8] (7 páginas)
- Duşa, Adrian (2008-10-01) [septiembre de 2007]. "Una aproximación matemática al problema de minimización booleana". Calidad y cantidad . 44 : 99-113. doi : 10.1007 / s11135-008-9183-x . S2CID 123042755 . Número de artículo: 99 (2010). [9] (22 páginas)
- Duşa, Adrian (2007). "Mejora de Quine-McCluskey" (PDF) . Universidad de Bucarest . Archivado (PDF) desde el original el 12 de mayo de 2020 . Consultado el 12 de mayo de 2020 .(16 páginas) (NB. QCA , una implementación de código abierto basada en R utilizada en las ciencias sociales).
enlaces externos
- Implementación del algoritmo Quine-McCluskey con búsqueda de todas las soluciones , por Frédéric Carpon.
- Karċma 3 , un conjunto de herramientas de síntesis lógica que incluyen mapas de Karnaugh, minimización de Quine-McCluskey, BDD, probabilidades, módulo de enseñanza y más. Laboratorios de Síntesis de Circuitos Lógicos (LogiCS) - UFRGS , Brasil.
- BFunc , simplificadores lógicos booleanos basados en QMC que admiten hasta 64 entradas / 64 salidas (independientemente) o 32 salidas (simultáneamente), de António Costa
- Implementación de Python por Robert Dick, con una versión optimizada .
- Implementación de Python para reducir simbólicamente expresiones booleanas.
- Quinessence , una implementación de código abierto escrita en Free Pascal por Marco Caminati.
- minBool una implementación de Andrey Popov.
- Applet QMC , un applet para un análisis paso a paso del algoritmo QMC- por Christian Roth
- Implementación de C ++ Programa C ++ de SourceForge.net que implementa el algoritmo.
- Módulo Perl de Darren M. Kulp.
- Tutorial Tutorial sobre el método de Quine-McCluskey y Petrick.
- Implementación de Petrick C ++ (incluido Petrick) basada en el tutorial anterior.
- Programa C Programa C basado en consola de dominio público en SourceForge.net.
- Para ver un ejemplo completamente elaborado, visite: http://www.cs.ualberta.ca/~amaral/courses/329/webslides/Topic5-QuineMcCluskey/sld024.htm
- El bot booleano: una implementación de JavaScript para la web: http://booleanbot.com/
- minimizador de código abierto GUI QMC
- Códigos de simulación por computadora para el método Quine-McCluskey , por Sourangsu Banerji.