PUBLICATIONS (a selection)

FORMAL GRAMMARS:

A. Ja. Dikovsky, L. S. Modina. Minimization of a pd-automaton complexity measure and categorial grammars of the depth 3. ``Algebra and Logics", 1968, v.7, n.3.

A. Ja. Dikovsky. On Proper Inclusion of Deterministic CF-languages into All CF-languages. ``Algebra and Logics", 1968, v.8, n.1.

A. Ja. Dikovsky. On deterministic linear languages. ``Problems of Cybernetics", 1970, v. 23.

A. Ja. Dikovsky. Languages of bounded active capacity. Soviet Math. Dokl., 1970, vol.11, n.3.

A. V. Gladky, A. Ja. Dikovsky. Theory of formal grammars. Proc. of the 2nd Allunion Conf. on Programming, Novossibirsk, USSR, 1970 (Invited talk) (Russ.).

A. Ja. Dikovsky. Density - a derivation complexity measure in cf-grammars. Problems of information transmission, 1972, vol.8, issue 2.

A. Ja. Dikovsky. Density of derivation trees and index of grammars. Problems of information transmission, 1972, vol.8, issue 4.

A. Ja. Dikovsky. On domination density. Soviet Math. Dokl., 1972, vol.13, n.3.

A. V. Gladky, A. Ja. Dikovsky. Theory of formal grammars. Scientific reviews. VINITI. Acad. of Sci., Moscow, 1972, vol.10 (Russ.).

A. Ja. Dikovsky. On the general notion of complexity of derivation in a context-free grammar. Soviet Math. Dokl., 1974, vol.15, n.1.

M. K. Valiev, A. Ja. Dikovsky. On a hierarchy of cf-languages on their acceptance time. Cybernetics, 1975, n.3.

A. Ja. Dikovsky. On closure properties of context-free derivation complexity classes. Lect. Notes in Comput. Sci., 1975, vol.32.

A. Ja. Dikovsky, L. S. Modina. On three types of unambiguity of cf-languages. Lect. Notes in Comput. Sci., 1977, vol.52.

A. Ja. Dikovsky. Towards a general notion of complexity of derivation and syntactic description in cf-grammars. Semiotics and Informatics, 1977, issue 9. (Russ.).

A. Ja. Dikovsky, L. S. Modina. On three types of unambiguity of CF-languages. Transactions of the Tver State Univ., 1978, issue 1. (Russ.).

A. Ja. Dikovsky. Derivation complexity of unambiguous CF-languages. Transactions of the Tver State Univ., 1981, issue 4. (Russ.).

A. Ja. Dikovsky. Classification of context-free languages by their derivation complexity. Semiotics and Informatics, 1981, issue 17. (Russ.).

A. Ja. Dikovsky. A critical overview of Montague semiotics. Allunion Workshop ``Semiotic Aspects of Intell. Activity. Telavi, 1983 (Invited talk) (Russ.).

RECURSION SCHEMES, PROGRAM SYNTHESIS AND ANALYSIS:

A. Ja. Dikovsky. A theory of complexity of monadic recursion schemes. R.A.I.R.O. Theoretical Informatics, 1981, vol.15, n.1.

A. Ja. Dikovsky. Nets of covers and linear-time analysis of functional dependencies. Transactions of the Tver State Univ., 1982, issue 5. (Russ.).

A. Ja. Dikovsky. Complexity of the equivalence problem of recursive program schemes. Proc. of the 6 Allunion Conf. on Mathem. Logic. Tbilisi, 1982. (Russ.).

A. Ja. Dikovsky. Recursion schemes of strongly bounded density are translatable into WHILE-program schemes. Transactions of the Tver State Univ., 1983, issue 6. (Russ.).

A. Ja. Dikovsky. Optimal algorithm of automatic synthesis of the optimal algorithms over the computational models. Proc. of the Allunion Workshop on Program Transformation and Optimization. Part 1. Novossibirsk, 1983. (Russ.).

A. Ja. Dikovsky, M. I. Kanovich. Mathematical methods of analysis of programs. Tver State Univ. Press. 1983. (Russ.).

A. Ja. Dikovsky. Complexity bounds of algorithms on computational models. 3d Allunion Conf. on Appl. of Math. Logic, Tallin, 1983 (Invited talk) (Russ.).

A. Ja. Dikovsky. Linear time algorithm of automatic synthesis of loop-free programs. Allunion Workshop on Effective Algorithms, 1984, Cecis, Latvia (Invited talk) (Russ.).

A. Ja. Dikovsky. Computational models for fast synthesis of recursive programs. Int. Conf. on AI and Pattern Recognition, Kiev, 1984 (Invited talk) (Russ.).

