## RAIRO. Theoretical Informatics and Applications

 Short Title: Theor. Inform. Appl. Parallel Title: Informatique Théorique et Applications Publisher: EDP Sciences, Les Ulis ISSN: 0988-3754; 1290-385X/e Online: http://www.rairo-ita.org/index.phphttp://www.numdam.org/journals/ITA Predecessor: RAIRO. Informatique Théorique et Applications Successor: RAIRO. Theoretical Informatics and Applications Comments: No longer indexed
 Documents Indexed: 345 Publications (1999–2009) References Indexed: 328 Publications with 6,647 References.
all top 5

### Latest Issues

 43, No. 4 (2009) 43, No. 3 (2009) 43, No. 2 (2009) 43, No. 1 (2009) 42, No. 4 (2008) 42, No. 3 (2008) 42, No. 2 (2008) 42, No. 1 (2008) 41, No. 4 (2007) 41, No. 3 (2007) 41, No. 2 (2007) 41, No. 1 (2007) 40, No. 4 (2006) 40, No. 3 (2006) 40, No. 2 (2006) 40, No. 1 (2006) 39, No. 3 (2005) 39, No. 2 (2005) 39, No. 1 (2005) 38, No. 4 (2004) 38, No. 3 (2004) 38, No. 2 (2004) 38, No. 1 (2004) 37, No. 4 (2003) 37, No. 3 (2003) 37, No. 2 (2003) 37, No. 1 (2003) 36, No. 4 (2002) 36, No. 3 (2002) 36, No. 2 (2002) 36, No. 1 (2002) 35, No. 6 (2001) 35, No. 5 (2001) 35, No. 4 (2001) 35, No. 3 (2001) 35, No. 2 (2001) 35, No. 1 (2001) 34, No. 6 (2000) 34, No. 5 (2000) 34, No. 4 (2000) 34, No. 3 (2000) 34, No. 2 (2000) 34, No. 1 (2000) 33, No. 6 (1999) 33, No. 4-5 (1999) 33, No. 3 (1999) 33, No. 2 (1999) 33, No. 1 (1999)
all top 5

### Authors

 7 Carton, Olivier 6 Choffrut, Christian 6 Ésik, Zoltán 5 Harju, Tero 5 Justin, Jacques 4 de Luca, Aldo 4 Finkel, Olivier 4 Frougny, Christiane 4 Honkala, Juha 4 Karhumaki, Juhani 4 Mereghetti, Carlo 4 Palano, Beatrice 4 Pelantová, Edita 3 Balková, L’ubomíra 3 Bollig, Beate 3 Carpi, Arturo 3 Cassaigne, Julien 3 Geffert, Viliam 3 Goldwurm, Massimiliano 3 Halava, Vesa 3 Héam, Pierre-Cyrille 3 Holub, Štěpán 3 Ingólfsdóttir, Anna 3 Jirásková, Galina 3 Kärki, Tomi 3 La Torre, Salvatore 3 Labella, Anna 3 Litow, Bruce E. 3 Maňuch, Ján 3 Masáková, Zuzana 3 Mitrana, Victor 3 Napoli, Margherita 3 Otto, Friedrich 3 Restivo, Antonio 3 Seibert, Sebastian 3 Selivanov, Viktor L’vovich 3 Serna Iglesias, Maria José 3 Szepietowski, Andrzej 3 Terlutte, Alain 2 Aceto, Luca 2 Almeida, Jorge 2 Béal, Marie-Pierre 2 Berstel, Jean 2 Berthé, Valérie 2 Blanchet-Sadri, Francine 2 Böckenhauer, Hans-Joachim 2 Bozapalidis, Symeon 2 Bradfield, Julian Charles 2 Cabessa, Jérémie 2 Campadelli, Paola 2 Carrasco, Rafael C. 2 Cegielski, Patrick 2 Creignou, Nadia 2 Currie, James D. 2 Czaja, Ludwik 2 Daudé, Hervé 2 De Felice, Clelia 2 de Figueiredo, Celina M. Herrera 2 do Lago, Alair Pereira 2 Duparc, Jacques 2 Duval, Jean-Pierre 2 Fernau, Henning 2 Frid, Anna Èduardovna 2 Ghani, Neil 2 Glen, Amy 2 Grübel, Rudolf 2 Guesnet, Yannick 2 Guessarian, Irène 2 Ilie, Lucian 2 Imai, Katsunobu 2 Jurdziński, Tomasz 2 Kirsten, Daniel 2 Klein, Sulamita 2 Kuske, Dietrich 2 Lefebvre, Arnaud 2 Lombardy, Sylvain 2 Margenstern, Maurice 2 Mauri, Giancarlo 2 Mignosi, Filippo 2 Morita, Kenichi 2 Muller, Jean-Michel 2 Nguyen Huong Lam 2 Nour, Karim 2 Ochem, Pascal 2 Okhotin, Alexander 2 Parente, Mimmo 2 Pighizzini, Giovanni 2 Pin, Jean-Eric 2 Pirillo, Giuseppe 2 Popély, Norbert 2 Rampersad, Narad 2 Richomme, Gwénaël 2 Roos, Yves 2 Salomaa, Arto Kustaa 2 Santini, Massimo 2 Shur, Arseny M. 2 Silva, Pedro V. 2 Simonnet, Pierre 2 Simplot, David 2 Torelli, Mauro ...and 383 more Authors
