List of PSPACE-complete Problems - Automata and Language Theory - Formal Languages

Formal Languages

Word problem for Context-sensitive language · Regular language intersection · Regular expression star freeness · Equivalence problem for regular expressions · Emptiness problem for regular expressions with intersection. · Equivalence problem for star-free regular expressions with squaring. · Covering for linear grammars · Structural equivalence for linear grammars · Equivalence problem for Regular grammars · Emptiness problem for ET0L grammars · Word problem for ET0L grammars · Tree transducer language membership problem for top down finite-state tree transducers

Read more about this topic:  List Of PSPACE-complete Problems, Automata and Language Theory

Other articles related to "formal languages, languages, language, formal":

Logical Connectives - In Language - Formal Languages
... In formal languages, truth functions are represented by unambiguous symbols ... These symbols are called "logical connectives", "logical operators", "propositional operators", or, in classical logic, "truth-functional connectives" ...
Semantic Gap - Formal Languages
... Real world tasks are formalized by programming languages, which are executed on computers based on the von Neumann architecture ... Since programming languages are only comfortable representations of the Turing machine any program on a von Neumann computer has the same properties and limitations as the Turing machine or its ... Consequently every programming language such as CPU level machine code, assembler, or any high level programming language has the same expressional power as ...
Important Distinctions in Metalogic - Syntax–semantics
... In metalogic, 'syntax' has to do with formal languages or formal systems without regard to any interpretation of them, whereas, 'semantics' has to do with interpretations of formal languages ... than 'proof-theoretic', since it may be applied to properties of formal languages without any deductive systems, as well as to formal systems ...

Famous quotes containing the words languages and/or formal:

    Science and technology multiply around us. To an increasing extent they dictate the languages in which we speak and think. Either we use those languages, or we remain mute.
    —J.G. (James Graham)

    There must be a profound recognition that parents are the first teachers and that education begins before formal schooling and is deeply rooted in the values, traditions, and norms of family and culture.
    Sara Lawrence Lightfoot (20th century)