|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
19 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Structural Complexity of Multi-Valued Partial Functions Computed by Nondeterministic Pushdown Automata | | Tomoyuki Yamakami
; | | Date: |
24 Aug 2015 | | Abstract: | This paper continues a systematic and comprehensive study on the structural
properties of CFL functions, which are in general multi-valued partial
functions computed by one-way one-head nondeterministic pushdown automata
equipped with write-only output tapes (or pushdown transducers), where CFL
refers to a relevance to context-free languages. The CFL functions tend to
behave quite differently from their corresponding context-free languages. We
extensively discuss containments, separations, and refinements among various
classes of functions obtained from the CFL functions by applying Boolean
operations, functional composition, many-one relativization, and Turing
relativization. In particular, Turing relativization helps construct a
hierarchy over the class of CFL functions. We also analyze the computational
complexity of optimization functions, which are to find optimal values of CFL
functions, and discuss their relationships to the associated languages. | | Source: | arXiv, 1508.5814 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER