Calcul de l'intersection de deux NPDA là où c'est possible

Apropois à la suggestion de Raphaël sur l' intersection de deux NPDA :

Soit et NPDA pour les langues sans contexte et , respectivement. En supposant que nous savons que est sans contexte, pouvons-nous (effectivement) construire NPDA pour ? $A_1$ $A_2$ $L_1$ $L_2$ $L = L_1 \cap L_2$ $A$ $L$

Tout type d'algorithme serait acceptable, mais le plus pratique sera le mieux.

computability automata pushdown-automata soandos
la source

un exemple d'un tel L où ni L1 / L2 ne sont réguliers et l'intersection n'est pas vide pourrait être utile, un tel L existe-t-il? des problèmes quelque peu similaires aux NPDA (test de la vacuité de l'intersection, test de l'égalité) sont indécidables. suggérer de migrer / promouvoir vers tcs.se si aucune réponse ne se matérialise

vzn

@vzn Je crois avoir un exemple d'état ~ 50, je vais essayer de trouver quelqu'un qui est plus minimal

soandos

{0, 1}

$\{0,1\}$

@sjmc pouvez-vous esquisser une preuve? pas évident pour moi. votera positivement si vous le postez comme réponse même si sa réponse n'est pas complète, sa progression

vzn

mettre à jour cela semble être répondu comme indécidable à tcs.se sur la base du fait que le calcul arbitraire de la MT peut être exprimé comme l'intersection de deux CFL.

vzn

Réponses:

Je pense que cela est possible pour la sous-classe des LFC qui sont invariantes par permutation avec un alphabet binaire.

$\langle 1,1\rangle$

L'ensemble semi-linéaire qui est leur intersection pourrait être un peu difficile à calculer ... mais, si vous en avez un, [3] (pgs.11-12) donne un algorithme pour créer un NPDA acceptant le langage basé sur les générateurs de la ensemble semi-linéaire correspondant.

[1] Makoto Kanazawa. Quantiers monadiques reconnus par des automates déterministes déroulants . Dans Actes du 19e Colloque d'Amsterdam, pages 139-146, 2013.

[2] Johann van Benthem. Essais en sémantique logique . Studies in Linguistics and Philosophy Volume 29, 1986, pp 151-176.

[3] Marcin Mostowski. Sémantique informatique pour les quantiers monadiques . Journal of Applied Non-Classical Logics, 8 (1-2): 107-121, 1998.

sjmc
la source