Principal investigator (ÚFAL): 
Grant id: 


Non-Standard Computational Models and Their Applications in Complexity, Linguistics, and Learning

NoSCoM is a basic research project combining several complementary subfields of theoretical computer
science in order to deepen our knowledge of important specialized non-standard models of computation. Its
aim is to characterize the computational power and efficiency of these models and to explore their ability to
model problems from selected application domains such as complexity theory, linguistics, and machine
learning. Our multi-model approach will also include the analysis of new resources or measures of effective
computation which are introduced in the respective non-standard computational models. In particular, the
research will focus mainly on non-uniform amorphous computing systems modeling mobile sensory nets;
nano-scale machines; formal models of practical neurocomputing in AI; specialized unbounded automata and
grammars with important applications in linguistics (e.g. word-order freedom measures); branching programs
for studying space-complexity aspects of computing; models for approximating distributions of empirical data
such as random forests.

Institute of Computer Science, Academy of Sciences of the Czech Republic