RAIRO. Informatique Théorique et Applications Short Title: RAIRO, Inform. Théor. Appl. Parallel Title: Theoretical Informatics and Applications Publisher: Dunod, Paris ISSN: 0988-3754 Online: http://www.numdam.org/numdam-bin/feuilleter?j=ITA&sl=0 Predecessor: RAIRO, Informatique Théorique Successor: RAIRO. Theoretical Informatics and Applications Comments: No longer indexed Documents Indexed: 333 Publications (1986–1997) References Indexed: 328 Publications with 4,761 References. all top 5 Latest Issues 31, No. 6 (1997) 31, No. 5 (1997) 31, No. 4 (1997) 31, No. 3 (1997) 31, No. 2 (1997) 31, No. 1 (1997) 30, No. 6 (1996) 30, No. 5 (1996) 30, No. 4 (1996) 30, No. 3 (1996) 30, No. 2 (1996) 30, No. 1 (1996) 29, No. 6 (1995) 29, No. 5 (1995) 29, No. 4 (1995) 29, No. 3 (1995) 29, No. 2 (1995) 29, No. 1 (1995) 28, No. 6 (1994) 28, No. 5 (1994) 28, No. 3-4 (1994) 28, No. 2 (1994) 28, No. 1 (1994) 27, No. 6 (1993) 27, No. 5 (1993) 27, No. 4 (1993) 27, No. 3 (1993) 27, No. 2 (1993) 27, No. 1 (1993) 26, No. 6 (1992) 26, No. 5 (1992) 26, No. 4 (1992) 26, No. 3 (1992) 26, No. 2 (1992) 26, No. 1 (1992) 25, No. 6 (1991) 25, No. 5 (1991) 25, No. 4 (1991) 25, No. 3 (1991) 25, No. 2 (1991) 25, No. 1 (1991) 24, No. 6 (1990) 24, No. 5 (1990) 24, No. 4 (1990) 24, No. 3 (1990) 24, No. 2 (1990) 24, No. 1 (1990) 23, No. 4 (1989) 23, No. 3 (1989) 23, No. 2 (1989) 23, No. 1 (1989) 22, No. 4 (1988) 22, No. 3 (1988) 22, No. 2 (1988) 22, No. 1 (1988) 21 (1987) 20 (1986) all top 5 Authors 5 Ehrenfeucht, Andrzej 5 Rozenberg, Grzegorz 5 Wood, Derick 4 Blanchet-Sadri, Francine 4 Harju, Tero 4 Honkala, Juha 4 Latteux, Michel 4 Le Saëc, Bertrand 4 Litovsky, Igor 4 Nour, Karim 4 Salomaa, Arto Kustaa 3 Afrati, Foto N. 3 Arquès, Didier G. 3 Balcázar, José Luis 3 Cori, Robert 3 Courcelle, Bruno 3 Do Long Van 3 Geffert, Viliam 3 Hoogeboom, Hendrik Jan 3 Karhumaki, Juhani 3 Lombardi, Henri 3 Mateescu, Alexandru 3 Nguyen Huong Lam 3 Salemi, Sergio 3 Salomaa, Kai T. 3 Staiger, Ludwig 3 Talamo, Maurizio 3 Waack, Stephan 2 Allouche, Jean-Paul Simon 2 Arnold, André 2 Arsac, Jacques J. 2 Bellia, Marco 2 Blanc, Georges 2 Bleuzen-Guernalec, Noëlle 2 Boasson, Luc 2 Boffa, Maurice 2 Book, Ronald Vernon 2 Bozapalidis, Symeon 2 Brzozowski, Janusz Antoni 2 Caucal, Didier 2 Charron-Bost, Bernadette 2 Chemillier, Marc 2 Choffrut, Christian 2 Dauchet, Max 2 Diks, Krzysztof 2 Duske, Jürgen 2 Gabarró, Joaquim 2 Gambosi, Giorgio 2 Gonzalez-Vega, Laureano 2 Gouyou-Beauchamps, Dominique 2 Guessarian, Irène 2 Head, Thomas J. 2 Hébrard, Jean-Jacques 2 Ito, Masami 2 Katajainen, Jyrki 2 Kemp, Rainer 2 Kleijn, H. C. M. 2 Köbler, Johannes 2 Kortelainen, Juha 2 Krause, Matthias 2 Krithivasan, Kamala 2 Krob, Daniel 2 Néraud, Jean 2 Parchmann, Rainer 2 Păun, Gheorghe 2 Pelc, Andrzej 2 Pirillo, Giuseppe 2 Prodinger, Helmut 2 Protasi, Marco 2 Rangan, Chandrasekharan Pandu 2 Raspaud, André 2 Rayward-Smith, Victor J. 2 Rebaine, Djamal 2 Recio, Tomas 2 Régnier, Mireille 2 Restivo, Antonio 2 Roy, Marie-Françoise 2 Séébold, Patrice 2 Ślusarek, Maciej 2 Sportelli, Tecla 2 Stafylopatis, Andreas N. 2 Terlutte, Alain 2 Thérien, Denis 2 Timmerman, Erick 2 Weiss, Alex 2 Yu, Sheng 1 Aalbersberg, Ijsbrand Jan 1 Abdulrab, Habib 1 Alessi, Fabio 1 Alexandrakis, Athanasios 1 Alimonti, Paola 1 Allender, Eric W. 1 Almeida, Jorge 1 André, Yves 1 Angelaccio, Michele 1 Anselmo, Marcella 1 Arvind, Vikraman 1 Autebert, Jean-Michel 1 Avnaim, Francis 1 Balayogan, V. B. ...and 310 more Authors all top 5 Fields 305 Computer science (68-XX) 36 Mathematical logic and foundations (03-XX) 35 Group theory and generalizations (20-XX) 24 Combinatorics (05-XX) 13 Information and communication theory, circuits (94-XX) 12 Number theory (11-XX) 8 General algebraic systems (08-XX) 6 Order, lattices, ordered algebraic structures (06-XX) 5 General and overarching topics; collections (00-XX) 5 Field theory and polynomials (12-XX) 4 Category theory; homological algebra (18-XX) 3 Linear and multilinear algebra; matrix theory (15-XX) 3 Associative rings and algebras (16-XX) 3 Functions of a complex variable (30-XX) 2 Convex and discrete geometry (52-XX) 2 General topology (54-XX) 2 Numerical analysis (65-XX) 2 Operations research, mathematical programming (90-XX) 1 Algebraic geometry (14-XX) 1 Nonassociative rings and algebras (17-XX) 1 Real functions (26-XX) 1 Dynamical systems and ergodic theory (37-XX) 1 Difference and functional equations (39-XX) 1 Probability theory and stochastic processes (60-XX) 1 Systems theory; control (93-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 231 Publications have been cited 1,610 times in 1,426 Documents Cited by ▼ Year ▼ Notes on finite asynchronous automata. Zbl 0623.68055Zielonka, Wiesław 77 1987 The monadic second-order logic of graphs. III: Tree-decompositions, minors and complexity issues. Zbl 0754.03006Courcelle, B. 76 1992 A limit theorem for “Quicksort”. Zbl 0718.68026Rösler, Uwe 75 1991 A remark on morphic Sturmian words. Zbl 0883.68104Berstel, J.; Séébold, P. 54 1994 Repetitions in the Fibonacci infinite word. Zbl 0761.68078Mignosi, F.; Pirillo, G. 51 1992 The complexity of the travelling repairman problem. Zbl 0585.68057Afrati, Foto; Cosmadakis, Stavros; Papadimitriou, Christos H.; Papageorgiou, George; Papakostantinou, Nadia 42 1986 The difference and truth-table hierarchies for NP. Zbl 0642.03024Köbler, Johannes; Schöning, Uwe; Wagner, Klaus W. 39 1987 On semigroups of matrices over the tropical semiring. Zbl 0888.68086Simon, Imre 36 1994 A limiting distribution for quicksort. Zbl 0677.68072Régnier, Mireille 36 1989 Each regular code is included in a maximal regular code. Zbl 0609.68053Ehrenfeucht, A.; Rozenberg, G. 27 1986 Speeding up the computations on an elliptic curve using addition- subtraction chains. Zbl 0724.11068Morain, François; Olivos, Jorge 27 1990 Decidability of periodicity for infinite words. Zbl 0617.68063Pansiot, Jean-Jacques 26 1986 Completing codes. Zbl 0669.94012Restivo, A.; Salemi, S.; Sportelli, T. 24 1989 Normal forms for phrase-structure grammars. Zbl 0755.68092Geffert, Viliam 24 1991 On generating all solutions of generalized satisfiability problems. Zbl 0901.68075Creignou, N.; Hebrard, J.-J. 23 1997 Spécialisation de la suite de Sturm et sous-résultants. I. (Specialization of the Sturm sequence and subresultants. I). Zbl 0732.68059González-Vega, L.; Lombardi, H.; Recio, T.; Roy, M.-F. 23 1990 On the periodicity of morphisms on free monoids. Zbl 0608.68065Harju, Tero; Linna, Matti 23 1986 On some packing problem related to dynamic storage allocation. Zbl 0675.68041Chrobak, Marek; Ślusarek, Maciej 22 1988 Une remarque sur les systèmes complets d’identités rationnelles. (A note on complete systems of rational identities). Zbl 0701.68059Boffa, Maurice 22 1990 A condition implying all rational identities. (Une condition impliquant toutes les identités rationnelles.) Zbl 0881.68071Boffa, M. 20 1995 A note on read-\(k\) times branching programs. Zbl 0889.68021Jukna, Stasys 20 1995 Exact and asymptotic distributions in digital and binary search trees. Zbl 0643.68077Louchard, G. 20 1987 Graphes canoniques de graphes algébriques. (Canonical graphs of algebraic graphs). Zbl 0701.68082Caucal, Didier 20 1990 A decision method for the recognizability of sets defined by number systems. Zbl 0639.68074Honkala, Juha 18 1986 Analysis of quickselect: An algorithm for order statistics. Zbl 0838.68029Mahmoud, Hosam M.; Modarres, Reza; Smythe, Robert T. 17 1995 Relationships among \(PL\), \(\# L\), and the determinant. Zbl 0851.68033Allender, Eric; Ogihara, Mitsunori 17 1996 Une condition suffisante de reconnaissabilité dans un monoïde partiellement commutatif. (A sufficient condition for recognizability in a partially commutative monoid). Zbl 0599.20107Métivier, Yves 16 1986 Combinatorial analysis of quicksort algorithm. Zbl 0685.68058Hennequin, P. 16 1989 Codes et motifs. (Codes and motifs). Zbl 0689.68102Ratoandromanana, Bodonirina 15 1989 On frontiers of regular trees. Zbl 0639.68071Thomas, Wolfgang 15 1986 Représentations matricielles des séries d’arbre reconnaissables. (Matrix representations of series on recognizable trees). Zbl 0689.68099Bozapalidis, Symeon; Alexandrakis, Athanasios 14 1989 On infinitary finite length codes. Zbl 0628.68056Staiger, Ludwig 13 1986 A linear-time algorithm to decide whether a binary word contains an overlap. Zbl 0645.68087Kfoury, A. J. 11 1988 Complexity of boundary graph languages. Zbl 0701.68062Engelfriet, Joost; Leih, George 11 1990 A hierarchy that does not collapse: Alternations in low level space. Zbl 0884.68054Geffert, Viliam 10 1994 The pseudovariety \(J\) is hyperdecidable. Zbl 0928.20046Almeida, J.; Zeitoun, M. 10 1997 An extension of the notions of traces and of asynchronous automata. Zbl 0765.68153Arnold, A. 10 1991 Trace languages defined by regular string languages. Zbl 0612.68071Aalbersberg, Ijsbrand Jan; Welzl, Emo 10 1986 On dot-depth two. Zbl 0718.68046Blanchet-Sadri, F. 10 1990 Finite degrees of ambiguity in pattern languages. Zbl 0883.68076Mateescu, A.; Salomaa, A. 9 1994 Open shop scheduling with delays. Zbl 0766.90043Rayward-Smith, V. J.; Rebaine, D. 9 1992 Sur des points fixes de morphismes d’un monoïde libre. Zbl 0691.68065Allouche, J.-P.; Betrema, J.; Shallit, J. O. 9 1988 Implementing term rewriting by jungle evaluation. Zbl 0706.68061Hoffmann, B.; Plump, D. 9 1991 Fractals, dimension, and formal languages. Zbl 0883.68078Merzenich, W.; Staiger, L. 8 1994 A unified approach to control problems in discrete event processes. Zbl 0807.93002Bergeron, A. 8 1993 Deux propriétés combinatoires des nombres de Schröder. (Two combinatorial properties of Schröder numbers). Zbl 0669.05002Gouyou-Beauchamps, Dominique; Vauquelin, Bernard 8 1988 On a subclass of context-free groups. Zbl 0751.68040Herbst, Thomas 8 1991 Approximate counting: An alternative approach. Zbl 0732.68052Kirschenhofer, Peter; Prodinger, Helmut 8 1991 Elementariness of a finite set of words is co-NP-complete. Zbl 0704.68065Neraud, Jean 8 1990 On finitely generated monoids of matrices with entries in \({\mathbb{N}}\). Zbl 0721.20042Weber, Andreas; Seidl, Helmut 8 1991 Decimations and Sturmian words. Zbl 0889.68090Justin, Jacques; Pirillo, Giuseppe 7 1997 On free inverse monoid languages. Zbl 0867.68074Silva, Pedro V. 7 1996 External power of a deterministic automaton, application to the zeta-function of a sofic system. (Puissance extérieure d’un automate déterministe, application au calcul de la fonction zêta d’un système sofique.) Zbl 0843.58035Béal, Marie-Pierre 7 1995 Lower bounds on the complexity of real-time branching programs. Zbl 0664.68046Kriegel, Klaus; Waack, Stephan 7 1988 Une extension d’un théorème de P. Jullien sur les âges de mots. (An extension of a theorem of P. Jullien on the ages of words). Zbl 0754.68067Kabil, M.; Pouzet, M. 7 1992 A generalization of traces. Zbl 0731.68083Vogler, Walter 7 1991 Unavoidable languages, cuts and innocent sets of words. Zbl 0838.68068Rosaz, L. 7 1995 A note on separating the relativized polynomial time hierarchy by immune sets. Zbl 0701.68032Ko, Ker-I 7 1990 Two-way automaton computations. Zbl 0701.68058Birget, Jean-Camille 7 1990 Cutwidth of the de Bruijn graph. Zbl 0880.05054Raspaud, André; Sýkora, Ondrej; Vrto, Imrich 6 1995 Generalized ternary simulation of sequential circuits. Zbl 0879.94040Seger, C.-J.; Brzozowski, J. A. 6 1994 Retrieving library functions by unifying types modulo linear isomorphism. Zbl 0809.68063Rittri, M. 6 1993 Decomposing a \(k\)-valued transducer into \(k\) unambiguous ones. Zbl 0867.68046Weber, Andreas 6 1996 Sequential mappings of \(\omega\)-languages. Zbl 0634.68070Staiger, Ludwig 6 1987 Catégories et langages de dot-depth un. (Categories and dot-depth one languages). Zbl 0659.68094Thérien, Denis 6 1988 First-order properties of trees, star-free expressions, and aperiodicity. Zbl 0741.68065Heuter, Uschi 6 1991 A bijection between convex and directed polyominoes and the words of the bilateral Dyck language. (Une bijection entre les polyominos convexes dirigés et les mots de Dyck bilatères.) Zbl 0761.68077Bousquet-Mélou, M. 6 1992 Spanning trees with low crossing number. Zbl 0732.68100Matoušek, Jiří 6 1991 Optimal on-line coloring of circular arc graphs. Zbl 0838.68090Ślusarek, Maciej 6 1995 Une approche quantitative de l’exclusion mutuelle. Zbl 0602.68024Françon, Jean 6 1986 Varieties of finite categories. Zbl 0608.18002Weiss, Alex; Therien, Denis 6 1986 Lambda-calcul, évaluation paresseuse et mise en mémoire. (Lambda calculus, lazy evaluation and storage operators). Zbl 0717.03003Krivine, Jean-Louis 6 1991 Partially abelian squarefree words. Zbl 0719.68033Cori, Robert; Formisano, Maria Rosaria 6 1990 On bandwidth, cutwidth, and quotient graphs. Zbl 0881.68089Barth, Dominique; Pellegrini, François; Raspaud, André; Roman, Jean 5 1995 Using persistent data structures for adding range restrictions to searching problems. Zbl 0998.68520Lenhof, Hans-Peter; Smid, Michiel 5 1994 Fractal geometry, turing machines and divide-and-conquer recurrences. Zbl 0883.68056Dube, S. 5 1994 An algorithm to compute the Möbius function of the rotation lattice of binary trees. Zbl 0779.68066Pallo, J. M. 5 1993 An imperative language based on distributive categories. II. Zbl 0806.18006Khalil, Wafaa; Walters, R. F. C. 5 1993 Algorithm of Bareiss, algorithm of subresultants. (Algorithme de Bareiss, algorithme des sous-résultants.) Zbl 0868.65026Ducos, Lionel 5 1996 Holonomic functions and their relation to linearly constrained languages. Zbl 0781.68079Massazza, P. 5 1993 Immunity and simplicity in relativizations of probabilistic complexity classes. Zbl 0647.68053Balcázar, José L.; Russo, David A. 5 1988 Polygon placement under translation and rotation. Zbl 0665.68037Avnaim, Francis; Boissonnat, Jean-Daniel 5 1989 Automata and zigzag codes. (Automates et codes zigzag.) Zbl 0735.68050Anselmo, Marcella 5 1991 A combinatorial theorem on p-power-free words and an application to semigroups. Zbl 0701.68065de Luca, Aldo; Varricchio, Stefano 5 1990 Storage operators and \(\forall\)-positive types. (Opérateurs de mise en mémoire et types \(\forall\)-positifs.) Zbl 0869.03009Nour, Karim 5 1996 On continuous functions computed by finite automata. Zbl 0883.68095Derencourt, D.; Karhumäki, J.; Latteux, M.; Terlutte, A. 4 1994 Accurate computation of the relative entropy between stochastic regular grammars. Zbl 0893.68094Carrasco, R. C. 4 1997 The laterality problem for non-erasing Turing machines on \(\{0,1\}\) is completely solved. Zbl 0878.68063Margenstern, Maurice 4 1997 On morphically generated formal power series. Zbl 0816.68077Honkala, Juha 4 1995 A fast algorithm to decide on the equivalence of stateless DPDA. Zbl 0778.68051Caucal, Didier 4 1993 Efficient reductions of picture words. Zbl 0770.68081Brandenburg, Franz J.; Dassow, Jürgen 4 1993 PCP-prime words and primality types. Zbl 0770.68082Mateescu, Alexandru; Salomaa, Arto 4 1993 Codes limites et factorisations finies du monoïde libre. (Limit codes and finite factorizations of free monoids). Zbl 0643.20037Krob, Daniel 4 1987 Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines. Zbl 0768.68017Krause, Matthias; Meinel, Christoph; Waack, Stephan 4 1992 Equations on the semidirect product of a finite semilattice by a \(J\)- trivial monoid of height \(k\). Zbl 0833.68073Blanchet-Sadri, F. 4 1995 The topological structure of adherences of regular languages. Zbl 0608.68066Head, Tom 4 1986 Calcul de la distance par les sous-mots. (Computing the distance by subwords). Zbl 0639.68063Hebrard, Jean-Jacques; Crochemore, Maxime 4 1986 Tours de Hanoï et automates. (Towers of Hanoi and automata). Zbl 0701.68036Allouche, J.-P.; Dress, François 4 1990 Separating words with machines and groups. Zbl 0851.68076Robson, J. M. 4 1996 Complexity classes between \(\Theta^ P_ k\) and \(\Delta^ P_ k\). Zbl 0860.68048Castro, J.; Seara, C. 4 1996 On generating all solutions of generalized satisfiability problems. Zbl 0901.68075Creignou, N.; Hebrard, J.-J. 23 1997 The pseudovariety \(J\) is hyperdecidable. Zbl 0928.20046Almeida, J.; Zeitoun, M. 10 1997 Decimations and Sturmian words. Zbl 0889.68090Justin, Jacques; Pirillo, Giuseppe 7 1997 Accurate computation of the relative entropy between stochastic regular grammars. Zbl 0893.68094Carrasco, R. C. 4 1997 The laterality problem for non-erasing Turing machines on \(\{0,1\}\) is completely solved. Zbl 0878.68063Margenstern, Maurice 4 1997 Undecidable event detection problems for ODEs of dimension one and two. Zbl 0878.68062Ruohonen, Keijo 3 1997 Polynomial size test sets for commutative languages. Zbl 0889.68091Hakala, Ismo; Kortelainen, Juha 2 1997 On the power of parallel communicating grammar systems with right-linear components. Zbl 0892.68058Dumitrescu, S.; Păun, G. 2 1997 Enumeration of rooted maps on the Klein bottle. (Énumération des cartes pointées sur la bouteille de Klein.) Zbl 0891.05040Arquès, Didier; Béraud, Jean-François 2 1997 Completeness results for the class of types of the \(\mathcal{AF}2\) system. (Résultats de complétude pour des classes de types du système \(\mathcal{AF}2\).) Zbl 0898.68045Farkh, Samir; Nour, Karim 2 1997 A decision procedure for a satisfiability problem in a hereditarily finite set-theoretical universe. (Une procédure de décision pour un problème de satisfiabilité dans un univers ensembliste héréditairement fini.) Zbl 0889.68062Hibti, M.; Legeard, B.; Lombardi, H. 1 1997 On the semidirect product of the pseudovariety of semilattices by a locally finite pseudovariety of groups. Zbl 0889.68089Blanchet-Sadri, F. 1 1997 The approximate calculus of the lower bound of distributed values. (Calculs approchés de la borne inférieure de valeurs réparties.) Zbl 0892.68042Charron-Bost, Bernadette; Tel, Gerard 1 1997 Languages obtained from infinite words. Zbl 0903.68115Harju, T.; Ilie, L. 1 1997 Relationships among \(PL\), \(\# L\), and the determinant. Zbl 0851.68033Allender, Eric; Ogihara, Mitsunori 17 1996 On free inverse monoid languages. Zbl 0867.68074Silva, Pedro V. 7 1996 Decomposing a \(k\)-valued transducer into \(k\) unambiguous ones. Zbl 0867.68046Weber, Andreas 6 1996 Algorithm of Bareiss, algorithm of subresultants. (Algorithme de Bareiss, algorithme des sous-résultants.) Zbl 0868.65026Ducos, Lionel 5 1996 Storage operators and \(\forall\)-positive types. (Opérateurs de mise en mémoire et types \(\forall\)-positifs.) Zbl 0869.03009Nour, Karim 5 1996 Separating words with machines and groups. Zbl 0851.68076Robson, J. M. 4 1996 Complexity classes between \(\Theta^ P_ k\) and \(\Delta^ P_ k\). Zbl 0860.68048Castro, J.; Seara, C. 4 1996 One-rule semi-Thue systems with loops of length one, two or three. Zbl 0867.68064Kurth, Winfried 3 1996 UET flow shop scheduling with delays. Zbl 0851.68036Rayward-Smith, V. J.; Rebaine, D. 3 1996 A category theory approach to conceptual data modeling. Zbl 0851.68019Lippe, E.; ter Hofstede, A. H. M. 3 1996 On the Horton-Strahler number for random tries. Zbl 0867.68087Devroye, L.; Kruszewski, P. 2 1996 On the average minimal prefix-length of the generalized semi-Dycklanguage. Zbl 0877.68077Kemp, Rainer 2 1996 A note concerning the limit distribution of the quicksort algorithm. Zbl 0860.68052Cramer, Michael 2 1996 The closure under division and a characterization of the recognizable \({\mathcal Z}\)-subsets. Zbl 0860.68073Kobayashi, Nami 2 1996 On the robustness of \(\text{ALMOST-}{\mathcal R}\). Zbl 0860.68049Book, Ronald V.; Mayordomo, Elvira 2 1996 Average case analysis of fully dynamic reachability for directed graphs. Zbl 0876.68080Alimonti, Paola; Leonardi, Stefano; Marchetti-Spaccamela, Alberto 1 1996 On semidirect and two-sided semidirect products of finite \(\mathcal J\)-trivial monoids. Zbl 0906.20039Blanchet-Sadri, F. 1 1996 On codes having no finite completion. Zbl 0877.68012Nguyen Huong Lam 1 1996 The biased circular automata which verify Černý’s conjecture. (Les automates circulaires biaisés vérifient la conjecture de Černý.) Zbl 0877.68083Dubuc, L. 1 1996 Efficient string matching on packed texts. Zbl 0877.68047Breslauer, D.; Gąsieniec, Leszek 1 1996 A condition implying all rational identities. (Une condition impliquant toutes les identités rationnelles.) Zbl 0881.68071Boffa, M. 20 1995 A note on read-\(k\) times branching programs. Zbl 0889.68021Jukna, Stasys 20 1995 Analysis of quickselect: An algorithm for order statistics. Zbl 0838.68029Mahmoud, Hosam M.; Modarres, Reza; Smythe, Robert T. 17 1995 External power of a deterministic automaton, application to the zeta-function of a sofic system. (Puissance extérieure d’un automate déterministe, application au calcul de la fonction zêta d’un système sofique.) Zbl 0843.58035Béal, Marie-Pierre 7 1995 Unavoidable languages, cuts and innocent sets of words. Zbl 0838.68068Rosaz, L. 7 1995 Cutwidth of the de Bruijn graph. Zbl 0880.05054Raspaud, André; Sýkora, Ondrej; Vrto, Imrich 6 1995 Optimal on-line coloring of circular arc graphs. Zbl 0838.68090Ślusarek, Maciej 6 1995 On bandwidth, cutwidth, and quotient graphs. Zbl 0881.68089Barth, Dominique; Pellegrini, François; Raspaud, André; Roman, Jean 5 1995 On morphically generated formal power series. Zbl 0816.68077Honkala, Juha 4 1995 Equations on the semidirect product of a finite semilattice by a \(J\)- trivial monoid of height \(k\). Zbl 0833.68073Blanchet-Sadri, F. 4 1995 Algebraic and topological theory of languages. Zbl 0889.68088Rhodes, J.; Weil, P. 3 1995 Complexity of E0L structural equivalence. Zbl 0881.68070Salomaa, Kai; Wood, Derick; Yu, Sheng 2 1995 On parallel deletions applied to a word. Zbl 0816.68095Kari, Lila; Mateescu, Alexandru; Paun, Gheorghe; Salomaa, Arto 2 1995 On codes having no finite completion. Zbl 0819.94019Nguyen Huong Lam 2 1995 On-line computations of the ideal lattice of posets. Zbl 0833.68055Jard, Claude; Jourdan, Guy-Vincent; Rampon, Jean-Xavier 2 1995 Minimum complexity of automatic non Sturmian sequences. Zbl 0838.68057Tapsoba, T. 2 1995 Uniformly growing backtrack trees. Zbl 0889.68114Kemp, Rainer 1 1995 Binary trees, fringe thickness and minimum path length. Zbl 0833.68092Cameron, Helen; Wood, Derick 1 1995 A remark on morphic Sturmian words. Zbl 0883.68104Berstel, J.; Séébold, P. 54 1994 On semigroups of matrices over the tropical semiring. Zbl 0888.68086Simon, Imre 36 1994 A hierarchy that does not collapse: Alternations in low level space. Zbl 0884.68054Geffert, Viliam 10 1994 Finite degrees of ambiguity in pattern languages. Zbl 0883.68076Mateescu, A.; Salomaa, A. 9 1994 Fractals, dimension, and formal languages. Zbl 0883.68078Merzenich, W.; Staiger, L. 8 1994 Generalized ternary simulation of sequential circuits. Zbl 0879.94040Seger, C.-J.; Brzozowski, J. A. 6 1994 Using persistent data structures for adding range restrictions to searching problems. Zbl 0998.68520Lenhof, Hans-Peter; Smid, Michiel 5 1994 Fractal geometry, turing machines and divide-and-conquer recurrences. Zbl 0883.68056Dube, S. 5 1994 On continuous functions computed by finite automata. Zbl 0883.68095Derencourt, D.; Karhumäki, J.; Latteux, M.; Terlutte, A. 4 1994 Specialization of the Sturm sequence. (Spécialisation de la suite de Sturm.) Zbl 0999.12502González-Vega, Laureano; Lombardi, Henri; Recio, Thomas; Roy, Marie-Françoise 3 1994 The complexity of systolic dissemination of information in interconnection networks. Zbl 0888.68014Hromkovič, J.; Klasing, R.; Unger, W.; Wagener, H.; Pardubská, D. 3 1994 Decidability of equivalence for a class of non-deterministic tree transducers. Zbl 0884.68095André, Yves; Dauchet, Max 3 1994 Pumping and pushdown machines. Zbl 0883.68093Salomaa, Kai; Wood, D.; Yu, Sheng 2 1994 The Hamilton circuit problem on grids. Zbl 0884.68097Afrati, Foto 2 1994 On deciding some equivalences for concurrent processes. Zbl 1004.68521Huynh, Dung T.; Tian, Lu 1 1994 Arithmetic coding of weighted finite automata. Zbl 0883.68094Kari, J.; Fränti, P. 1 1994 Updating approximately complete trees. Zbl 0884.68094Lai, Tony W.; Wood, Derick 1 1994 Pebbling dynamic graphs in minimal space. Zbl 0884.68096Ružička, Peter; Waczulík, Juraj 1 1994 A unified approach to control problems in discrete event processes. Zbl 0807.93002Bergeron, A. 8 1993 Retrieving library functions by unifying types modulo linear isomorphism. Zbl 0809.68063Rittri, M. 6 1993 An algorithm to compute the Möbius function of the rotation lattice of binary trees. Zbl 0779.68066Pallo, J. M. 5 1993 An imperative language based on distributive categories. II. Zbl 0806.18006Khalil, Wafaa; Walters, R. F. C. 5 1993 Holonomic functions and their relation to linearly constrained languages. Zbl 0781.68079Massazza, P. 5 1993 A fast algorithm to decide on the equivalence of stateless DPDA. Zbl 0778.68051Caucal, Didier 4 1993 Efficient reductions of picture words. Zbl 0770.68081Brandenburg, Franz J.; Dassow, Jürgen 4 1993 PCP-prime words and primality types. Zbl 0770.68082Mateescu, Alexandru; Salomaa, Arto 4 1993 Sublogarithmic \(\Sigma_ 2\)-space is not closed under complement and other separation results. Zbl 0804.68047Geffert, V. 3 1993 Combinatorial properties of texts. Zbl 0803.68098Ehrenfeucht, A.; ten Pas, P.; Rozenberg, G. 3 1993 An optimal congestion for embedding the hypercube \(H(n)\) into the line \(P(2^ n)\). (Congestion optimale du plongement de l’hypercube \(H(n)\) dans la chaîne \(P(2^ n)\).) Zbl 0803.68091Hala, A. Bel 3 1993 Space-efficient parallel merging. Zbl 0778.68037Katajainen, J.; Levcopoulos, C.; Petersson, O. 2 1993 Objects in relational database schemes with functional, inclusion, and exclusion dependencies. Zbl 0787.68031Biskup, Joachim; Dublish, Pratul 2 1993 \(Pm\) numbers, ambiguity, and regularity. Zbl 0806.11007Cameron, H. A.; Wood, D. 2 1993 On ranking 1-way finitely ambiguous NL languages and #\(P_ 1\)- complete census functions. Zbl 0780.68082Bertoni, A.; Goldwurm, M. 2 1993 On the positive and the inversion complexity of Boolean functions. Zbl 0789.68070Dičiūnas, V. 1 1993 Performance considerations on a random graph model for parallel processing. Zbl 0778.68017Afrati, F.; Stafylopatis, A. 1 1993 Fast diagnosis of multiprocessor systems with random faults. Zbl 0803.68004Diks, Krzysztof; Pelc, Andrzej 1 1993 Language classes defined by time-bounded relativised cellular automata. Zbl 0803.68076Mahajan, Meena; Krithivasan, Kamala 1 1993 On the average number of registers needed to evaluate a special class of backtrack trees. Zbl 0809.68104Trier, U. 1 1993 Real time recognition with cellular automata: A meaningful example. Zbl 0776.68089Terrier, V. 1 1993 The monadic second-order logic of graphs. III: Tree-decompositions, minors and complexity issues. Zbl 0754.03006Courcelle, B. 76 1992 Repetitions in the Fibonacci infinite word. Zbl 0761.68078Mignosi, F.; Pirillo, G. 51 1992 Open shop scheduling with delays. Zbl 0766.90043Rayward-Smith, V. J.; Rebaine, D. 9 1992 Une extension d’un théorème de P. Jullien sur les âges de mots. (An extension of a theorem of P. Jullien on the ages of words). Zbl 0754.68067Kabil, M.; Pouzet, M. 7 1992 A bijection between convex and directed polyominoes and the words of the bilateral Dyck language. (Une bijection entre les polyominos convexes dirigés et les mots de Dyck bilatères.) Zbl 0761.68077Bousquet-Mélou, M. 6 1992 Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines. Zbl 0768.68017Krause, Matthias; Meinel, Christoph; Waack, Stephan 4 1992 On a tree collision resolution algorithm in presence of capture. Zbl 0767.94001Schmid, U. 3 1992 Compositional representation of rational functions. Zbl 0769.68097Harju, T.; Kleijn, H. C. M.; Latteux, M. 3 1992 Enumeration of bordered words. Le langage de la vache-qui-rit. Zbl 0754.68089Régnier, M. 3 1992 ...and 131 more Documents all cited Publications top 5 cited Publications all top 5 Cited by 1,653 Authors 19 Ésik, Zoltán 18 Mahmoud, Hosam M. 16 Blanchet-Sadri, Francine 16 Karhumaki, Juhani 16 Prodinger, Helmut 16 Shallit, Jeffrey O. 15 Fernau, Henning 14 Rozenberg, Grzegorz 13 Courcelle, Bruno 13 de Luca, Aldo 11 Golovach, Petr A. 11 Neininger, Ralph 10 Allouche, Jean-Paul Simon 10 Engelfriet, Joost 10 Nour, Karim 10 Pirillo, Giuseppe 10 Rampersad, Narad 9 Geffert, Viliam 9 Harju, Tero 9 Honkala, Juha 9 Latteux, Michel 9 Litovsky, Igor 9 Muscholl, Anca 9 Néraud, Jean 9 Otachi, Yota 9 Staiger, Ludwig 9 Weil, Pascal 8 Bruyère, Véronique 8 Carpi, Arturo 8 De Felice, Clelia 8 Gastin, Paul 8 Hemaspaandra, Lane A. 8 Paulusma, Daniël 8 Rösler, Uwe 8 Rytter, Wojciech 8 Tuza, Zsolt 8 Vollmer, Heribert 7 Bozapalidis, Symeon 7 Carton, Olivier 7 Flajolet, Philippe 7 Justin, Jacques 7 Kuppusamy, Lakshmanan 7 Pin, Jean-Eric 7 Roy, Marie-Françoise 7 Rüschendorf, Ludger 7 Sulzbach, Henning 7 Yukna, Stasys P. 6 Almeida, Jorge 6 Béal, Marie-Pierre 6 De Luca, Alessandro 6 Fill, James Allen 6 Frid, Anna Èduardovna 6 Glaßer, Christian 6 Grübel, Rudolf 6 Heuberger, Clemens 6 Hoogeboom, Hendrik Jan 6 Janicki, Ryszard 6 Kim, Changwook 6 Kuske, Dietrich 6 Lohrey, Markus 6 Louchard, Guy 6 Mignosi, Filippo 6 Mukund, Madhavan 6 Perrin, Dominique 6 Pous, Damien 6 Raman, Indhumathi 6 Restivo, Antonio 6 Reutenauer, Christophe 6 Rothe, Jörg-Matthias 6 Schott, René 6 Struth, Georg 5 Aalbersberg, Ijsbrand Jan 5 Bazgan, Cristina 5 Beigel, Richard 5 Berstel, Jean 5 Bloom, Stephen L. 5 Bodlaender, Hans L. 5 Bollig, Benedikt 5 Cassaigne, Julien 5 Charlier, Emilie 5 Creignou, Nadia 5 Currie, James D. 5 Ehrenfeucht, Andrzej 5 El Kahoui, M’hammed 5 Glen, Amy 5 Gonzalez-Vega, Laureano 5 Head, Thomas J. 5 Janson, Svante 5 Koutny, Maciej 5 Kratsch, Dieter 5 Krawczyk, Tomasz 5 Le Saëc, Bertrand 5 Lombardi, Henri 5 Mahajan, Meena 5 McKenzie, Pierre 5 Mikulski, Łukasz 5 Reidenbach, Daniel 5 Sabadini, Nicoletta 5 Salemi, Sergio 5 Santocanale, Luigi ...and 1,553 more Authors all top 5 Cited in 185 Journals 392 Theoretical Computer Science 73 RAIRO. Informatique Théorique et Applications 56 Information and Computation 49 Discrete Applied Mathematics 49 RAIRO. Theoretical Informatics and Applications 45 Information Processing Letters 31 Journal of Computer and System Sciences 25 Discrete Mathematics 23 Acta Informatica 20 International Journal of Algebra and Computation 19 Algorithmica 18 International Journal of Foundations of Computer Science 16 Mathematical Systems Theory 16 Theory of Computing Systems 15 European Journal of Combinatorics 14 European Journal of Operational Research 13 Random Structures & Algorithms 12 The Annals of Applied Probability 11 RAIRO. Theoretical Informatics and Applications 10 Journal of Algebra 10 Journal of Applied Probability 10 Journal of Pure and Applied Algebra 10 Semigroup Forum 10 Advances in Applied Mathematics 10 Annals of Pure and Applied Logic 9 Advances in Applied Probability 9 Order 9 Computers & Operations Research 8 Journal of Combinatorial Theory. Series A 8 Discrete & Computational Geometry 8 Stochastic Processes and their Applications 7 Transactions of the American Mathematical Society 7 Journal of Symbolic Computation 7 Logical Methods in Computer Science 6 The Annals of Probability 6 Linear Algebra and its Applications 5 SIAM Journal on Computing 5 Applicable Algebra in Engineering, Communication and Computing 5 Computational Complexity 5 Journal of Discrete Algorithms 4 The Journal of Symbolic Logic 4 Ergodic Theory and Dynamical Systems 4 Operations Research Letters 4 Journal of Mathematical Sciences (New York) 4 The Electronic Journal of Combinatorics 4 The Journal of Logic and Algebraic Programming 4 Journal of Logical and Algebraic Methods in Programming 3 Mathematical Biosciences 3 Periodica Mathematica Hungarica 3 Problems of Information Transmission 3 Algebra Universalis 3 Applied Mathematics and Computation 3 Journal of Computational and Applied Mathematics 3 Networks 3 Mathematical and Computer Modelling 3 Formal Aspects of Computing 3 Designs, Codes and Cryptography 3 Distributed Computing 3 Journal de Théorie des Nombres de Bordeaux 3 Annals of Mathematics and Artificial Intelligence 3 Journal of Automata, Languages and Combinatorics 3 Sādhanā 2 Artificial Intelligence 2 Computers & Mathematics with Applications 2 Mathematics of Computation 2 Advances in Mathematics 2 Annals of the Institute of Statistical Mathematics 2 Automatica 2 Bulletin de la Société Mathématique de France 2 Journal of Statistical Planning and Inference 2 Mathematica Slovaca 2 Memoirs of the American Mathematical Society 2 Monatshefte für Mathematik 2 Statistics & Probability Letters 2 Combinatorica 2 Probability Theory and Related Fields 2 Journal of Complexity 2 Journal of Computer Science and Technology 2 Journal of Automated Reasoning 2 Annals of Operations Research 2 Computational Geometry 2 MSCS. Mathematical Structures in Computer Science 2 Journal of Global Optimization 2 Discrete Event Dynamic Systems 2 International Journal of Computer Mathematics 2 Archive for Mathematical Logic 2 Mathematical Programming. Series A. Series B 2 Journal of Logic, Language and Information 2 Journal of Applied Non-Classical Logics 2 Constraints 2 Journal of Combinatorial Optimization 2 Journal of Scheduling 2 Journal of Graph Algorithms and Applications 2 Fundamenta Informaticae 2 Methodology and Computing in Applied Probability 2 Natural Computing 2 Journal of Applied Logic 2 Computer Science Review 2 Prikladnaya Diskretnaya Matematika 1 Bulletin of the Australian Mathematical Society ...and 85 more Journals all top 5 Cited in 44 Fields 1,144 Computer science (68-XX) 209 Combinatorics (05-XX) 139 Mathematical logic and foundations (03-XX) 112 Group theory and generalizations (20-XX) 87 Probability theory and stochastic processes (60-XX) 81 Number theory (11-XX) 75 Operations research, mathematical programming (90-XX) 59 Information and communication theory, circuits (94-XX) 31 Order, lattices, ordered algebraic structures (06-XX) 29 General algebraic systems (08-XX) 22 Algebraic geometry (14-XX) 22 Dynamical systems and ergodic theory (37-XX) 21 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 18 Associative rings and algebras (16-XX) 18 Category theory; homological algebra (18-XX) 17 Numerical analysis (65-XX) 16 Linear and multilinear algebra; matrix theory (15-XX) 14 Field theory and polynomials (12-XX) 14 Convex and discrete geometry (52-XX) 12 Commutative algebra (13-XX) 11 Measure and integration (28-XX) 10 Statistics (62-XX) 9 Biology and other natural sciences (92-XX) 9 Systems theory; control (93-XX) 6 History and biography (01-XX) 4 Statistical mechanics, structure of matter (82-XX) 3 Topological groups, Lie groups (22-XX) 3 Special functions (33-XX) 2 General and overarching topics; collections (00-XX) 2 Functions of a complex variable (30-XX) 2 Difference and functional equations (39-XX) 2 Approximations and expansions (41-XX) 2 Functional analysis (46-XX) 2 Quantum theory (81-XX) 1 Nonassociative rings and algebras (17-XX) 1 Ordinary differential equations (34-XX) 1 Partial differential equations (35-XX) 1 Harmonic analysis on Euclidean spaces (42-XX) 1 Operator theory (47-XX) 1 Calculus of variations and optimal control; optimization (49-XX) 1 Differential geometry (53-XX) 1 General topology (54-XX) 1 Algebraic topology (55-XX) 1 Manifolds and cell complexes (57-XX) Citations by Year