6533b7cefe1ef96bd1257947

RESEARCH PRODUCT

Feasibility of finite and infinite paths in data dependent programs

Karlis Cerans

subject

Mathematical optimizationProgramming languageReachability problemSimple (abstract algebra)Computer sciencePath (graph theory)Computer Science::Programming Languagescomputer.software_genrecomputerData dependentInteger (computer science)Decidability

description

This paper considers the feasibility of finite and infinite paths in programs in two simple programming languages. The language LBASE allows to express the dependencies of real time systems on integer data, the language LTIM can model quantitative timing constraints in r.t.s. specifications. It is proven that the problem of whether a given LBASE or LTIM program has an infinite feasible path (i.e. whether it can exhibit an infinite behaviour) is decidable. The possibilities to characterise the sets of all feasible finite and infinite paths in LBASE and LTIM programs are also discussed. The infinite feasible path existence problem is proven decidable also for the language LTIBA which has both the LBASE and LTIM modelling capabilities.

https://doi.org/10.1007/bfb0023864