all top 5

### Fields

 306 Computer science (68-XX) 66 Mathematical logic and foundations (03-XX) 30 Combinatorics (05-XX) 26 Group theory and generalizations (20-XX) 22 Information and communication theory, circuits (94-XX) 21 Number theory (11-XX) 14 Category theory; homological algebra (18-XX) 12 Dynamical systems and ergodic theory (37-XX) 10 General and overarching topics; collections (00-XX) 9 Order, lattices, ordered algebraic structures (06-XX) 9 Operations research, mathematical programming (90-XX) 7 General algebraic systems (08-XX) 7 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 6 Numerical analysis (65-XX) 4 Quantum theory (81-XX) 3 History and biography (01-XX) 3 Convex and discrete geometry (52-XX) 3 Probability theory and stochastic processes (60-XX) 3 Biology and other natural sciences (92-XX) 2 Field theory and polynomials (12-XX) 2 Linear and multilinear algebra; matrix theory (15-XX) 2 General topology (54-XX) 1 Commutative algebra (13-XX) 1 Associative rings and algebras (16-XX) 1 Functions of a complex variable (30-XX) 1 Approximations and expansions (41-XX) 1 Statistics (62-XX) 1 Systems theory; control (93-XX)

### Citations contained in zbMATH Open

261 Publications have been cited 1,645 times in 1,434 Documents Cited by Year
A sharpening of the Parikh mapping. Zbl 1005.68092
Mateescu, Alexandru; Salomaa, Arto; Salomaa, Kai; Yu, Sheng
2001
Lack, Stephen; Sobociński, Paweł
2005
Return words in Sturmian and episturmian words. Zbl 0987.68055
Justin, Jacques; Vuillon, Laurent
2000
Episturmian words: a survey. Zbl 1182.68155
Glen, Amy; Justin, Jacques
2009
A generator of morphisms for infinite words. Zbl 1110.68122
Ochem, Pascal
2006
Many-sorted coalgebraic modal logic: A model-theoretic study. Zbl 0984.03019
Jacobs, Bart
2001
On the equivalence of linear conjunctive grammars and trellis automata. Zbl 1084.68079
Okhotin, Alexander
2004
Episturmian morphisms and a Galois theorem on continued fractions. Zbl 1126.68519
Justin, Jacques
2005
On a paper by Castelli, Mignosi, Restivo. Zbl 0987.68056
Justin, Jacques
2000
Division in logspace-uniform NC. Zbl 1014.68062
Chiu, Andrew; Davida, George; Litow, Bruce
2001
On Christoffel classes. Zbl 1085.68116
Borel, Jean-Pierre; Reutenauer, Christophe
2006
The $$\mu$$-calculus alternation-depth hierarchy is strict on binary trees. Zbl 0945.68118
Arnold, André
1999
Measuring the problem-relevant information in input. Zbl 1176.68089
Dobrev, Stefan; Královič, Rastislav; Pardubská, Dana
2009
Finding $$H$$-partitions efficiently. Zbl 1063.05124
Dantas, Simone; de Figueiredo, Celina M. H.; Gravier, Sylvain; Klein, Sulamita
2005
Permissive strategies: From parity games to safety games. Zbl 1090.91514
Bernet, Julien; Janin, David; Walukiewicz, Igor
2002
Dejean’s conjecture holds for $${n\geq 27}$$. Zbl 1192.68497
2009
On synchronized sequences and their separators. Zbl 1003.68064
Carpi, Arturo; Maggi, Cristiano
2001
Unambiguous recognizable two-dimensional languages. Zbl 1112.68085
Anselmo, Marcella; Giammarresi, Dora; Madonia, Maria; Restivo, Antonio
2006
Hyper-minimizing minimized deterministic finite state automata. Zbl 1170.68023
Badr, Andrew; Geffert, Viliam; Shipman, Ian
2009
Some results on $$\mathcal C$$-varieties. Zbl 1083.20059
Pin, Jean-Éric; Straubing, Howard
2005
Polynomials over the reals in proofs of termination: from theory to practice. Zbl 1085.68076
2005
Computing $$\varepsilon$$-free NFA from regular expressions in $$O(n\log^2 (n))$$ time. Zbl 0971.68091
Hagenah, Christian; Muscholl, Anca
2000
Some decision problems on integer matrices. Zbl 1081.20066
Choffrut, Christian; Karhumäki, Juhani
2005
A Burnside approach to the termination of Mohri’s algorithm for polynomially ambiguous min-plus-automata. Zbl 1155.68042
Kirsten, Daniel
2008
Generalizing substitution. Zbl 1042.18003
Uustalu, Tarmo
2003
Distance desert automata and the star height problem. Zbl 1082.20041
Kirsten, Daniel
2005
On some problems related to palindrome closure. Zbl 1155.68061
Bucci, Michelangelo; de Luca, Aldo; De Luca, Alessandro; Zamboni, Luca Q.
2008
Least periods of factors of infinite words. Zbl 1162.68510
Currie, James D.; Saari, Kalle
2009
Words over an ordered alphabet and suffix permutations. Zbl 1013.68153
Duval, Jean-Pierre; Lefebvre, Arnaud
2002
Traced premonoidal categories. Zbl 1110.68356
Benton, Nick; Hyland, Martin
2003
Wadge degrees of $$\omega$$-languages of deterministic Turing machines. Zbl 1048.03031
Selivanov, Victor
2003
Note on the succinctness of deterministic, nondeterministic, probabilistic and quantum finite automata. Zbl 1010.68068
Mereghetti, Carlo; Palano, Beatrice; Pighizzini, Giovanni
2001
Theories of orders on the set of words. Zbl 1098.03021
Kuske, Dietrich
2006
On substitution invariant Sturmian words: an application of Rauzy fractals. Zbl 1140.11014
Berthé, Valérie; Ei, Hiromi; Ito, Shunji; Rao, Hui
2007
State complexity of cyclic shift. Zbl 1144.68033
Jirásková, Galina; Okhotin, Alexander
2008
A characterization of poly-slender context-free languages. Zbl 0966.68097
Ilie, Lucian; Rozenberg, Grzegorz; Salomaa, Arto
2000
Complexity of infinite words associated with beta-expansions. Zbl 1104.11013
Frougny, Christiane; Masáková, Zuzana; Pelantová, Edita
2004
On extremal properties of the Fibonacci word. Zbl 1155.68062
Cassaigne, Julien
2008
Quantum finite automata with control language. Zbl 1112.68064
Mereghetti, Carlo; Palano, Beatrice
2006
On a characteristic property of Arnoux-Rauzy sequences. Zbl 1060.68094
Justin, Jacques; Pirillo, Giuseppe
2002
An exercise of Fibonacci representations. Zbl 1005.68119
Berstel, Jean
2001
Density of critical factorizations. Zbl 1013.68154
Harju, Tero; Nowotka, Dirk
2002
Non-looping string rewriting. Zbl 0951.68054
Geser, Alfons; Zantema, Hans
1999
A note on coinduction and weak bisimiliarity for while programs. Zbl 0945.68073
Rutten, J. J. M. M.
1999
Rewriting on cyclic structures: Equivalence between the operational and the categorical description. Zbl 0940.18002
1999
Local transition functions of quantum Turing machines. Zbl 0987.68035
Ozawa, Masanao; Nishimura, Harumichi
2000
Comparing complexity functions of a language and its extendable part. Zbl 1149.68055
Shur, Arseny M.
2008
Efficient validation and construction of border arrays and validation of string matching automata. Zbl 1166.68033
Duval, Jean-Pierre; Lecroq, Thierry; Lefebvre, Arnaud
2009
On the complexity of the hidden weighted bit function for various BDD models. Zbl 0946.68042
Bollig, Beate; Löbbing, Martin; Sauerhoff, Martin; Wegener, Ingo
1999
On existentially first-order definable languages and their relation to NP. Zbl 0949.03035
Borchert, Bernd; Kuske, Dietrich; Stephan, Frank
1999
Fixpoint alternation: Arithmetic, transition systems, and the binary tree. Zbl 0945.68126
1999
Call-by-value solvability. Zbl 0958.68061
Paolini, Luca; Ronchi Della Rocca, Simona
1999
Improved lower bounds on the approximability of the traveling salesman problem. Zbl 0971.68075
Böckenhauer, Hans-Joachim; Seibert, Sebastian
2000
Termination checking with types. Zbl 1089.68028
Abel, Andreas
2004
Coproducts of ideal monads. Zbl 1072.18006
Ghani, Neil; Uustalu, Tarmo
2004
An algorithm for deciding if a polyomino tiles the plane. Zbl 1146.68409
Gambini, Ian; Vuillon, Laurent
2007
On the size of one-way quantum finite automata with periodic behaviors. Zbl 1013.68088
Mereghetti, Carlo; Palano, Beatrice
2002
Learning deterministic regular grammars from stochastic samples in polynomial time. Zbl 0940.68071
Carrasco, Rafael C.; Oncina, Jose
1999
Domain-free $$\lambda\mu$$-calculus. Zbl 0974.68032
Fujita, Ken-Etsu
2000
Galois lattice as a framework to specify building class hierarchies algorithms. Zbl 0976.06003
Huchard, M.; Dicky, H.; Leblanc, H.
2000
Picture codes. Zbl 1117.94015
Bozapalidis, Symeon; Grammatikopoulou, Archontia
2006
Complexity classes for membrane systems. Zbl 1112.68065
Porreca, Antonio E.; Mauri, Giancarlo; Zandron, Claudio
2006
A note on a conjecture of Duval and Sturmian words. Zbl 1013.68152
Mignosi, Filippo; Zamboni, Luca Q.
2002
A note on the number of squares in a partial word with one hole. Zbl 1192.68496
2009
Iteration of rational transductions. Zbl 0962.68090
Terlutte, Alain; Simplot, David
2000
A lower bound for reversible automata. Zbl 0987.68043
Héam, Pierre-Cyrille
2000
Two-variable word equations. Zbl 0977.68070
Ilie, Lucian; Plandowski, Wojciech
2000
Hereditary properties of words. Zbl 1132.68048
Balogh, József; Bollobás, Béla
2005
Cricular splicing and regularity. Zbl 1082.68048
Bonizzoni, Paola; De Felice, Clelia; Mauri, Giancarlo; Zizza, Rosalba
2004
Undecidability of topological and arithmetical properties of infinitary rational relations. Zbl 1112.03312
Finkel, Olivier
2003
Undecidability of infinite Post correspondence problem for instances of size 9. Zbl 1114.03035
Halava, Vesa; Harju, Tero
2006
Substitutions by motives of dimension 1. (Substitutions par des motifs en dimension 1.) Zbl 1144.11020
Fogg, N. Pytheas
2007
Object oriented institutions to specify symbolic computation systems. Zbl 1146.68481
Domínguez, César; Lambán, Laureano; Rubio, Julio
2007
Hierarchies of function classes defined by the first-value operator. Zbl 1146.03032
Hemmerling, Armin
2008
Decision problems among the main subfamilies of rational relations. Zbl 1112.03008
Carton, Olivier; Choffrut, Christian; Grigorieff, Serge
2006
$$\mu$$-bicomplete categories and parity games. Zbl 1024.18001
Santocanale, Luigi
2002
Equational description of pseudovarieties of homomorphisms. Zbl 1045.20049
Kunc, Michal
2003
Highly undecidable problems for infinite computations. Zbl 1171.03024
Finkel, Olivier
2009
Left-to-right regular languages and two-way restarting automata. Zbl 1176.68107
Otto, Friedrich
2009
On-line finite automata for addition in some numeration systems. Zbl 0927.68052
Frougny, Christiane
1999
Immunity and simplicity for exact counting and other counting classes. Zbl 0946.68051
Rothe, J.
1999
Topologies, continuity and bisimulations. Zbl 0940.03021
Davoren, J. M.
1999
Computing the Rabin index of a parity automaton. Zbl 0958.68089
Carton, Olivier; Maceiras, Ramón
1999
Universality of reversible hexagonal cellular automata. Zbl 0953.68099
Morita, Kenichi; Margenstern, Maurice; Imai, Katsunobu
1999
Forbidden factors and fragment assembly. Zbl 1005.68122
Mignosi, F.; Restivo, A.; Sciortino, M.
2001
Series which are both max-plus and min-plus rational are unambiguous. Zbl 1085.68081
Lombardy, Sylvain; Mairesse, Jean
2006
Sequences of low arithmetical complexity. Zbl 1110.68116
Avgustinovich, Sergey V.; Cassaigne, Julien; Frid, Anna E.
2006
Returning and non-returning parallel communicating finite automata are equivalent. Zbl 1146.68385
Choudhary, Ashish; Krithivasan, Kamala; Mitrana, Victor
2007
Recursive coalgebras of finitary functors. Zbl 1147.18001
Adámek, Jiří; Lücke, Dominik; Milius, Stefan
2007
A morphic approach to combinatorial games: the Tribonacci case. Zbl 1143.91314
Duchêne, Eric; Rigo, Michel
2008
A hierarchy for circular codes. Zbl 1155.68069
Pirillo, Giuseppe
2008
Feedback, trace and fixed-point semantics. Zbl 1050.68100
Katis, P.; Sabadini, Nicoletta; Walters, Robert F. C.
2002
Minimal NFA and biRFSA languages. Zbl 1166.68025
Latteux, Michel; Roos, Yves; Terlutte, Alain
2009
Complexity and linear cellular automata. (Complexité et automates cellulaires linéaires.) Zbl 0988.68116
Berthé, Valérie
2000
Characteristic formulae for timed autoamta. Zbl 0974.68121
Aceto, Luca; Ingólfsdóttir, Anna; Pedersen, Mikkel Lykke; Poulsen, Jan
2000
The pseudovariety of semigroups of triangular matrices over a finite field. Zbl 1086.20029
Almeida, Jorge; Margolis, Stuart W.; Volkov, Mikhail V.
2005
On the number of dissimilar Pfaffian orientations of graphs. Zbl 1069.05066
de Carvalho, Marcelo H.; Lucchesi, Cláudio L.; Murty, U. S. R.
2005
Similarity relations and cover automata. Zbl 1102.68057
Champarnaud, Jean-Marc; Guingne, Franck; Hansel, Georges
2005
A test-set for $$k$$-power-free binary morphisms. Zbl 1010.68102
Wlazinski, F.
2001
On the topological complexity of infinitary rational relations. Zbl 1112.03313
Finkel, Olivier
2003
Episturmian words: a survey. Zbl 1182.68155
Glen, Amy; Justin, Jacques
2009
Measuring the problem-relevant information in input. Zbl 1176.68089
Dobrev, Stefan; Královič, Rastislav; Pardubská, Dana
2009
Dejean’s conjecture holds for $${n\geq 27}$$. Zbl 1192.68497
2009
Hyper-minimizing minimized deterministic finite state automata. Zbl 1170.68023
Badr, Andrew; Geffert, Viliam; Shipman, Ian
2009
Least periods of factors of infinite words. Zbl 1162.68510
Currie, James D.; Saari, Kalle
2009
Efficient validation and construction of border arrays and validation of string matching automata. Zbl 1166.68033
Duval, Jean-Pierre; Lecroq, Thierry; Lefebvre, Arnaud
2009
A note on the number of squares in a partial word with one hole. Zbl 1192.68496
2009
Highly undecidable problems for infinite computations. Zbl 1171.03024
Finkel, Olivier
2009
Left-to-right regular languages and two-way restarting automata. Zbl 1176.68107
Otto, Friedrich
2009
Minimal NFA and biRFSA languages. Zbl 1166.68025
Latteux, Michel; Roos, Yves; Terlutte, Alain
2009
Hierarchies and reducibilities on regular languages related to modulo counting. Zbl 1174.03016
Selivanov, Victor L.
2009
Directive words of episturmian words: equivalences and normalization. Zbl 1166.68034
Glen, Amy; Levé, Florence; Richomme, Gwénaël
2009
On critical exponents in fixed points of $$k$$-uniform binary morphisms. Zbl 1170.68034
Krieger, Dalia
2009
Labeled shortest paths in digraphs with negative and positive edge weights. Zbl 1175.68196
Bradford, Phillip G.; Thomas, David A.
2009
Palindromes in infinite ternary words. Zbl 1191.68476
Balková, L&rsquo;ubomíra; Pelantová, Edita; Starosta, Štěpán
2009
Equations on partial words. Zbl 1170.68032
Blanchet-Sadri, Francine; Blair, D. Dakota; Lewis, Rebeca V.
2009
Cycle and path embedding on 5-ary $$n$$-cubes. Zbl 1156.68041
Lin, Tsong-Jie; Hsieh, Sun-Yuan; Huang, Hui-Ling
2009
On the power of randomization for job shop scheduling with $$k$$-units length tasks. Zbl 1166.68041
Mömke, Tobias
2009
On context-free rewriting with a simple restriction and its computational completeness. Zbl 1171.68017
Masopust, Tomáš; Meduna, Alexander
2009
On the proper intervalization of colored caterpillar trees. Zbl 1192.68339
Àlvarez, Carme; Serna, Maria
2009
The theorem of Fine and Wilf for relational periods. Zbl 1166.68035
Halava, Vesa; Harju, Tero; Kärki, Tomi
2009
A note on dual approximation algorithms for class constrained bin packing problems. Zbl 1166.68368
Xavier, Eduardo C.; Miyazawa, Flàvio Keidi
2009
Polynomial languages with finite antidictionaries. Zbl 1166.68026
Shur, Arseny M.
2009
Tree automata and automata on linear orderings. Zbl 1166.68022
Bruyère, Véronique; Carton, Olivier; Sénizergues, Géraud
2009
A game theoretical approach to the algebraic counterpart of the Wagner hierarchy. I. Zbl 1175.03021
Cabessa, Jérémie; Duparc, Jacques
2009
A game theoretical approach to the algebraic counterpart of the Wagner hierarchy. II. Zbl 1175.03022
Cabessa, Jérémie; Duparc, Jacques
2009
Dynamic overloading with copy semantics in object-oriented languages: a formal account. Zbl 1175.68094
Bettini, Lorenzo; Capecchi, Sara; Venneri, Betti
2009
Squares and cubes in Sturmian sequences. Zbl 1176.68150
Dubickas, Artūras
2009
Palindromic complexity of infinite words associated with non-simple Parry numbers. Zbl 1156.68043
Balková, L&rsquo;ubomíra; Masáková, Zuzana
2009
A Burnside approach to the termination of Mohri’s algorithm for polynomially ambiguous min-plus-automata. Zbl 1155.68042
Kirsten, Daniel
2008
On some problems related to palindrome closure. Zbl 1155.68061
Bucci, Michelangelo; de Luca, Aldo; De Luca, Alessandro; Zamboni, Luca Q.
2008
State complexity of cyclic shift. Zbl 1144.68033
Jirásková, Galina; Okhotin, Alexander
2008
On extremal properties of the Fibonacci word. Zbl 1155.68062
Cassaigne, Julien
2008
Comparing complexity functions of a language and its extendable part. Zbl 1149.68055
Shur, Arseny M.
2008
Hierarchies of function classes defined by the first-value operator. Zbl 1146.03032
Hemmerling, Armin
2008
A morphic approach to combinatorial games: the Tribonacci case. Zbl 1143.91314
Duchêne, Eric; Rigo, Michel
2008
A hierarchy for circular codes. Zbl 1155.68069
Pirillo, Giuseppe
2008
When is the orbit algebra of a group an integral domain? Proof of a conjecture of P. J. Cameron. Zbl 1146.03015
Pouzet, Maurice
2008
On an algorithm to decide whether a free group is a free factor of another. Zbl 1146.20021
Silva, Pedro V.; Weil, Pascal
2008
Some algebraic properties of machine poset of infinite words. Zbl 1167.68030
Belovs, Aleksandrs
2008
Drunken man infinite words complexity. Zbl 1188.68217
Le Gonidec, Marion
2008
Two sided sand piles model and unimodal sequences. Zbl 1149.68408
Phan, Thi Ha Duong
2008
A complete characterization of primitive recursive intensional behaviours. Zbl 1148.68388
Valarcher, P.
2008
Weakly maximal decidable structures. Zbl 1149.03015
Bès, Alexis; Cégielski, Patrick
2008
Efficiency of automata in semi-commutation verification techniques. Zbl 1144.68039
Cécé, Gérard; Héam, Pierre-Cyrille; Mainier, Yann
2008
D0L sequence equivalence is in P for fixed alphabets. Zbl 1144.68037
Ruohonen, Keijo
2008
Dejean’s conjecture and letter frequency. Zbl 1147.68612
Chalopin, Jérémie; Ochem, Pascal
2008
Tree inclusion problems. Zbl 1149.68040
Cégielski, Patrick; Guessarian, Irène; Matiyasevich, Yuri
2008
Arithmetization of the field of reals with exponentiation – extended abstract. Zbl 1144.03027
Boughattas, Sedki; Ressayre, Jean-Pierre
2008
Computing the $$j$$th solution of a first-order query. Zbl 1149.68028
Bagan, Guillaume; Durand, Arnaud; Grandjean, Eitenne; Olive, Frédéric
2008
On varieties of literally idempotent languages. Zbl 1151.68032
Klíma, Ondřej; Polák, Libor
2008
Traces of term-automatic graphs. Zbl 1149.68395
Meyer, Antoine
2008
About the domino problem in the hyperbolic plane from an algorithmic point of view. Zbl 1237.52016
Margenstern, Maurice
2008
An intrinsically non minimal-time Minsky-like 6-states solution to the firing squad synchronization problem. Zbl 1148.68410
Yunès, Jean-Baptiste
2008
Deciding whether a relation defined in Presburger logic can be defined in weaker logics. Zbl 1158.03007
Choffrut, Christian
2008
On the continuity set of an omega rational function. Zbl 1149.03028
Carton, Olivier; Finkel, Olivier; Simonnet, Pierre
2008
Census algorithms for Chinese remainder pseudorank. Zbl 1141.11324
Laing, David; Litow, Bruce
2008
A hierarchy of automatic $$\omega$$-words having a decidable MSO theory. Zbl 1152.03030
Bárány, Vince
2008
An automata-theoretic approach to the study of the intersection of two submonoids of a free monoid. Zbl 1149.68058
Giambruno, Laura; Restivo, Antonio
2008
Compatibility relations on codes and free monoids. Zbl 1149.68069
Kärki, Tomi
2008
On substitution invariant Sturmian words: an application of Rauzy fractals. Zbl 1140.11014
Berthé, Valérie; Ei, Hiromi; Ito, Shunji; Rao, Hui
2007
An algorithm for deciding if a polyomino tiles the plane. Zbl 1146.68409
Gambini, Ian; Vuillon, Laurent
2007
Substitutions by motives of dimension 1. (Substitutions par des motifs en dimension 1.) Zbl 1144.11020
Fogg, N. Pytheas
2007
Object oriented institutions to specify symbolic computation systems. Zbl 1146.68481
Domínguez, César; Lambán, Laureano; Rubio, Julio
2007
Returning and non-returning parallel communicating finite automata are equivalent. Zbl 1146.68385
Choudhary, Ashish; Krithivasan, Kamala; Mitrana, Victor
2007
Recursive coalgebras of finitary functors. Zbl 1147.18001
Adámek, Jiří; Lücke, Dominik; Milius, Stefan
2007
An upper bound for transforming self-verifying automata into deterministic ones. Zbl 1130.68067
Assent, Ira; Seibert, Sebastian
2007
A graph approach to computing nondeterminacy in substitutional dynamical systems. Zbl 1165.37006
Carlsen, Toke M.; Eilers, Søren
2007
Combinatorial and arithmetical properties of infinite words associated with non-simple quadratic Parry numbers. Zbl 1144.11009
Balková, Lubomíra; Pelantová, Edita; Turek, Ondřej
2007
Balance properties of the fixed point of the substitution associated to quadratic simple Pisot numbers. Zbl 1146.68410
Turek, Ondřej
2007
Decidability of code properties. Zbl 1203.68084
Fernau, Henning; Reinhardt, Klaus; Staiger, Ludwig
2007
Formally certified floating-point filters for homogeneous geometric predicates. Zbl 1133.65010
Melquiond, Guillaume; Pion, Sylvain
2007
Three notes on the complexity of model checking fixpoint logic with Chop. Zbl 1133.68046
Lange, Martin
2007
Defect theorem in the plane. Zbl 1144.68048
2007
Uniformly bounded duplication codes. Zbl 1144.68047
Leupold, Peter; Mitrana, Victor
2007
Deciding inclusion of set constants over infinite non-strict data structures. Zbl 1146.68353
Schmidt-Schauss; Manfred; Sabel, David; Schütz, Marko
2007
Real and complex pseudozero sets for polynomials with applications. Zbl 1163.65023
Graillat, Stef; Langlois, Philippe
2007
Fast and correctly rounded logarithms in double-precision. Zbl 1132.65302
de Dinechin, Florent; Lauter, Christoph; Muller, Jean-Michel
2007
Learning tree languages from text. Zbl 1144.68031
Fernau, Henning
2007
A generator of morphisms for infinite words. Zbl 1110.68122
Ochem, Pascal
2006
On Christoffel classes. Zbl 1085.68116
Borel, Jean-Pierre; Reutenauer, Christophe
2006
Unambiguous recognizable two-dimensional languages. Zbl 1112.68085
Anselmo, Marcella; Giammarresi, Dora; Madonia, Maria; Restivo, Antonio
2006
Theories of orders on the set of words. Zbl 1098.03021
Kuske, Dietrich
2006
Quantum finite automata with control language. Zbl 1112.68064
Mereghetti, Carlo; Palano, Beatrice
2006
Picture codes. Zbl 1117.94015
Bozapalidis, Symeon; Grammatikopoulou, Archontia
2006
Complexity classes for membrane systems. Zbl 1112.68065
Porreca, Antonio E.; Mauri, Giancarlo; Zandron, Claudio
2006
Undecidability of infinite Post correspondence problem for instances of size 9. Zbl 1114.03035
Halava, Vesa; Harju, Tero
2006
Decision problems among the main subfamilies of rational relations. Zbl 1112.03008
Carton, Olivier; Choffrut, Christian; Grigorieff, Serge
2006
Series which are both max-plus and min-plus rational are unambiguous. Zbl 1085.68081
Lombardy, Sylvain; Mairesse, Jean
2006
Sequences of low arithmetical complexity. Zbl 1110.68116
Avgustinovich, Sergey V.; Cassaigne, Julien; Frid, Anna E.
2006
Squares and overlaps in the Thue-Morse sequence and some variants. Zbl 1110.68117
2006
A little more about morphic Sturmian words. Zbl 1110.68118
Fagnot, Isabelle
2006
On a complete set of operations for factorizing codes. Zbl 1091.94017
De Felice, Clelia
2006
On possible growths of arithmetical complexity. Zbl 1110.68120
Frid, Anna E.
2006
Graph fibrations, graph isomorphism, and PageRank. Zbl 1112.68002
Boldi, Paolo; Lonati, Violetta; Santini, Massimo; Vigna, Sebastiano
2006
Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP. Zbl 1085.68056
Hemaspaandra, Edith; Rothe, Jörg; Spakowski, Holger
2006
The accessibility of an access structure. Zbl 1117.94014
Carreras, Francesc; Magaña, Antonio; Munuera, Carlos
2006
On multiperiodic words. Zbl 1110.68121
Holub, Štěpán
2006
On the simplest centralizer of a language. Zbl 1112.68097
Massazza, Paolo; Salmela, Petri
2006
String distances and intrusion detection: bridging the gap between formal languages and computer security. Zbl 1112.68017
Bruschi, Danilo; Pighizzini, Giovanni
2006
...and 161 more Documents
all top 5

### Cited by 1,568 Authors

 29 Okhotin, Alexander 22 de Luca, Aldo 22 Shallit, Jeffrey O. 21 Zamboni, Luca Quardo 20 Selivanov, Viktor L’vovich 19 Ochem, Pascal 18 Teh, Wen Chean 17 De Felice, Clelia 16 Cassaigne, Julien 16 Palano, Beatrice 15 Mereghetti, Carlo 15 Pelantová, Edita 15 Restivo, Antonio 15 Reutenauer, Christophe 15 Richomme, Gwénaël 15 Shur, Arseny M. 14 Blanchet-Sadri, Francine 14 Finkel, Olivier 14 Salomaa, Arto Kustaa 14 Subramanian, Kumbakonam Govindarajan 13 De Luca, Alessandro 13 Harju, Tero 13 Perrin, Dominique 13 Rampersad, Narad 13 Rigo, Michel 12 Anselmo, Marcella 12 Berthé, Valérie 12 Corradini, Andrea 12 Holzer, Markus 12 Kutrib, Martin 12 Lucas, Salvador 12 Madonia, Maria 11 Glen, Amy 11 Milius, Stefan 11 Pirillo, Giuseppe 11 Sciortino, Marinella 10 Atanasiu, Adrian 10 Carpi, Arturo 10 Gadducci, Fabio 10 Jeż, Artur 10 Karhumaki, Juhani 9 Bollig, Beate 9 Giammarresi, Dora 9 Komm, Dennis 9 Královič, Richard 9 Mahalingam, Kalpana 9 Potapov, Igor 8 Baldan, Paolo 8 Bera, Somnath 8 Bucci, Michelangelo 8 Carton, Olivier 8 Currie, James D. 8 Dolce, Francesco 8 Frid, Anna Èduardovna 8 König, Barbara 8 Maletti, Andreas 8 Otto, Friedrich 8 Paulusma, Daniël 8 Pin, Jean-Eric 8 Silva, Pedro V. 8 Skrzypczak, Michał 8 Yu, Sheng 7 Adámek, Jiří 7 Behr, Nicolas 7 Böckenhauer, Hans-Joachim 7 D’Alessandro, Flavio 7 Ehrig, Hartmut 7 Fici, Gabriele 7 Holub, Štěpán 7 Honkala, Juha 7 Justin, Jacques 7 Leroy, Julien 7 Masáková, Zuzana 7 Michel, Christian J. 7 Nowotka, Dirk 7 Pattinson, Dirk 7 Poovanandran, Ghajendran 7 Qiu, Daowen 7 Rosenfeld, Matthieu 7 Rytter, Wojciech 7 Salomaa, Kai T. 7 Schröder, Lutz 7 Zizza, Rosalba 6 Badkobeh, Golnaz 6 Berstel, Jean 6 Bianchi, Maria Paola 6 Bonchi, Filippo 6 Choffrut, Christian 6 de Figueiredo, Celina M. Herrera 6 Ésik, Zoltán 6 Goncharov, Sergeĭ Savost’yanovich 6 Heindel, Tobias 6 Inenaga, Shunsuke 6 Jirásková, Galina 6 Klasing, Ralf 6 Komenda, Jan 6 Lahaye, Sébastien 6 Li, Lvzhou 6 Malcher, Andreas 6 Mercaş, Robert George ...and 1,468 more Authors
