Undecidability and finite automata

Jörg Endrullis, Jeffrey Shallit, Tim Smith

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

Fingerprint

Undecidability
Finite Automata
Finite automata
Rewriting
Decision problem

Keywords

  • Conjugate
  • Finite automata
  • Power
  • Undecidability

Cite this

Endrullis, J., Shallit, J., & Smith, T. (2017). Undecidability and finite automata. In Developments in Language Theory - 21st International Conference, DLT 2017, Proceedings (Vol. 10396 LNCS, pp. 160-172). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10396 LNCS). Springer/Verlag. https://doi.org/10.1007/978-3-319-62809-7_11
Endrullis, Jörg ; Shallit, Jeffrey ; Smith, Tim. / Undecidability and finite automata. Developments in Language Theory - 21st International Conference, DLT 2017, Proceedings. Vol. 10396 LNCS Springer/Verlag, 2017. pp. 160-172 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{c21a63961fc1464ab3b7aacf5ff10e98,
title = "Undecidability and finite automata",
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.",
keywords = "Conjugate, Finite automata, Power, Undecidability",
author = "J{\"o}rg Endrullis and Jeffrey Shallit and Tim Smith",
year = "2017",
doi = "10.1007/978-3-319-62809-7_11",
language = "English",
isbn = "9783319628080",
volume = "10396 LNCS",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer/Verlag",
pages = "160--172",
booktitle = "Developments in Language Theory - 21st International Conference, DLT 2017, Proceedings",

}

Endrullis, J, Shallit, J & Smith, T 2017, Undecidability and finite automata. in Developments in Language Theory - 21st International Conference, DLT 2017, Proceedings. vol. 10396 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10396 LNCS, Springer/Verlag, pp. 160-172, 21st International Conference on Developments in Language Theory, DLT 2017, Liege, Belgium, 7/08/17. https://doi.org/10.1007/978-3-319-62809-7_11

Undecidability and finite automata. / Endrullis, Jörg; Shallit, Jeffrey; Smith, Tim.

Developments in Language Theory - 21st International Conference, DLT 2017, Proceedings. Vol. 10396 LNCS Springer/Verlag, 2017. p. 160-172 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10396 LNCS).

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

TY - GEN

T1 - Undecidability and finite automata

AU - Endrullis, Jörg

AU - Shallit, Jeffrey

AU - Smith, Tim

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

KW - Conjugate

KW - Finite automata

KW - Power

KW - Undecidability

UR - http://www.scopus.com/inward/record.url?scp=85026786635&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85026786635&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-62809-7_11

DO - 10.1007/978-3-319-62809-7_11

M3 - Conference contribution

SN - 9783319628080

VL - 10396 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 160

EP - 172

BT - Developments in Language Theory - 21st International Conference, DLT 2017, Proceedings

PB - Springer/Verlag

ER -

Endrullis J, Shallit J, Smith T. Undecidability and finite automata. In Developments in Language Theory - 21st International Conference, DLT 2017, Proceedings. Vol. 10396 LNCS. Springer/Verlag. 2017. p. 160-172. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-62809-7_11