8. DCFS 2006: Las Cruces, New Mexico, USA

Hing Leung, Giovanni Pighizzini (Eds.): 8th International Workshop on Descriptional Complexity of Formal Systems - DCFS 2006, Las Cruces, New Mexico, USA, June 21 - 23, 2006. Proceedings. New Mexico State University, Las Cruces, New Mexico, USA 2006

Invited Papers

Piotr Faliszewski, Lane A. Hemaspaandra: The Consequences of Eliminating NP Solutions. 1-15
Vinod Chirayath, Luc Longpré: Measuring privacy loss in statistical databases. 16-25
Andreas Malcher: Cellular Automata and Descriptional Complexity. 26-40
Jeffrey Shallit: New Directions in State Complexity. 41-45

Regular Papers

Tanbir Ahmed, Gösta Grahne: Parallel Composition of Finite State Activity Automata. 46-57
Marco Almeida, Nelma Moreira, Rogério Reis: Aspects of Enumeration and Generation with a String Automata Representation. 58-69
Franziska Biegler, Michael J. Burrell, Mark Daley: Regulated RNA rewriting: modelling RNA editing with guided insertion. 70-81
Franziska Biegler, Ian McQuillan, Kai Salomaa: An Infinite Hierarchy Induced by Depth Synchronization. 82-93
Haiming Chen, Mihai Ionescu, Andrei Paun, Gheorghe Paun, Bianca Popa: On Trace Languages Generated by (Small) Spiking Neural P Systems. 94-105
Alessandra Cherubini, Andrzej Kisielewicz: Recognizing Collapsing Words is co-NP-Complete. 106-117
Brendan J. Cordy, Kai Salomaa: Regular Approximations of Non-Regular Languages. 118-129
Jürgen Dassow, György Vaszil: On the Number of Active Symbols in Lindenmayer Systems. 130-140
Michael Domaratzki, Kai Salomaa: Transition Complexity of Language Operations. 141-152
Yuan Gao, Kai Salomaa, Sheng Yu: State Complexity of Catenation and Reversal Combined with Star. 153-164
Yo-Sub Han, Kai Salomaa, Derick Wood: State Complexity of Prefix-Free Regular Languages. 165-176
Markus Holzer, Martin Kutrib: The Size of Higman-Haines Sets. 177-187
J. Kavitha, L. Jeganathan, G. Sethuraman: Descriptional Complexity of Alternating Finite Automata. 188-198
Carlo Mereghetti, Beatrice Palano: Quantum Automata for some Multiperiodic Languages. 199-210
Frank Nießner, Ulrich Ultes-Nitsche: A Complete Characterization of Deterministic Regular Liveness Properties. 211-222

Short Papers

Cezar Câmpeanu, Andrei Paun, Jason R. Smith: Tight Bounds for the State Complexity of Deterministic Cover Automata. 223-231
Brian Cloteaux, Desh Ranjan: Some Separation Results Between Classes of Pointer Algorithms. 232-240
Jürgen Dassow, Bianca Truthe: On the Degree Complexity of Special Non-Context-Free Languages with Respect to PC Grammar Systems. 241-249
Rudolf Freund: Special Variants of P Systems with One Catalyst in One Membrane. 250-258
Rudolf Freund, Marion Oswald: A Small Universal Antiport P System with Forbidden Context. 259-266
Hermann Gruber, Markus Holzer: Results on the Average State and Transition Complexity of Finite Automata Accepting Finite Languages (Extended Abstract). 267-275
Joachim Kupke: A Powerful Tool in Lower-Bounding Constantly Ambiguous Automata. 276-284

Last update Thu May 24 04:16:11 2012 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page