all top 5

### Cited in 184 Journals

 314 Theoretical Computer Science 91 International Journal of Foundations of Computer Science 67 RAIRO. Theoretical Informatics and Applications 65 Information and Computation 35 RAIRO. Theoretical Informatics and Applications 33 Discrete Applied Mathematics 33 Information Processing Letters 33 Journal of Computer and System Sciences 31 Theory of Computing Systems 24 MSCS. Mathematical Structures in Computer Science 21 European Journal of Combinatorics 20 Logical Methods in Computer Science 19 International Journal of Algebra and Computation 17 The Electronic Journal of Combinatorics 15 Acta Informatica 15 Annals of Pure and Applied Logic 11 Discrete Mathematics 10 Journal of Combinatorial Theory. Series A 10 Algorithmica 9 Journal of Discrete Algorithms 8 Advances in Applied Mathematics 8 The Journal of Logic and Algebraic Programming 7 Journal of Functional Programming 6 Discrete Event Dynamic Systems 6 Computational Complexity 6 Integers 5 Journal of Pure and Applied Algebra 5 The Journal of Symbolic Logic 5 Transactions of the American Mathematical Society 5 Journal of Automated Reasoning 5 Archive for Mathematical Logic 5 International Journal of Bifurcation and Chaos in Applied Sciences and Engineering 5 Applied Categorical Structures 5 Annals of Mathematics and Artificial Intelligence 5 Discrete Mathematics and Theoretical Computer Science. DMTCS 5 Journal of Logical and Algebraic Methods in Programming 4 Journal of Number Theory 4 Monatshefte für Mathematik 4 International Journal of Computer Mathematics 4 Applicable Algebra in Engineering, Communication and Computing 4 Journal of Combinatorial Optimization 4 Fundamenta Informaticae 3 Mathematics of Computation 3 Algebra and Logic 3 Annales de l’Institut Fourier 3 Journal of Algebra 3 Proceedings of the American Mathematical Society 3 Semigroup Forum 3 SIAM Journal on Computing 3 Siberian Mathematical Journal 3 Ergodic Theory and Dynamical Systems 3 Journal of Symbolic Computation 3 Formal Aspects of Computing 3 Machine Learning 3 Expositiones Mathematicae 3 Cybernetics and Systems Analysis 3 Combinatorics, Probability and Computing 3 Journal of Mathematical Sciences (New York) 2 Bulletin of the Australian Mathematical Society 2 Mathematical Notes 2 Chaos, Solitons and Fractals 2 Advances in Mathematics 2 Automatica 2 Canadian Journal of Mathematics 2 Information Sciences 2 Journal of Combinatorial Theory. Series B 2 Journal of Computational and Applied Mathematics 2 Discrete & Computational Geometry 2 Computers & Operations Research 2 The Annals of Applied Probability 2 Pattern Recognition 2 Indagationes Mathematicae. New Series 2 Journal of Applied Non-Classical Logics 2 Theory and Applications of Categories 2 Journal of Automata, Languages and Combinatorics 2 Journal of Integer Sequences 2 Higher-Order and Symbolic Computation 2 Bulletin of the Malaysian Mathematical Sciences Society. Second Series 2 Natural Computing 2 Quantum Information Processing 2 Journal of Algebra and its Applications 2 Discrete Mathematics, Algorithms and Applications 2 Journal of Theoretical Biology 2 Computer Science Review 2 Journal of Mathematics 2 Journal of Discrete Mathematics 2 Journal of Membrane Computing 1 Artificial Intelligence 1 Communications in Algebra 1 Computers & Mathematics with Applications 1 Communications in Mathematical Physics 1 International Journal of Control 1 International Journal of General Systems 1 International Journal of Theoretical Physics 1 Israel Journal of Mathematics 1 Journal d’Analyse Mathématique 1 Journal of Mathematical Physics 1 Journal of Statistical Physics 1 Letters in Mathematical Physics 1 Rocky Mountain Journal of Mathematics ...and 84 more Journals
