Generalized Post embedding problems

DOI10.1007/s00224-014-9561-9zbMath1316.03020arXiv1109.1691OpenAlexW3104597505MaRDI QIDQ2354596

Prateek Karandikar, Philippe Schnoebelen

Publication date: 20 July 2015

Published in: Theory of Computing Systems, Computer Science – Theory and Applications (Search for Journal in Brave)

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

zbMATH Keywords

well-quasi-orderingcomputabilityPost's correspondence problemchannel systemsPost's embedding problemsubwords and Higman's lemma

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Recursively (computably) enumerable sets and degrees (03D25)

Related Items (4)

On Arch Factorization and Subword Universality for Words and Compressed Words ⋮ Well-Quasi Orders and Hierarchy Theory ⋮ Complexity Hierarchies beyond Elementary ⋮ Generalized Post embedding problems

Cites Work

• Unnamed Item
• On deterministic finite automata and syntactic monoid size
• Using forward reachability analysis for verification of lossy channel systems
• Unreliable channels are easier to verify than perfect channels
• Verifying programs with unreliable channels
• Computable fixpoints in well-structured symbolic model checking
• Generalized Post embedding problems
• The theory of well-quasi-ordering: a frequently discovered concept
• Complexity Hierarchies beyond Elementary
• Graph Logics with Rational Relations
• Unidirectional Channel Systems Can Be Tested
• Multiply-Recursive Upper Bounds with Higman’s Lemma
• Mixing Lossy and Perfect Fifo Channels
• On the Reachability Analysis of Acyclic Networks of Pushdown Systems
• Computing Blocker Sets for the Regular Post Embedding Problem
• Pumping and Counting on the Regular Post Embedding Problem
• The Parametric Ordinal-Recursive Complexity of Post Embedding Problems
• Alternating timed automata
• Context-Bounded Analysis of Concurrent Queue Systems
• The ω-Regular Post Embedding Problem
• Post Embedding Problem Is Not Primitive Recursive, with Applications to Channel Systems
• Automata, Languages and Programming
• Foundations of Software Science and Computation Structures
• Well-structured transition systems everywhere!

This page was built for publication: Generalized Post embedding problems