zbMATH — the first resource for mathematics

Developments in language theory. 12th international conference, DLT 2008, Kyoto, Japan, September 16–19, 2008. Proceedings. (English) Zbl 1147.68007
Lecture Notes in Computer Science 5257. Berlin: Springer (ISBN 978-3-540-85779-2/pbk). xiii, 544 p. (2008).

Show indexed articles as search result.

The articles of this volume will be reviewed individually. The preceding conference has been reviewed (see Zbl 1119.68010).
Indexed articles:
Ésik, Zoltán, Iteration semirings, 1-20 [Zbl 1161.68598]
Hirvensalo, Mika, Various aspects of finite quantum automata. (Extended abstract), 21-33 [Zbl 1161.68535]
Hromkovič, Juraj; Schnitger, Georg, On the hardness of determining small NFA’s and of proving lower bounds on their sizes, 34-55 [Zbl 1159.68017]
Jančar, Petr, Selected ideas used for decidability and undecidability of bisimilarity, 56-71 [Zbl 1161.68621]
Shallit, Jeffrey, The Frobenius problem and its generalizations, 72-83 [Zbl 1161.11319]
D’Alessandro, Flavio; Varricchio, Stefano, Well quasi-orders in formal language theory, 84-95 [Zbl 1161.68024]
Ada, Anil, On the non-deterministic communication complexity of regular languages, 96-107 [Zbl 1161.68597]
Allauzen, Cyril; Mohri, Mehryar; Rastogi, Ashish, General algorithms for testing the ambiguity of finite automata, 108-120 [Zbl 1161.68507]
Atig, Mohamed Faouzi; Bollig, Benedikt; Habermehl, Peter, Emptiness of multi-pushdown automata is 2ETIME-complete, 121-133 [Zbl 1161.68509]
Bassino, Frédérique; Giambruno, Laura; Nicaud, Cyril, The average state complexity of the star of a finite set of words is linear, 134-145 [Zbl 1161.68510]
Bordihn, Henning; Kutrib, Martin; Malcher, Andreas, On the computational capacity of parallel communicating finite automata, 146-157 [Zbl 1161.68513]
Bucci, Michelangelo; de Luca, Aldo; De Luca, Alessandro, On a generalization of standard episturmian morphisms, 158-169 [Zbl 1159.68027]
Calude, Cristian S.; Nies, André; Staiger, Ludwig; Stephan, Frank, Universal recursively enumerable sets of strings, 170-182 [Zbl 1159.68011]
Calude, Cristian S.; Zimand, Marius, Algorithmically independent sequences, 183-195 [Zbl 1159.68012]
Cassaigne, Julien; Kärki, Tomi; Zamboni, Luca Q., Relationally periodic sequences and subword complexity, 196-205 [Zbl 1159.68029]
Crochemore, Maxime; Fazekas, Szilárd Zsolt; Iliopoulos, Costas; Jayasekera, Inuka, Bounds on powers in strings, 206-215 [Zbl 1159.68014]
Csima, Barbara F.; Khoussainov, Bakhadyr, When is reachability intrinsically decidable?, 216-227 [Zbl 1161.68037]
Csuhaj-Varjú, Erzsébet; Dassow, Jürgen; Vaszil, György, Some new modes of competence-based derivations in CD grammar systems, 228-239 [Zbl 1161.68501]
Carpi, Arturo; D’Alessandro, Flavio, The synchronization problem for strongly transitive automata, 240-251 [Zbl 1161.68517]
de Souza, Rodrigo, On the decidability of the equivalence for \(k\)-valued transducers. (Extended abstract), 252-263 [Zbl 1161.68556]
Dennunzio, Alberto; Formenti, Enrico, Decidable properties of 2D cellular automata, 264-275 [Zbl 1161.68602]
Durand, Bruno; Romashchenko, Andrei; Shen, Alexander, Fixed point and aperiodic tilings, 276-288 [Zbl 1161.68033]
Engelfriet, Joost; Lilin, Eric; Maletti, Andreas, Extended multi bottom-up tree transducers, 289-300 [Zbl 1161.68523]
Esparza, Javier; Kiefer, Stefan; Luttenberger, Michael, Derivation tree analysis for accelerated fixed-point computation, 301-313 [Zbl 1161.68880]
Filiot, Emmanuel; Talbot, Jean-Marc; Tison, Sophie, Tree automata with global constraints, 314-326 [Zbl 1161.68525]
Freydenberger, Dominik D.; Reidenbach, Daniel, Bad news on decision problems for patterns, 327-338 [Zbl 1161.68526]
Gawrychowski, Paweł; Krieger, Dalia; Rampersad, Narad; Shallit, Jeffrey, Finding the growth rate of a regular of context-free language in polynomial time, 339-358 [Zbl 1161.68528]
Geffert, Viliam; Mereghetti, Carlo; Palano, Beatrice, More concise representation of regular languages by automata and regular expressions, 359-370 [Zbl 1161.68529]
Glöckler, Jens, A taxonomy of deterministic forgetting automata, 371-382 [Zbl 1161.68531]
Gruber, Hermann; Holzer, Markus, Provably shorter regular expressions from deterministic finite automata. (Extended abstract), 383-395 [Zbl 1161.68533]
Hadravová, Jana; Holub, Štěpán, Large simple binary equality words, 396-407 [Zbl 1159.68030]
Holub, Štěpán; Nowotka, Dirk, On the relation between periodicity and unbordered factors of finite words, 408-418 [Zbl 1159.68031]
Ito, Masami; Kari, Lila; Kincaid, Zachary; Seki, Shinnosuke, Duplication in DNA sequences, 419-430 [Zbl 1161.68537]
Jirásková, Galina, On the state complexity of complements, stars, and reversals of regular languages, 431-442 [Zbl 1161.68539]
Jirásková, Galina; Okhotin, Alexander, On the state complexity of operations on two-way finite automata, 443-454 [Zbl 1161.68540]
Kapoutsis, Christos; Královič, Richard; Mömke, Tobias, On the size complexity of rotating and sweeping automata, 455-466 [Zbl 1161.68541]
Karhumäki, Juhani; Saarela, Aleksi, An analysis and a reproof of Hmelevskii’s theorem. (Extended abstract), 467-478 [Zbl 1161.68706]
Klíma, Ondřej; Polák, Libor, Hierarchies of piecewise testable languages, 479-490 [Zbl 1159.68023]
Kuske, Dietrich; Meinecke, Ingmar, Construction of tree automata from regular expressions, 491-503 [Zbl 1159.68018]
Mantaci, Roberto; Mantaci, Sabrina; Restivo, Antonio, Balance properties and distribution of squares in circular words, 504-515 [Zbl 1159.68032]
Morin, Rémi, MSO logic for unambiguous shared-memory systems, 516-528 [Zbl 1159.68025]
Selivanov, Victor L.; Wagner, Klaus W., Complexity of topological properties of regular \(\omega \)-languages, 529-542 [Zbl 1159.68019]

68-06 Proceedings, conferences, collections, etc. pertaining to computer science
68Q45 Formal languages and automata
00B25 Proceedings of conferences of miscellaneous specific interest
Full Text: DOI