Uniform \textit{vs.} nonuniform membership for mildly context-sensitive languages: a brief survey (Q1736791): Difference between revisions

From MaRDI portal
Set OpenAlex properties.
ReferenceBot (talk | contribs)
Changed an Item
Property / cites work
 
Property / cites work: Three models for the description of language / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3862379 / rank
 
Normal rank
Property / cites work
 
Property / cites work: The equivalence of four extensions of context-free grammars / rank
 
Normal rank
Property / cites work
 
Property / cites work: On multiple context-free grammars / rank
 
Normal rank
Property / cites work
 
Property / cites work: Translations on a context free grammar / rank
 
Normal rank
Property / cites work
 
Property / cites work: The string generating power of context-free hypergraph grammars / rank
 
Normal rank
Property / cites work
 
Property / cites work: Tree transducers, L systems, and two-way machines / rank
 
Normal rank
Property / cites work
 
Property / cites work: Trading independent for synchronized parallelism in finite copying parallel rewriting systems / rank
 
Normal rank
Property / cites work
 
Property / cites work: From Contextual Grammars to Range Concatenation Grammars / rank
 
Normal rank
Property / cites work
 
Property / cites work: Parsing Beyond Context-Free Grammars / rank
 
Normal rank
Property / cites work
 
Property / cites work: Tree-Walking Automata / rank
 
Normal rank
Property / cites work
 
Property / cites work: Parametrized complexity theory. / rank
 
Normal rank
Property / cites work
 
Property / cites work: Dependency structures and lexicalized grammars. An algebraic approach / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4599177 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4281539 / rank
 
Normal rank

Revision as of 21:52, 18 July 2024

scientific article
Language Label Description Also known as
English
Uniform \textit{vs.} nonuniform membership for mildly context-sensitive languages: a brief survey
scientific article

    Statements

    Uniform \textit{vs.} nonuniform membership for mildly context-sensitive languages: a brief survey (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    26 March 2019
    0 references
    Summary: Parsing for mildly context-sensitive language formalisms is an important area within natural language processing. While the complexity of the parsing problem for some such formalisms is known to be polynomial, this is not the case for all of them. This article presents a series of results regarding the complexity of parsing for linear context-free rewriting systems and deterministic tree-walking transducers. We discuss the difference between uniform and nonuniform complexity measures and how parameterized complexity theory can be used to investigate how different aspects of the formalisms influence how hard the parsing problem is. The main results we survey are all hardness results and indicate that parsing is hard even for relatively small values of parameters such as rank and fan-out in a rewriting system.
    0 references
    mildly context-sensitive languages
    0 references
    parsing
    0 references
    formal languages
    0 references
    parameterized complexity
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references