Affiliations: Department of Computer Science, Faculty of Mathematics and Physics, Charles University, CZ-118 00 Praha 1, Czech Republik | Fachbereich Elektrotechnik/Informatik, Universität Kassel, D-34109 Kassel, Germany | Department of Computer Science, Faculty of Mathematics and Physics, Charles University, CZ-118 00 Praha 1, Czech Republik. Martin.Platek@mff.cuni.cz
Note: [] The work was supported by a grant from the Deutsche Forschungsgemeinschaft, and by the Grant Agency of the Czech Republic under Grant-No. P202/10/1333 and P103/10/0783. This work was partially performed while F. Mráz was visiting the University of Kassel.
Note: [] Address for correspondence: Charles University, Faculty of Mathematics and Physics, Department of Computer Science, Malostranské nám. 25, 118 00 PRAHA 1, Czech Republic
Abstract: In natural languages with a high degree of word-order freedom, syntactic phenomena like dependencies (subordinations) or valences do not depend on the word-order (or on the individual positions of the individual words). This means that some permutations of sentences of these languages are in some (important) sense syntactically equivalent. Here we study this phenomenon in a formal way. Various types of j-monotonicity for restarting automata can serve as parameters for the degree of word-order freedom and for the complexity of word-order in sentences (languages). Here we combine two types of parameters on computations of restarting automata: the degree of j-monotonicity, and the number of rewrites per cycle. We study these notions formally in order to obtain an adequate tool for modelling and comparing formal descriptions of (natural) languages with different degrees of word-order freedom and word-order complexity.