all top 5

### Cited in 41 Fields

 1,206 Computer science (68-XX) 221 Mathematical logic and foundations (03-XX) 143 Combinatorics (05-XX) 85 Category theory; homological algebra (18-XX) 78 Number theory (11-XX) 65 Group theory and generalizations (20-XX) 55 Dynamical systems and ergodic theory (37-XX) 40 Information and communication theory, circuits (94-XX) 38 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 33 Order, lattices, ordered algebraic structures (06-XX) 31 Quantum theory (81-XX) 22 Operations research, mathematical programming (90-XX) 18 Linear and multilinear algebra; matrix theory (15-XX) 14 Convex and discrete geometry (52-XX) 12 General algebraic systems (08-XX) 12 Biology and other natural sciences (92-XX) 12 Systems theory; control (93-XX) 11 Numerical analysis (65-XX) 10 General topology (54-XX) 10 Probability theory and stochastic processes (60-XX) 8 History and biography (01-XX) 8 Functional analysis (46-XX) 7 Measure and integration (28-XX) 6 Field theory and polynomials (12-XX) 5 Nonassociative rings and algebras (17-XX) 5 Operator theory (47-XX) 5 Manifolds and cell complexes (57-XX) 4 Commutative algebra (13-XX) 4 Topological groups, Lie groups (22-XX) 4 Algebraic topology (55-XX) 3 General and overarching topics; collections (00-XX) 3 Algebraic geometry (14-XX) 3 Associative rings and algebras (16-XX) 3 $$K$$-theory (19-XX) 3 Statistical mechanics, structure of matter (82-XX) 2 Difference and functional equations (39-XX) 2 Statistics (62-XX) 1 Real functions (26-XX) 1 Functions of a complex variable (30-XX) 1 Partial differential equations (35-XX) 1 Differential geometry (53-XX)