Undecidability and finite automata

Jörg Endrullis; Jeffrey Shallit; Tim Smith

doi:10.1007/978-3-319-62809-7_11

Undecidability and finite automata

Jörg Endrullis, Jeffrey Shallit^*, Tim Smith

^*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

22 Downloads (Pure)

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 language	English
Title of host publication	Developments in Language Theory
Subtitle of host publication	21st International Conference, DLT 2017, Liège, Belgium, August 7-11, 2017, Proceedings
Editors	Émilie Charlier, Julien Leroy, Michel Rigo
Publisher	Springer/Verlag
Pages	160-172
Number of pages	13
ISBN (Electronic)	9783319628097
ISBN (Print)	9783319628080
DOIs	https://doi.org/10.1007/978-3-319-62809-7_11
Publication status	Published - 2017
Event	21st International Conference on Developments in Language Theory, DLT 2017 - Liege, Belgium Duration: 7 Aug 2017 → 11 Aug 2017

Publication series

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

Conference

Conference	21st International Conference on Developments in Language Theory, DLT 2017
Country/Territory	Belgium
City	Liege
Period	7/08/17 → 11/08/17

Keywords

Conjugate
Finite automata
Power
Undecidability

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

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

Undecidability and Finite AutomataFinal published version, 215 KBLicence: Article 25fa Dutch Copyright Act

Persistent URL (handle)

Persistent link

Cite this

Endrullis, J., Shallit, J., & Smith, T. (2017). Undecidability and finite automata. In É. Charlier, J. Leroy, & M. Rigo (Eds.), Developments in Language Theory : 21st International Conference, DLT 2017, Liège, Belgium, August 7-11, 2017, Proceedings (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, Liège, Belgium, August 7-11, 2017, Proceedings. editor / Émilie Charlier ; Julien Leroy ; Michel Rigo. 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",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer/Verlag",

pages = "160--172",

editor = "{\'E}milie Charlier and Julien Leroy and Michel Rigo",

booktitle = "Developments in Language Theory",

note = "21st International Conference on Developments in Language Theory, DLT 2017 ; Conference date: 07-08-2017 Through 11-08-2017",

}

Endrullis, J, Shallit, J & Smith, T 2017, Undecidability and finite automata. in É Charlier, J Leroy & M Rigo (eds), Developments in Language Theory : 21st International Conference, DLT 2017, Liège, Belgium, August 7-11, 2017, Proceedings. 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, Liège, Belgium, August 7-11, 2017, Proceedings. ed. / Émilie Charlier; Julien Leroy; Michel Rigo. 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 proceeding › Conference contribution › Academic › peer-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

AN - SCOPUS:85026786635

SN - 9783319628080

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

A2 - Charlier, Émilie

A2 - Leroy, Julien

A2 - Rigo, Michel

PB - Springer/Verlag

T2 - 21st International Conference on Developments in Language Theory, DLT 2017

Y2 - 7 August 2017 through 11 August 2017

ER -

Endrullis J, Shallit J, Smith T. Undecidability and finite automata. In Charlier É, Leroy J, Rigo M, editors, Developments in Language Theory : 21st International Conference, DLT 2017, Liège, Belgium, August 7-11, 2017, Proceedings. Springer/Verlag. 2017. p. 160-172. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). Epub 2017 Jul 21. doi: 10.1007/978-3-319-62809-7_11

Undecidability and finite automata

Abstract

Publication series

Conference

Keywords

UN SDGs

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this