Undecidability and finite automata

Jörg Endrullis, Jeffrey Shallit*, Tim Smith

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

Using a novel rewriting problem, we show that several natural decision problems about finite automata are undecidable (i.e., recursively unsolvable). In contrast, we also prove three related problems are decidable. We apply one result to prove the undecidability of a related problem about k-automatic sets of rational numbers.

Original languageEnglish
Title of host publicationDevelopments in Language Theory - 21st International Conference, DLT 2017, Proceedings
PublisherSpringer/Verlag
Pages160-172
Number of pages13
Volume10396 LNCS
ISBN (Print)9783319628080
DOIs
Publication statusPublished - 2017
Event21st International Conference on Developments in Language Theory, DLT 2017 - Liege, Belgium
Duration: 7 Aug 201711 Aug 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10396 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference21st International Conference on Developments in Language Theory, DLT 2017
CountryBelgium
CityLiege
Period7/08/1711/08/17

Keywords

  • Conjugate
  • Finite automata
  • Power
  • Undecidability

Fingerprint Dive into the research topics of 'Undecidability and finite automata'. Together they form a unique fingerprint.

Cite this