Higher-Order Pushdown Systems with Data
We propose a new extension of higher-order pushdown automata, which allows to use an infinite alphabet. The new automata recognize languages of data words (instead of normal words), which beside each its letter from a finite alphabet have a data value from an infinite alphabet. Those data values can...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Open Publishing Association
2012-10-01
|
| Series: | Electronic Proceedings in Theoretical Computer Science |
| Online Access: | http://arxiv.org/pdf/1210.2460v1 |
| _version_ | 1828368900360765440 |
|---|---|
| author | Paweł Parys |
| author_facet | Paweł Parys |
| author_sort | Paweł Parys |
| collection | DOAJ |
| description | We propose a new extension of higher-order pushdown automata, which allows to use an infinite alphabet. The new automata recognize languages of data words (instead of normal words), which beside each its letter from a finite alphabet have a data value from an infinite alphabet. Those data values can be loaded to the stack of the automaton, and later compared with some farther data values on the input. Our main purpose for introducing these automata is that they may help in analyzing normal automata (without data). As an example, we give a proof that deterministic automata with collapse can recognize more languages than deterministic automata without collapse. This proof is simpler than in the no-data case. We also state a hypothesis how the new automaton model can be related to the original model of higher-order pushdown automata. |
| first_indexed | 2024-04-14T06:16:51Z |
| format | Article |
| id | doaj.art-6b56fbb8e9104c49bf421d842f2f41a8 |
| institution | Directory Open Access Journal |
| issn | 2075-2180 |
| language | English |
| last_indexed | 2024-04-14T06:16:51Z |
| publishDate | 2012-10-01 |
| publisher | Open Publishing Association |
| record_format | Article |
| series | Electronic Proceedings in Theoretical Computer Science |
| spelling | doaj.art-6b56fbb8e9104c49bf421d842f2f41a82022-12-22T02:08:10ZengOpen Publishing AssociationElectronic Proceedings in Theoretical Computer Science2075-21802012-10-0196Proc. GandALF 201221022310.4204/EPTCS.96.16Higher-Order Pushdown Systems with DataPaweł ParysWe propose a new extension of higher-order pushdown automata, which allows to use an infinite alphabet. The new automata recognize languages of data words (instead of normal words), which beside each its letter from a finite alphabet have a data value from an infinite alphabet. Those data values can be loaded to the stack of the automaton, and later compared with some farther data values on the input. Our main purpose for introducing these automata is that they may help in analyzing normal automata (without data). As an example, we give a proof that deterministic automata with collapse can recognize more languages than deterministic automata without collapse. This proof is simpler than in the no-data case. We also state a hypothesis how the new automaton model can be related to the original model of higher-order pushdown automata.http://arxiv.org/pdf/1210.2460v1 |
| spellingShingle | Paweł Parys Higher-Order Pushdown Systems with Data Electronic Proceedings in Theoretical Computer Science |
| title | Higher-Order Pushdown Systems with Data |
| title_full | Higher-Order Pushdown Systems with Data |
| title_fullStr | Higher-Order Pushdown Systems with Data |
| title_full_unstemmed | Higher-Order Pushdown Systems with Data |
| title_short | Higher-Order Pushdown Systems with Data |
| title_sort | higher order pushdown systems with data |
| url | http://arxiv.org/pdf/1210.2460v1 |
| work_keys_str_mv | AT pawełparys higherorderpushdownsystemswithdata |