Item request has been placed! ×
Item request cannot be made. ×
loading  Processing Request

The finiteness of a group generated by a 2-letter invertible-reversible Mealy automaton is decidable

Item request has been placed! ×
Item request cannot be made. ×
loading   Processing Request
Read More Add to Saved list
  • Additional Information
    • Contributors:
      Automates et Applications; Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA); Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS); Natacha Portier and Thomas Wilke
    • Publication Information:
      HAL CCSD
      Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
      Leibniz-Zentrum für Informatik
    • Publication Date:
      2013
    • Subject Terms:
      Kiel; Germany
    • Abstract:
      International audience ; We prove that a semigroup generated by a reversible two-state Mealy automaton is either finite or free of rank 2. This fact leads to the decidability of finiteness for groups generated by two-state or two-letter invertible-reversible Mealy automata and to the decidability of freeness for semigroups generated by two-state invertible-reversible Mealy automata.
    • Relation:
      info:eu-repo/semantics/altIdentifier/arxiv/1208.6324; hal-00875177; https://u-paris.hal.science/hal-00875177; https://u-paris.hal.science/hal-00875177/document; https://u-paris.hal.science/hal-00875177/file/stacs010.klimann.pdf; ARXIV: 1208.6324
    • Accession Number:
      10.4230/LIPIcs.STACS.2013.502
    • Online Access:
      https://doi.org/10.4230/LIPIcs.STACS.2013.502
      https://u-paris.hal.science/hal-00875177
      https://u-paris.hal.science/hal-00875177/document
      https://u-paris.hal.science/hal-00875177/file/stacs010.klimann.pdf
    • Rights:
      info:eu-repo/semantics/OpenAccess
    • Accession Number:
      edsbas.1F291797