Inclusion is undecidable for pattern languages

DOI10.1007/3-540-56939-1_81zbMath1422.68152OpenAlexW1540862879MaRDI QIDQ4630269

Tao Jiang, Kai Salomaa, Arto Salomaa, Sheng Yu

Publication date: 29 March 2019

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-56939-1_81

zbMATH Keywords

decidabilitypattern languagesinclusion problemsequivalence problems

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

From learning in the limit to stochastic finite learning ⋮ Learning unions of tree patterns using queries ⋮ Monotonic and dual monotonic language learning ⋮ Pattern systems ⋮ Undecidability of ground reducibility for word rewriting systems with variables ⋮ Case-based representation and learning of pattern languages ⋮ Learning unions of tree patterns using queries ⋮ Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries ⋮ Learners based on transducers ⋮ Incremental concept learning for bounded data mining.

Cites Work

• Unnamed Item
• Unnamed Item
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• The equivalence problem of multitape finite automata
• Avoidable patterns in strings of symbols
• Finding patterns common to a set of strings
• Learning regular languages from counterexamples
• Reversal-bounded multipushdown machines
• Inductive inference of formal languages from positive data
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Pattern languages with and without erasing