From decidability to undecidability by considering regular sets of instances

DOI10.1016/j.tcs.2021.11.006OpenAlexW3113708318MaRDI QIDQ2062120

Petra Wolf

Publication date: 22 December 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1906.08027

zbMATH Keywords

undecidabilitydeterministic finite automatonregular intersection emptiness problem

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

On the decidability of finding a positive ILP-instance in a regular set of ILP-instances

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On regular realizability problems for context-free languages
• On regular realizability problems
• A survey of graph edit distance
• Detecting palindromes, patterns and borders in regular languages
• Automata accepting primitive words
• The Post correspondence problem over a unary alphabet
• Deciding regular intersection emptiness of complete problems for PSPACE and the polynomial hierarchy
• The synthesis problem of Petri nets
• On expressive power of regular realizability problems
• Phase transitions and the search problem
• Orbits of Linear Maps and Regular Languages
• On Models of a Nondeterministic Computation
• The Hardest Context-Free Language
• On the Undecidability of the Tiling Problem
• Phase Transitions in Combinatorial Optimization Problems
• Regular Realizability Problems and Context-Free Languages
• Properties of graphs specified by a regular language
• On the decidability of finding a positive ILP-instance in a regular set of ILP-instances

This page was built for publication: From decidability to undecidability by considering regular sets of instances