Partially-commutative context-free graphs

Niniejsza rozprawa dotyczy rozszerzenia gramatyk bezkontekstowych o częściową przemienność symboli nieterminalnych. W szczególności badamy podklasę, w której relacja zależności jest przechodnia oraz odpowiadający model automatu: bezstanowy automat wielostosowy. Rezultaty są podzielone na trzy rozdziały. Rozdział pierwszy bada wyrażalność językową rozważanych klas. Główny wynik pokazuje, że wyrażalność językowa analizowanych klas oraz dwóch innych, dobrze znanych klas rozszerzających języki bezkontekstowe o zachowania współbieżne, jest nieporównywalna. Pierwsza z tych klas to domknięcia języków bezkontekstowych ze względu na relację przemienności na terminalach. Druga to języki generowane przez gramatyki bezkontekstowe z operacją przeplotu. Ostatnie dwa rozdziały koncentrują się na grafach konfiguracji częściowo przemiennych gramatyk bezkontekstowych. Rozdział drugi rozważa problem osiągalności dla słabych automatów wielostosowych, uogólnienia bezstanowych automatów wielostosowych. Spośród wielu rezultatów przedstawionych w tym rozdziale najważniejsze są NP-zupełność dla bezstanowych automatów wielostosowych oraz rozstrzygalność dla słabych automatów wielostosowych. Ostatni rozdział prezentuje algorytm wielomianowy rozstrzygający równoważność bisy- mulacyjną w podklasie częściowo przemiennych grafów bezkontekstowych uogólniającej zarówno grafy bezkontekstowe jak i przemienne grafy bezkontekstowe. Uszczegółowiony algorytm dla klasy grafów bezkontekstowych ma złożoność czasową O(N^4 polylog(N)) i jest najszybszym aktualnie znanym. Dodatkowo uzyskaliśmy ograniczenie górne O(N^3 polylog(N)) w szczególnym przypadku gramatyk prostych.

This thesis is about an extension of context-free grammars with partial commutation on nonterminal symbols. In particular, we investigate the subclass with transitive dependence relation and the corresponding automaton model: stateless multi-pushdown automata. The results of the thesis are divided into three chapters. The first chapter investigates language expressivity of concerned classes. Roughly speaking, the main result states that in terms of expressivity, partially-commutative context-free languages are incomparable with two other well-known classes of languages extending context-free languages by a concurrent behaviour. One of these classes is trace closure of context-free languages. The other one is languages generated by context-free grammars with shuffle. The last two chapters concentrate on configuration graphs of partially-commutative context-free grammars rather than on the languages. The second chapter investigates reachability problem for weak multi-pushdown automata, a generalisation of stateless multi-pushdown automata. Among multiple results discussed in this chapter, the most important ones are NP-completeness for stateless multi-pushdown automata and decidability for weak multi-pushdown automata. The last chapter presents a polynomial-time algorithm deciding bisimilarity in a subclass of partially-commutative context-free graphs that subsumes both context-free graphs and commutative context-free graphs. A specialisation of the algorithm to the class of context- free graphs works in time O(N^4 polylog(N)), which is the fastest currently known. Finally, we obtain O(N^3 polylog(N)) upper bound in the special case of simple grammars.