28. A. Ja. Dikovsky. Deterministic computational models. Izvestija of Soviet Acad. of Sci. Technical Cybernetics, 1984, vol.5.

A. Ja. Dikovsky. Linear time solution of problems related to synthesis of loop-free programs. Programming and Computer Software, 1985, n.3.

A. Ja. Dikovsky, M. I. Kanovich. Computational models with shared subgoals. Izvestija of Soviet Acad. of Sci. Technical Cybernetics, 1985, vol.5.

A. Ja. Dikovsky. Relations between partial and general solutions of problems in recursive computational modelds. Transactions of the Tver State Univ., 1985, issue 8. (Russ.).

A. Ja. Dikovsky. Models, methods and regimes of synthesis of program schemes. Problems of Cybernetics. ``Problems of reduction of brute force choice", 1987, issue 131. (Russ.).

A. Ja. Dikovsky. Construction of programs - an alternative to automatic synthesis. Proc. of the Russian-French Symp. on Theoretical Foundations of Programs Design and Compiling. Grenoble, October 13-18, 1991.

A. Ja. Dikovsky. A survey of ideas and methods in software design. Part 1: Early phases of developing large programs. System Informatics. vol.1. Problems of Modern Programming. Novossibirsk, 1991 (Russ.).

A. Ja. Dikovsky. Models, Methods, and Modes for the Synthesis of Program Schemes. Amer. Math. Soc. Transl. 1996, vol.178, n.2, 103-131.

LOGIC PROGRAMMING:

A. Ja. Dikovsky. Space considerations in Prolog. Lect. Notes in Comput. Sci., 1989, vol.363.

A. Ja. Dikovsky. Prolog semantics for measuring space consumption. Lecture Notes in Artificial Intelligence, 1991, vol. 592.

A. Ja. Dikovsky. Abstract Complexity of Prolog Based on WAM. In : M. Bruynooghe, J. Penjam (Eds.) Proc. 5th Intern. Symp. on Programming Language Implementation and Logic Programming (PLILP). Tallin, Estonia, 1993 (Invited talk). LNCS, n. 714, 1993.

A. Ja. Dikovsky. On computational complexity of Prolog programs. Theoretical Computer Science, 1993, vol.119.

NON-MONOTONIC REASONING AND KNOWLEDGE BASE UPDATES:

M. I. Dekhtyar, A. Ja. Dikovsky. Dynamic deductive databases, Izvestija of Soviet Acad. of Sci. Technical Cybernetics, 1994, vol.5.

M. I. Dekhtyar, A.Ja.Dikovsky. Dynamic Deductive Data Bases with Steady Behavior. Proc. of the 12th International Conf. on Logic Programming (ICLP). (L. Sterling, Ed.), The MIT Press, 1995, 183-197.

M. I. Dekhtyar, A. Ja. Dikovsky. The analysis of behavior of discrete dynamic systems by means of logic programming. Programming and Computer Software, 1996, n.3.

M. I. Dekhtyar, A.Ja.Dikovsky. On Homeostatic Behavior of Dynamic Deductive Data Bases. Proc. 2nd Int. A. P. Ershov Memorial Conference ``Perspectives of System Informatics", D. Bjorner, M. Broy, I. Pottosin (Eds.). Lecture Notes in Computer Science. 1996, vol.1181, 420-432.

M. I. Dekhtyar, A. Ja. Dikovsky. Total Homeostaticity and Integrity Constraints. Proc. of the 14th International Conf. on Logic Programming (ICLP). L. Naish (Ed.), The MIT Press, 1997, 241-255.

