Developments in Language Theory, DLT 2007

ACCEPTED PAPERS:

  • From Determinism to Non-determinism in Recognizable Two-dimensional Languages (Anselmo, Marcella; Giammarresi, Dora; Madonia, Maria)
  • Multi-Letter Reversible and Quantum Finite Automata (Belovs, Aleksandrs; Rosmanis, Ansis; Smotrovs, Juris)
  • Approximability and non-approximability results in computing the mean speedup of trace monoids (Bertoni, Alberto; Radicioni, Roberto)
  • The dynamics of cellular automata in shift-invariant topologies (Bienvenu, Laurent; Sablik, Mathieu)
  • Two Element Unavoidable Sets of Partial Words (Blanchet-Sadri, Francine; Brownstein, Naomi; Palumbo, Justin)
  • Hairpin Finite Automata (Bordihn, Henning; Holzer, Markus; Kutrib, Martin)
  • Characterizing Reduction Graphs for Gene Assembly in Ciliates (Brijder, Robert; Hoogeboom, Hendrik Jan)
  • Coding Partitions: Regularity, Maximality and Global Ambiguity (Burderi, Fabio; Béal, Marie-Pierre; Restivo, Antonio)
  • 2-Visibly Pushdown Automata (Carotenuto, Dario; Murano, Aniello; Peron, Adriano)
  • An efficient computation of the equation K-automaton of a regular K-expression (Champarnaud, Jean-Marc; Ouardi, Faissal; Ziadi, Djelloul)
  • An Extension of Newton's Method to omega-Continuous Semirings (Esparza, Javier; Kiefer, Stefan; Luttenberger, Michael)
  • Non-constructive Methods for Finite Probabilistic Automata (Freivalds, Rusins)
  • The Unambiguity of Segmented Morphisms (Freydenberger, Dominik; Reidenbach, Daniel)
  • Commutation of factorial languages (Frid, Anna)
  • Inapproximability of Nondeterministic State and Transition Complexity Assuming PTIME ≠ NP (Gruber, Hermann; Holzer, Markus)
  • State Complexity of Union and Intersection of Finite Languages (Han, Yo-Sub; Salomaa, Kai)
  • Bisimulation Minimisation for Weighted Tree Automata (Högberg, Johanna; Maletti, Andreas; May, Jonathan)
  • Conjunctive grammars can generate non-regular unary languages (Jez, Artur)
  • Deterministic Blow-ups of Minimal Nondeterministic Finite Automata over a Fixed Alphabet (Jirásek, Jozef; Jirásková, Galina; Szabari, Alexander)
  • Reduced languages as w-generators (Julia, Sandrine; Tran, Vinh Duc)
  • Avoiding Approximate Squares (Krieger, Dalia; Ochem, Pascal; Rampersad, Narad; Shallit, Jeffrey)
  • Duplication Roots (Leupold, Peter)
  • A Complexity Theory for Splicing Systems (Loos, Remco; Ogihara, Mitsunori)
  • Descriptional Complexity of Bounded Context-Free Languages (Malcher, Andreas; Pighizzini, Giovanni)
  • Definable Transductions and Weighted Logics for Texts (Mathissen, Christian)
  • A Star Operation for Star-Free Trace Languages (Ochmanski, Edward; Stawikowska, Krystyna)
  • Finite Automata on Unranked and Unordered DAGs (Priese, Lutz)
  • On Almost Periodicity Criteria for Morphic Sequences in Some Particular Cases (Pritykin, Yuri)
  • A local balance property of episturmian words(Richomme, Gwénaël)
  • Suffix Automata and Standard Sturmian Words (Sciortino, Marinella; Zamboni, Luca Q.)
  • Fine Hierarchy of Regular Aperiodic ∞-Languages (Selivanov, Victor)
  • On Transition Minimality of Bideterministic Automata (Tamm, Hellis)