Finite bases for semigroup varieties

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorAraújo, João-
Autor(es): dc.contributorLee, Edmond W. H.-
Autor(es): dc.creatorPereira, Manuel Jorge Raminhos-
Data de aceite: dc.date.accessioned2022-02-15T14:07:47Z-
Data de disponibilização: dc.date.available2022-02-15T14:07:47Z-
Data de envio: dc.date.issued2021-01-19-
Data de envio: dc.date.issued2020-07-01-
Data de envio: dc.date.issued2021-01-19-
Data de envio: dc.date.issued2023-07-01-
Fonte completa do material: dc.identifierhttp://hdl.handle.net/10400.2/10426-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/10400.2/10426-
Descrição: dc.descriptionO objetivo deste trabalho é fornecer um atlas das bases de identidades para as variedades geradas por semigrupos e grupos de ordem pequena. Com o propósito de auxiliar os matemáticos que trabalham neste campo a encontrar informações com facilidade, foi implementado um website que executa em segundo plano um conjunto de algoritmos desenvolvidos no âmbito deste trabalho e ainda ferramentas de demonstração automática e construtores de modelos finitos, para que o utilizador tenha um guia automático e inteligente. Por exemplo, o site fornece a primeira lista completa de variedades geradas por semigrupos de ordens iguais ou inferiores a 5, e consegue identificar rapidamente se a variedade gerada por um semigrupo inserido pelo utilizador, mesmo para ordens bastante superiores, coincide com uma das 218 variedades presentes na base de dados (atualmente inclui ainda outras 11 variedades geradas por semigrupos de ordens superiores). O site também fornece bases de identidades para classes arbitrariamente grandes de semigrupos, como bandas, ou a identificação dos semigrupos de ordem 6 conhecidos que geram variedades de base não finita. Além desta base de dados, o site propõe ainda uma lista das variedades geradas pelos semigrupos de ordem 6, num total de 414 conjeturas para novas variedades, entre as 463 identificadas neste trabalho e retirando as 49 variedades já conhecidas. O site disponibiliza ainda a informação para variedades geradas pelos grupos de ordens iguais ou inferiores a 255, obtida em resultado do levantamento e análise da literatura existente sobre as variedades geradas por estes grupos, para um total de 7012 grupos. O tratamento da informação recolhida para variedades geradas por grupos foi efetuado em GAP e através do desenvolvimento de algoritmos específicos para grupos comutativos e grupos metabelianos, nomeadamente para obtenção das identidades especificas de cada grupo, quando possível. O site oferece ainda um conjunto de funções sobre semigrupos, como encontrar o mínimo lexicográfico das cópias isomórficas de um dado semigrupo. Em relação à propriedade de base inerentemente não finita, o site pode decidir se um determinado semigrupo finito possui ou não essa propriedade; calcular a decomposição do semigrupo em semireticulados; ou converter a sintaxe da tabela de multiplicação de um semigrupo para utilização no GAP ou num demonstrador automático de teoremas/construtor de modelos finitos. O site fornece algumas outras funcionalidades, como uma ferramenta que gera a tabela de multiplicação de um semigrupo fornecida por uma apresentação em C, onde C ´e qualquer classe de álgebras definida por um conjunto de fórmulas em predicados de primeira ordem. A operação no sentido inverso também está acessível. O site disponibiliza um conjunto de informações e funcionalidades sobre variedades e as suas bases de identidades, como apresentar todas as inclusões entre as variedades da base de dados (variedades que são sub-variedades de outras variedades, que as contem) em formato gráfico, identificar se a variedade gerada por um semigrupo coincide com uma existente na base de dados, ou identificar a variedade cuja base é equivalente ao conjunto de identidades inseridas pelo utilizador. O site consegue ainda listar todas as variedades da base dados cujas bases de identidades implicam ou são implicadas por um conjunto de identidades definidas pelo utilizador. Neste cálculo o site leva em conta o conhecimento prévio de todas as inclusões entre variedades acima referidas para acelerar o cálculo e minimizar o uso do demonstrador automático de teoremas/construtor de modelos finitos. No desenvolvimento deste site foram utilizados: na implementação de algoritmos no servidor, Python, substituído pela versão compilada Cython em todos os cálculos intensivos; no desenvolvimento da interface cliente, JavaScript, JQuery, Ajax, Flask, HTML5, CSS3, Bootstrap e MathJax; em bases de dados relacionais, MySQL e SQLAlchemy; na preparação da informação presente nas bases de dados: GAP-System e em particular os “packages” smallsemi e smallgroups; na demonstração automática de teoremas e construção de modelos finitos, Prover9 e Mace4; na apresentação de diagramas, Graphviz. Foi desenvolvido um extenso conjunto de algoritmos reutilizáveis, para manipulação de variedades, semigrupos e grupos, organizados em bibliotecas, destacando-se: varlib.pyx – Implementa os algoritmos de cálculo intensivo do site, como o algoritmo que encontra o mínimo lexicográfico das cópias isomorfas de um dado semigrupo, ou o que verifica se um dado semigrupo satisfaz a base de identidades de uma das variedades na base de dados, e não satisfaz as identidades que definem as sub-variedades maximais. Por questões de velocidade, não existe nesta biblioteca recurso a demonstradores automáticos de teoremas ou a construtores de modelos finitos, sendo a sua funcionalidade substituída por algoritmos desenvolvidos otimizados para identidades, correndo nesta biblioteca a uma velocidade tipicamente 1000x superior ao mesmo programa em Python interpretado; p9m4tools.py – Implementa os algoritmos que recorrem ao demonstrador automático de teoremas e construtor de modelos finitos, embora em ´ultimo recurso, por questões de desempenho, através da implementação de diversas técnicas de “cache”. Nesta biblioteca estão por exemplo os algoritmos desenvolvidos para obter um semigrupo e a sua tabela de multiplicação a partir de uma apresentação, e filtrar as variedades cuja bases de identidades implicam, são implicadas por, ou são equivalentes a um conjunto de identidades entradas pelo utilizador; vartools.py – Implementa rotinas de menor exigência computacional, como a interpretação da entrada de dados do utilizador (por exemplo tabelas de multiplicação em diversos formatos à escolha do utilizador) e a formatação dos dados a apresentar, quer em texto que de forma gráfica. Esta biblioteca inclui ainda diversos algoritmos sobre semigrupos, como a decomposição em semireticulados. Este trabalho também contribui para a extensão da base de dados de variedades conhecidas: existem 28634 semigrupos de ordem 6, considerados equivalentes quando isomorfos ou anti-isomorfos. As variedades de 2035 desses semigrupos não coincidem com nenhuma variedade conhecida gerada por semigrupos de ordem até 5. Neste projeto, com base no teorema de Birkhoff e aplicando novos algoritmos de computador e uma ferramenta de demonstração automática de teoremas/construtor de modelo finitos, foi possível dividir esses 2035 semigrupos em 463 conjuntos de semigrupos que satisfazem as mesmas identidades, correspondendo a 414 novas variedades propostas (dado que são já conhecidas 45 variedades de base finita e 4 variedades de base não finita, geradas por semigrupos da ordem 6). Além disso, as identidades candidatas para a bases de identidades para todas estas novas variedades também são propostas e apresentadas nesta tese, acompanhadas por todas as tabelas de Cayley e os IDs no “package” GAPs smallsemi correspondentes, para cada conjunto de semigrupos encontrados que geram a mesma variedade conjeturada. As provas dessas novas variedades representam problemas em aberto e um desafio para todos os matemáticos nesta área. A mesma metodologia pode ser utilizada para encontrar novas variedades candidatas geradas por semigrupos de ordem 7 ou maior (no âmbito deste trabalho foram encontrados 73807 semigrupos não isomorfos de ordem 7 cujas variedades não coincidem com as variedades registadas na base de dados do site). Esta tese começa com um artigo 1 de pesquisa sobre variedades de semigrupos que contém a maior parte do conteúdo matemático desta tese. Este trabalho representa diversas contribuições para o campo do estudo das variedades de semigrupos: pela primeira vez foi reunida a informação dispersa sobre todas as variedades geradas por semigrupos de ordem igual ou inferior a 5, e relativa aos grupos de ordem igual ou inferior a 255, sendo apresentada num site de fácil utilização. O site oferece ainda um conjunto de funcionalidades sobre semigrupos e sobre variedades da base de dados, alicerçadas num conjunto de algoritmos desenvolvidos para maximização da performance e integrando uma interface, transparente para o utilizador, com um demonstrador automático de teorema e um construtor de modelos finitos, funcionando em paralelo para resultados mais rápidos. Adicionalmente, este trabalho contribuiu para o enriquecimento da base de dados de variedades geradas por semigrupos, ao propor conjeturas para todas as variedades não conhecidas geradas por semigrupos de ordem 6 e respetivas bases de identidades. As principais limitações deste trabalho estão relacionadas com o fato de alguns dos algoritmos desenvolvidos exigirem uma utilização intensiva de recursos computacionais (memória e processador). Estes algoritmos, ou não são adequados para colocação no site (como a pesquisa de novas variedades e respetivas bases), ou exigem limitações dos parâmetros de entrada (por exemplo o cálculo do mínimo lexicográfico, a geração de semigrupos a partir de apresentações, e a identificação de variedades, estão limitados a semigrupos de ordem inferior ou igual a, respetivamente, 10, 20 e 100). Noutras situações, embora raras, o site pode atingir o limite de memória permitido a cada utilizador. Este trabalho inspirou um alargado conjunto de ideias para trabalho futuro, e a primeira consiste na criação de um “package” GAP. Além de oferecer tudo o que site oferece e sem as limitações de memória e processador do site, o utilizador pode realizar múltiplas operações de forma automática. Na realidade o grosso do trabalho está pronto, já que este “package” se pode materializar apenas com o desenvolvimento de uma pequena camada de interface de comandos GAP, já que todos os algoritmos do site estão em bibliotecas autónomas e prontos para ser invocados por qualquer programa externo (aliás o acesso pelo GAP a rotinas das bibliotecas do site foi testado com sucesso no âmbito deste trabalho). Outras ideias para trabalho futuro passam por estender a procura de variedades `as variedades geradas por semigrupos de ordem 7; melhorar os algoritmos atuais para propor também as identidades que definem as sub-variedades maximais; automatizar a demonstração das variedades conjeturadas; desenvolver uma interface no site que permita a extensão da base de dados com novas variedades pelos matemáticos; aumentar as funcionalidades sobre variedades de grupos; desenvolver novo algoritmo para acelerar o cálculo do mínimo lexicográfico.-
Descrição: dc.descriptionThe aim of this work was to provide an atlas of identity bases for varieties generated by small semigroups and groups. To help the working mathematician easily find information, a website was implemented, running in the background automated reasoning tools and finite model builders, so that the user has an automatic intelligent guide on the literature. For instance, the site provide the first complete the list of varieties generated by a semigroup of order up to 5. The website also provides identity bases for several types of semigroups or groups, such as bands, commutative groups, and metabelian groups. Regarding the inherent non-finite basis property, the website can decide whether or not a given finite semigroup possesses this property. The site provides some other functionalities such as a tool that outputs the multiplication table of a semigroup given by a C-presentation, where C is any class of algebras defined by a set of first order formulas. The inverse conversion is also available. This work also gives a contribution to the extension of the database of known varieties: there are 28634 nonisomorphic semigroups of order 6. The varieties of 2035 of these semigroups do not coincide to any known variety generated by semigroups of order up to 5. In this project, building on the Birkhoff theorem and applying new computer algorithms and automatic theorem proving, it was possible to divide these 2035 semigroups into 463 sets of semigroups that satisfy the same identities, corresponding to 414 new proposed varieties (since there are 45 known finitely-based and 4 known non-finitely based varieties generated by semigroups of order 6). Additionally, candidate identities for the identity basis for all these new varieties are also proposed and presented in this thesis, accompanied by all Cayley tables and the corresponding GAP smallsemi package IDs in each set of semigroups found. The proofs of these new varieties represent open problems and a challenge to all mathematicians in this field. The same methodology can be extended to find new candidate varieties generated by semigroups of order 7 or larger (within this work were found 73807 nonisomorphic semigroups of order 7 whose varieties do not coincide with known varieties registered in the site database).-
Idioma: dc.languageen-
Direitos: dc.rightsembargoedAccess-
Palavras-chave: dc.subjectVariedades de semigrupos-
Palavras-chave: dc.subjectÁlgebra computacional-
Palavras-chave: dc.subjectDemonstração automática de teoremas-
Palavras-chave: dc.subjectEnumeração combinatória-
Palavras-chave: dc.subjectBiblioteca de Dados-
Palavras-chave: dc.subjectGrupos-
Palavras-chave: dc.subjectSemigrupos-
Palavras-chave: dc.subjectInteração-
Palavras-chave: dc.subjectVisualização-
Palavras-chave: dc.subjectGráficos-
Palavras-chave: dc.subjectProver9-
Palavras-chave: dc.subjectMace4-
Palavras-chave: dc.subjectMatemática-
Palavras-chave: dc.subjectGAP-
Palavras-chave: dc.subjectSemigroup varieties-
Palavras-chave: dc.subjectComputer algebra-
Palavras-chave: dc.subjectAutomatic theorem proving-
Palavras-chave: dc.subjectEnumerative combinatorics-
Palavras-chave: dc.subjectComputer search-
Palavras-chave: dc.subjectData library-
Palavras-chave: dc.subjectGroups-
Palavras-chave: dc.subjectSemigroups-
Palavras-chave: dc.subjectInteraction-
Palavras-chave: dc.subjectVisualization-
Palavras-chave: dc.subjectGraphics-
Palavras-chave: dc.subjectMathematics-
Palavras-chave: dc.subjectProver9/Mace4-
Palavras-chave: dc.subjectODS::04:Educação de Qualidade-
Palavras-chave: dc.subjectODS::09:Indústria, Inovação e Infraestruturas-
Título: dc.titleFinite bases for semigroup varieties-
Tipo de arquivo: dc.typelivro digital-
Aparece nas coleções:Repositório Aberto - Universidade Aberta (Portugal)

Não existem arquivos associados a este item.