M. I. Dekhtyar, A. Ja. Dikovsky. Recognition of Deductive Data Base Stability. Proc. of the 4th Symp. on Logical Foundations of Comput. Sci. (LFCS'97). S. Adian, A. Nerode (Eds.). Lecture Notes in Computer Science. 1997, vol.1234, 67-77.

M. I. Dekhtyar, A. Ja. Dikovsky, M. K. Valiev. On Stable Behavior of Cooperating Logic Programs. Proc. of the World Multiconference on Systemics, Cybernetics and Informatics (SCI'97/ISAS'97). N. Callaos (Ed.). 1997.

M. I. Dekhtyar, A. Ja. Dikovsky, N. Spyratos. On Conservative Enforced Updates. Proc. of the 4th Internat. Conf. on Logic Programming and Non-Monotonic Reasoning (LPNMR'97). J. Dix, U. Furbach, A. Nerode (Eds.). Lecture Notes in Artificial Intelligence, 1997, vol.1265, 244-257.

M. I. Dekhtyar, A. Ja. Dikovsky, N. Spyratos. Enforcement of Integrity Constraints by Means of Minimal Sufficient Changes. In: A. Dikovsky (Ed.). Programming and Computer Software. Special issue. ``Application of Logics in Programming". 1998, vol.24, n.2, 63-70.

M. I. Dekhtyar, A. Ja. Dikovsky, N. Spyratos. On Logically Justified Updates. Proc. of the 1998 Joint International Conf. and Sympos. on Logic Programming. Manchester. J. Jaffar (Ed.). 1998, 250-264. MIT Press.

M. I. Dekhtyar, A. Ja. Dikovsky, N. Spyratos, Incremental Expansion of Database Updates Through Integrity Constraints. In: (F. Fages, Ed.) Actes des 8-èmes Journées Francophones de Programmation Logique et Programmation par Contraintes (JFPLC'99), 1999, Lyon. Hermes Science Publications 1999, pp.189-203.

M. I. Dekhtyar, A. Dikovsky, S. Dudakov, N. Spyratos. Monotone Expansion of Updates in Logical Databases. Michael Gelfond, Nicolas Leone, Gerald Pfeifer (Eds.). Proc. of the 5th Internat. Conf. on Logic Programming and Non-Monotonic Reasoning (LPNMR'99). Lecture Notes in Artificial Intelligence, 1999, vol.1730, 132-146.

M. I. Dekhtyar, A. Ja. Dikovsky, M. K. Valiev. Applying Temporal Logic to Analysis of Behavior of Cooperating Logic Programs. Proc. 3d Int. A. P. Ershov Memorial Conference ``Perspectives of System Informatics", 1999. D. Bjorner, M. Broy, A.V. Zamulin (Eds.).Lecture Notes in Comput. Sci.,2000, v.1755, 228-234.

M. I. Dekhtyar, A. Dikovsky, S. Dudakov, N. Spyratos. Maximal Expansions of Database Updates. K.-D. Schewe, B. Thalheim (Eds.) Proc. of the First International Sympos. on Foundations of Information and Knowledge Systems (FoIKS 2000) Burg, Germany. Lecture Notes in Computer Science. 2000, vol.1762, 72-87.

M. Dekhtyar, A. Dikovsky, S. Dudakov, On Complexity of Updates Through Integrity Constraints. In : Proc. of the First Int. Conf. on Computational Logic (CL 2000)}, LNAI, v. 1861 (2000), pp. 867--881.

DISTRIBUTED ALGORITHMS:

M. Dekhtyar, A. Dikovsky, M. Valiev. On behavior complexity of interacting intelligent agents. In : Proc. of the Conf. Dedicated to the 90th Anniversary of  A.A. Lyapunov. Novossibirsk, 2001, pp. 18--28. (Russ.)

M. I. Dekhtyar, A. Ja. Dikovsky, M. K. Valiev. On Complexity of Behavior Properties of Interacting Agents (Extended abstract). In: Proc. of the Internat. Workshop on Logic and Complexity in Computer Science (LCCS'2001). September 3-5, Créteil, France, pp. 57-68.

M. Dekhtyar, A. Dikovsky, S. Dudakov and N. Spyratos, Maximal State Independent Approximations to Minimal Real Change. Annals of Mathematics and Artificial Intelligence, 2001, v. 33, n. 2-4, pp. 157-204.

M. Dekhtyar, A. Dikovsky and M. Valiev, Complexity of Multi-Agent Systems Behavior. Proc. of the 8th European Conference on Logic in Artificial Intelligence (JELIA'2002), 2002, Cozenca, Italy, G. Ianni and S. Flesca (Eds.). Lecture Notes in Computer Science, n. 2424. pp. 125-136.

M. Dekhtyar, A. Dikovsky and M. Valiev, Checking Multi-Agent Systems Behavior Properties.
Proc. of the IEEE International Conference ACAI'2002, 2002, Russia, V. Kurelchik (Ed.).

M. Dekhtyar, A. Dikovsky and M. Valiev, On feasible cases of checking multi-agent systems behavior.
Theoretical Computer Science, 2003, n. 303, pp. 63-81.

M. Dekhtyar, A. Dikovsky and M. Valiev, On complexity of verification of interacting agents' behavior.
Annals of Pure and Applied Logics, 2006, n. 141, pp. 336-362.

M. Dekhtyar, A. Dikovsky and M. Valiev, Temporal Verification of Probabilistic Multi-Agent Systems. In: Trakhtenbrot/Festschrift, A. Aviron et al. (Eds.) LNCS 4800, 2008, pp. 256-265, Springer

M. Dekhtyar, A. Dikovsky and M. Valiev, Systems of Agents Controlled by Logical Programms: Verification Complexity. "Programmirovanie", 2009, N. 4, pp. 1-20 (Rus.)

NATURAL LANGUAGES FORMAL SEMANTICS and GRAMMARS; GRAMMATICAL INFERENCE:

2000:

Alexander Dikovsky, Larissa Modina, Dependencies on the other side of the Curtain.  In : (S. Kahane, Ed.) Les grammaires de dépendance. Traitement Automatique des Langues (TAL),``Hermes", 2000, v.41, n. 1, pp. 79--111.

 2001:

A. Dikovsky, Polarized Non-projective Dependency Grammars. In : Ph. de Groote, G. Morill and Ch. Retoré (Eds.) Proc. of the Fourth Intern. Conf. on Logical Aspects of Computational Linguistics. Lecture Notes in Artificial Intelligence, n. 2099, 2001, pp. 139-157.

A. Dikovsky, Grammars for Local and Long Dependencies. Proc. of the 39th Intern. Conf. ACL'2001. 2001, Toulouse, France, 156-163.

2003:

A. Dikovsky, Linguistic Meaning from the Language Acquisition Perspective. Proc. of the 8th Intern. Conf. ``Formal Grammar 2003'' (FG 2003), G. Jager, P. Monachesi, G. Penn and S. Winter (Eds.), 2003, Vienna, Austria, pp. 63-76. http://cs.haifa.ac.il/~shuly/fg03/

A. Dikovsky, Discourse Plan => Meaning. Proc. of the 1st International Conference ``Meaning-Text Theory'' (MTT 2003), 2003, Paris, France, pp. 299-308.

2004:

A. Dikovsky, Dependencies as Categories. Proc. of Workshop ``Recent Advances in Dependency Grammars''.
In conjunction with COLING 2004, G-J. Kruiff and D. Duchier (Eds.). 2004, Geneva, Switzerland, pp. 90-97. 

M. Dekhtyar and A. Dikovsky, Categorial Dependency Grammars. Proc. of the Internat. Conference 
"Categorial Grammars" (CG'2004), M. Moortgat (Ed.), 2004, Montpellier, France, pp. 76-91.

D. Béchet, A. Dikovsky, A. Foret and E. Moreau, On Learning Discontinuous Dependencies from Positive Data. Proc. of the 9th Intern. Conf. ``Formal Grammar 2004'' (FG 2004). G. Jager, P. Monachesi, G. Penn and S. Winter (Eds.), 2004, Nancy, France, pp. 1-16, http://cs.haifa.ac.il/~shuly/fg04/

2005:

D. Béchet, A. Dikovsky and A. Foret, Dependency Structure Grammars . P. Blache and E. Stabler (Eds.): LACL 2005, LNAI 3492, pp. 18-34, 2005.

A. Dikovsky and B. Smilga, Semantic Roles and Diatheses for Functional Discourse Plans . Proc. of the 2nd International Conference ``Meaning-Text Theory'' (MTT 2005), 2005, Moscow, Russia.

A. Dikovsky, Underspecified Semantics for Dependency Grammars. Proc. of the 4th Mexican Internat. Conf. on Artificial Intellience, MICAI 2005, A.Gelbukh, A. de Albornoz, and H. Terashima (Eds.). Monterrey, Mexico. LNAI 3789, pp.741-751, 2005.  

2006:

A. Dikovsky and C. Retoré, From syntactic structures to logical semantics. Notes of advanced course. In : The 18th European Summer School in Logic, Language and Information (ESSLLI 2006). 2006, 31 July - 11 August, Malaga, Spain.

2007:

A. Dikovsky, Architecture compositionnelle pour les dépendances croisées . TALN 2007, Toulouse, 5-8 juin 2007, pp. 165-174.

A. Dikovsky, A Finite-State Functional Grammar Architecture . In: D. Leivant and R. de Queiroz (Eds.) WoLLIC 2007, LNCS 4576, pp. 131-146, 2007.

A. Dikovsky, Multimodal categorial dependency grammars . In: The 12th conference on Formal Grammar (FG 2007). Dublin, Ireland. August 4-5, 2007.

2008:

M. Dekhtyar and A. Dikovsky, Generalized Categorial Dependency Grammars. In: Trakhtenbrot/Festschrift, A. Aviron et al. (Eds.) LNCS 4800, 2008, pp. 230-255, Springer

D. Béchet, A. Dikovsky, A. Foret and E. Garel Optional and Iterated Types for Pregroup Grammars. In: C. Martin-Vide, F. Otto and H. Fernau (Eds.), Proc. of the 2d Intern. Conf. on Language and Automata Theory and Applications (LATA 2008). Tarragona, Spain, March 13-19, 2008. LNCS 5196, pp. 88-100, Springer

2009:

A. Dikovsky, On Speaker's Stance Meaning of Discourse . Proc. of the 4th International Conference ``Meaning-Text Theory'' (MTT 2009), 16-18 June 2009, Montreal, Canada.

A. Dikovsky, Towards Wide Coverage Categorial Dependency Grammars . In: T. Fowler and G. Penn (Eds.) Proc. of the ESSLLI'2009 Workshop on Parsing with Categorial Grammars. Book of Abstracts, 20-24 July, 2009, Bordeaux, France.

2010:

A. Dikovsky, On constructive semantics of natural language. In: Solomon Feferman and Wilfried Sieg (eds.), with the collaboration of Vladik Kreinovich, Vladimir Lifschitz, and Ruy de Queiroz, Proofs, Categories and Computations: Essays in honor of Grigori Mints, College Publications, London, UK, 2010.

2011:

D. Béchet, A. Dikovsky and A. Foret, Sur les itérations dispersées et les choix itérés pour l'apprentissage incrémental des types dans les grammaires de dépendances. Actes de la Conférence francophone sur l'apprentissage automatique (CAp 2011), Chambéry, France, 17 - 20 mai 2011

D. Béchet, A. Dikovsky and A. Foret, Categorial Grammars with Iterated Types Form a Strict Hierarchy of k-Valued Languages. Proc. of the 16th Intern. Conf. ``Implementation and Application of Automata'' (CIAA 2011). B. Bouchou-Markhoff, P. Caron, J.-M. Champarnaud, D. Maurel (Eds.), 2011, Blois, France, July 2011, LNCS 6807, pp. 42-52, Springer

D. Béchet, A. Dikovsky and A. Foret, On Dispersed and Choice Iteration in Incrementally Learnable Dependency Types. Proc. of the 6th Intern. Conf. ``Logical Aspects of Computational Linguistics'' (LACL 2011). S. Pogodalla and J.-P. Prost (Eds.), 2011, Montpellier, France, June/July 2011, LNAI 6736, pp. 80-95, Springer

A. Dikovsky, Categorial Dependency Grammars: from Theory to Large Scale Grammars. In: K. Gerdes, E. Hajicova, and L. Wanner (Eds.), Proc. of the 1st Intern. ``Conf. on Dependency Linguistics'' (Depling 2011), Barcelona, September 5-7 2011.

R. Alfared, D. Béchet and A. Dikovsky, "CDG LAB": a Toolbox for Dependency Grammars and Dependency Treebanks Development. In: K. Gerdes, E. Hajicova, and L. Wanner (Eds.), Proc. of the 1st Intern. ``Conf. on Dependency Linguistics'' (Depling 2011), Barcelona, September 5-7 2011.

2012:

D. Béchet, A. Dikovsky and A. Foret, Two Models of Learning Iterated Dependencies. Proc. of the 15th Intern. Conf. on ``Formal Grammar'' (FG 2010). Copenhagen, Denmark, August 7-8, 2010. In: P. de Groote and M.-J. Nederhof (Eds.). Formal Grammar 2010/2011. LNCS 7395, 2012. pp. 17-32.

M.Dekhtyar, A. Dikovsky and B. Karlov, Iterated Dependencies and Kleene Iteration. Proc. of the 15th Intern. Conf. on ``Formal Grammar'' (FG 2010). Copenhagen, Denmark, August 7-8, 2010. In: P. de Groote and M.-J. Nederhof (Eds.). Formal Grammar 2010/2011. LNCS 7395, 2012. pp. 66-81.

R. Alfared, Denis Béchet, A. Dikovsky, Calcul des cadres de sous-catégorisation des noms déverbaux français (le cas du génitif). ``TALN'' 2012, Grenoble, 4 au 8 juin 2012, pp. 71-84.

D. Béchet, A. Dikovsky and A. Foret, Categorial Grammars with Iterated Types Form a Strict Hierarchy of k-Valued Languages. Theoretical Computer Science, vol. 450, 7 September 2012, Elsevier, pp. 22-30.

A. Dikovsky, What Should be a Proper Semantics for Dependency Structures. In: Ju. Apresjan, I. Boguslavsky, M.-C. L'Homme, L. Iomdin, J. Milic'evic', A. Polguere, L. Wanner (Eds.) Meanings, Texts and Other Exciting Things. A Festschrift to Commemorate the 80th Anniversary of Professor Igor Alexandrovich Mel'chuk. Languages of Slavic Culture, Moscow 2012, pp. 112-123.