nach oben

Theory of Computing Systems

Erschienen in:

01.05.2015

Generalized Post Embedding Problems

verfasst von: Prateek Karandikar, Philippe Schnoebelen

Erschienen in: Theory of Computing Systems | Ausgabe 4/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The Regular Post Embedding Problem extended with partial (co)directness is shown decidable. This extends to universal and/or counting versions. It is also shown that combining directness and codirectness in Post Embedding problems leads to undecidability.

Vorheriger Artikel Omega-Rational Expressions with Bounded Synchronization Delay

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

But the problem becomes easy, decidable in linear-time and logarithmic space [8], when restricted to R = Σ⁺ as in PCP.

PEP is undecidable if we allow constraint sets R outside Reg(Σ) [8]. Other extensions, like \(\exists x\in R_{1}:\forall y\in R_{2}:u(xy)\sqsubseteq v(xy)\), for R ₁, R ₂ ∈ Reg(Σ), have been shown undecidable [12].

Abdulla, P.A., Collomb-Annichini, A., Bouajjani, A., Jonsson, B.: Using forward reachability analysis for verification of lossy channel systems. Formal Methods in System Design 25(1), 39–65 (2004). doi:10.1023/B:FORM.0000033962.51898.1a CrossRefMATH

Abdulla, P.A., Deneux, J., Ouaknine, J., Worrell, J.: Decidability and complexity results for timed automata via channel machines. In: Proceedings of ICALP 2005.Lecture Notes in Computer Science, Vol. 3580, pp 1089–1101. Springer (2005), doi:10.1007/11523468_88

Abdulla, P.A., Jonsson, B.: Verifying programs with unreliable channels. Inf. Comput. 127(2), 91–101 (1996). doi:10.1006/inco.1996.0053 CrossRefMATHMathSciNet

Atig, M.F., Bouajjani, A., Touili, T.: On the reachability analysis of acyclic networks of pushdown systems. In: van Breugel, F., Chechik, M. (eds.) , Vol. 5201, pp 356–371. Springer (2008), doi:10.1007/978-3-540-85361-9_29

Barceló, P., Figueira, D., Libkin, L.: Graph logics with rational relations. Logical Methods in Comp. Science 9(3) (2013). doi:10.2168/LMCS-9(3:1)2013

Bertrand, N., Schnoebelen, Ph: Computable fixpoints in well-structured symbolic model checking. Form. Methods Sys. Des. 43(2), 233–267 (2013). doi:10.1007/s10703-012-0168-y CrossRefMATH

Cécé, G., Finkel, A., Purushothaman Iyer, S.: Unreliable channels are easier to verify than perfect channels. Inf. Comput. 124(1), 20–31 (1996). doi:10.1006/inco.1996.0003 CrossRefMATH

Chambart, P., Schnoebelen, Ph.: Post Embedding Problem is not primitive recursive, with applications to channel systems. In: Proceeding of FST & TCS 2007. Lecture Notes in Computer Science, Vol. 4855, pp 265–276. Springer. (2007) doi:10.1007/978-3-540-77050-3_22

Chambart, P., Schnoebelen, Ph.: Mixing lossy and perfect fifo channels. In: Proceeding of CONCUR 2008. Lecture Notes in Computer Science, Vol. 5201, pp 340–355. Springer (2008), doi:10.1007/978-3-540-85361-9_28

10.

Chambart, P., Schnoebelen, Ph.: The ω-Regular Post Embedding Problem. In: Proceeding of FOSSACS 2008,Lecture Notes in Computer Science, Vol. 4962, pp 97–111. Springer (2008), doi:10.1007/978-3-540-78499-9_8

11.

Chambart, P., Schnoebelen, Ph.: The ordinal recursive complexity of lossy channel systems. In: Proceeding of LICS 2008, IEEE Computer Society Press, pp. 205–216 (2008). doi:10.1109/LICS.2008.47

12.

Chambart, P., Schnoebelen, Ph.: Computing blocker sets for the regular Post embedding problem. In: Proceeding for DLT 2010, Lecture Notes in Computer Science, Vol. 6224, pp 136–147. Springer (2010), doi:10.1007/978-3-642-14455-4_14

13.

Chambart, P., Schnoebelen, Ph.: Pumping and counting on the regular Post embedding problem. In: Proceeding of ICALP 2010, Lecture Notes in Computer Science, Vol. 6199, pp 64–75. Springer (2010), doi:10.1007/978-3-642-14162-1_6

