Multipass automata and group word problems
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2014
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911826650857472 |
|---|---|
| author | Ceccherini-Silberstein, Tullio Coornaert, Michel Fiorenzi, Francesca Schupp, Paul E. Touikan, Nicholas W. M. |
| author_facet | Ceccherini-Silberstein, Tullio Coornaert, Michel Fiorenzi, Francesca Schupp, Paul E. Touikan, Nicholas W. M. |
| contents | We introduce the notion of multipass automata as a generalization of pushdown automata and study the classes of languages accepted by such machines. The class of languages accepted by deterministic multipass automata is exactly the Boolean closure of the class of deterministic context-free languages while the class of languages accepted by nondeterministic multipass automata is exactly the class of poly-context-free languages, that is, languages which are the intersection of finitely many context-free languages. We illustrate the use of these automata by studying groups whose word problems are in the above classes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1404_7442 |
| institution | arXiv |
| publishDate | 2014 |
| record_format | arxiv |
| spellingShingle | Multipass automata and group word problems Ceccherini-Silberstein, Tullio Coornaert, Michel Fiorenzi, Francesca Schupp, Paul E. Touikan, Nicholas W. M. Group Theory Formal Languages and Automata Theory 03B25, 05C05, 37B10, 37B15, 68Q70, 68Q80 We introduce the notion of multipass automata as a generalization of pushdown automata and study the classes of languages accepted by such machines. The class of languages accepted by deterministic multipass automata is exactly the Boolean closure of the class of deterministic context-free languages while the class of languages accepted by nondeterministic multipass automata is exactly the class of poly-context-free languages, that is, languages which are the intersection of finitely many context-free languages. We illustrate the use of these automata by studying groups whose word problems are in the above classes. |
| title | Multipass automata and group word problems |
| topic | Group Theory Formal Languages and Automata Theory 03B25, 05C05, 37B10, 37B15, 68Q70, 68Q80 |
| url | https://arxiv.org/abs/1404.7442 |