14.

Finkel, A., Schnoebelen, Ph.: Well-structured transition systems everywhere. Theor. Comput. Sci. 256(1–2), 63–92 (2001). doi:10.1016/S0304-3975(00)00102-X CrossRefMATHMathSciNet

15.

Holzer, M., König, B.: On deterministic finite automata and syntactic monoid size. Theor. Comput. Sci. 327(3), 319–347 (2004). doi:10.1016/j.tcs.2004.04.010 CrossRefMATH

16.

Jančar, P., Karandikar, P., Schnoebelen, Ph.: Unidirectional channel systems can be tested. In: Proceeding of IFIP TCS 2012, Lecture Notes in Computer Science, Vol. 7604, pp 149–163. Springer (2012), doi:10.1007/978-3-642-33475-7_11

17.

Karandikar, P., Schmitz, S.: The parametric ordinal-recursive complexity of Post embedding problems. In: Proceeding of FOSSACS 2013, Lecture Notes in Computer Science, Vol. 7794, pp 273–288. Springer (2013), doi:10.1007/978-3-642-37075-5_18

18.

Karandikar, P., Schnoebelen, Ph.: Cutting through regular Post embedding problems. In: Proceeding of CSR 2012, Lecture Notes in Computer Science, Vol. 7353, pp 229–240. Springer (2012), doi:10.1007/978-3-642-30642-6_22

19.

Konev, B., Kontchakov, R., Wolter, F., Zakharyaschev, M.: Dynamic topological logics over spaces with continuous functions, Advances in Modal Logic, vol. 6, pp. 299–318. College Publications (2006)

20.

Kruskal, J.B.: The theory of well-quasi-ordering: A frequently discovered concept. J. Comb. Theory, Series A 13(3), 297–305 (1972). doi:10.1016/0097-3165(72)90063-5 CrossRefMATHMathSciNet

21.

Kurucz, A.: Combining modal logics. In: Blackburn, P., Benthem, J.v., Wolter, F. (eds.) Handbook of Modal Logics, vol. 3, chap. 15, pp. 869–926. Elsevier Science (2006). doi:10.1016/S1570-2464(07)80018-8

22.

La Torre, S., Madhusudan, P., Parlato, G.: Context-bounded analysis of concurrent queue systems. In: Proceeding of TACAS 2008, Lecture Notes in Computer Science, Vol. 4963, pp 299–314. Springer (2008), doi:10.1007/978-3-540-78800-3_21

23.

Lasota, S., Walukiewicz, I.: Alternating timed automata. ACM Trans. Comput. Log. 9(2) (2008). doi:10.1145/1342991.1342994

24.

Ouaknine, J., Worrell, J.: On metric temporal logic and faulty Turing machines. In: Proceeding of FOSSACS 2006, Lecture Notes in Computer Science, Vol. 3921, pp 217–230. Springer (2006), doi:10.1007/11690634_15

25.

Schmitz, S.: Complexity hierarchies beyond elementary. Preprint, arXiv:1312.5686 [cs.CC] (2013)

26.

Schmitz, S., Schnoebelen, Ph.: Multiply-recursive upper bounds with Higman’s lemma. In: Proceeding of ICALP 2011, Lecture Notes in Computer Science, Vol. 6756, pp 441–452. Springer (2011), doi:10.1007/978-3-642-22012-8_35

27.

Schmitz, S., Schnoebelen, Ph.: Algorithmic aspects of WQO theory. Lecture notes, http://cel.archives-ouvertes.fr/cel-00727025 (2012)

Titel: Generalized Post Embedding Problems
verfasst von: Prateek Karandikar
Philippe Schnoebelen
Publikationsdatum: 01.05.2015
Verlag: Springer US
Erschienen in: Theory of Computing Systems / Ausgabe 4/2015
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-014-9561-9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 4/2015

Some Results on More Flexible Versions of Graph Motif

On Extracting Space-bounded Kolmogorov Complexity

New Lower Bounds on Circuit Size of Multi-output Functions

Towards Optimal Degree Distributions for Left-Perfect Matchings in Random Bipartite Graphs

Omega-Rational Expressions with Bounded Synchronization Delay

Two-Way Automata Characterizations of L/poly Versus NL

Premium Partner