Developments in Language Theory 12th International Conference, DLT 2008, Kyoto, Japan, September 16-19, 2008, Proceedings /

This book constitutes the refereed proceedings of the 12th International Conference on Developments in Language Theory, DLT 2008, held in Kyoto, Japan, September 2008. The 36 revised full papers presented together with 6 invited papers were carefully reviewed and selected from 102 submissions. All i...

Full description

Corporate Author: SpringerLink (Online service)
Other Authors: Ito, Masami. (Editor, http://id.loc.gov/vocabulary/relators/edt), Toyama, Masafumi. (Editor, http://id.loc.gov/vocabulary/relators/edt)
Language:English
Published: Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2008.
Edition:1st ed. 2008.
Series:Theoretical Computer Science and General Issues ; 5257
Subjects:
Online Access:https://doi.org/10.1007/978-3-540-85780-8
LEADER 05884nam a22005655i 4500
001 978-3-540-85780-8
003 DE-He213
005 20210624165201.0
007 cr nn 008mamaa
008 100301s2008 gw | s |||| 0|eng d
020 |a 9783540857808  |9 978-3-540-85780-8 
024 7 |a 10.1007/978-3-540-85780-8  |2 doi 
050 4 |a QA8.9-10.3 
072 7 |a UYA  |2 bicssc 
072 7 |a MAT018000  |2 bisacsh 
072 7 |a UYA  |2 thema 
082 0 4 |a 005.131  |2 23 
245 1 0 |a Developments in Language Theory  |h [electronic resource] :  |b 12th International Conference, DLT 2008, Kyoto, Japan, September 16-19, 2008, Proceedings /  |c edited by Masami Ito, Masafumi Toyama. 
250 |a 1st ed. 2008. 
264 1 |a Berlin, Heidelberg :  |b Springer Berlin Heidelberg :  |b Imprint: Springer,  |c 2008. 
300 |a XIII, 544 p.  |b online resource. 
336 |a text  |b txt  |2 rdacontent 
337 |a computer  |b c  |2 rdamedia 
338 |a online resource  |b cr  |2 rdacarrier 
347 |a text file  |b PDF  |2 rda 
490 1 |a Theoretical Computer Science and General Issues ;  |v 5257 
505 0 |a Invited Talks -- Iteration Semirings -- Various Aspects of Finite Quantum Automata -- On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes -- Selected Ideas Used for Decidability and Undecidability of Bisimilarity -- The Frobenius Problem and Its Generalizations -- Well Quasi-orders in Formal Language Theory -- Contributed Papers -- On the Non-deterministic Communication Complexity of Regular Languages -- General Algorithms for Testing the Ambiguity of Finite Automata -- Emptiness of Multi-pushdown Automata Is 2ETIME-Complete -- The Average State Complexity of the Star of a Finite Set of Words Is Linear -- On the Computational Capacity of Parallel Communicating Finite Automata -- On a Generalization of Standard Episturmian Morphisms -- Universal Recursively Enumerable Sets of Strings -- Algorithmically Independent Sequences -- Relationally Periodic Sequences and Subword Complexity -- Bounds on Powers in Strings -- When Is Reachability Intrinsically Decidable? -- Some New Modes of Competence-Based Derivations in CD Grammar Systems -- The Synchronization Problem for Strongly Transitive Automata -- On the Decidability of the Equivalence for k-Valued Transducers -- Decidable Properties of 2D Cellular Automata -- Fixed Point and Aperiodic Tilings -- Extended Multi Bottom-Up Tree Transducers -- Derivation Tree Analysis for Accelerated Fixed-Point Computation -- Tree Automata with Global Constraints -- Bad News on Decision Problems for Patterns -- Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time -- More Concise Representation of Regular Languages by Automata and Regular Expressions -- A Taxonomy of Deterministic Forgetting Automata -- Provably Shorter Regular Expressions from Deterministic Finite Automata -- Large Simple Binary Equality Words -- On the Relation between Periodicity and Unbordered Factors of Finite Words -- Duplication in DNA Sequences -- On the State Complexity of Complements, Stars, and Reversals of Regular Languages -- On the State Complexity of Operations on Two-Way Finite Automata -- On the Size Complexity of Rotating and Sweeping Automata -- An Analysis and a Reproof of Hmelevskii’s Theorem -- Hierarchies of Piecewise Testable Languages -- Construction of Tree Automata from Regular Expressions -- Balance Properties and Distribution of Squares in Circular Words -- MSO Logic for Unambiguous Shared-Memory Systems -- Complexity of Topological Properties of Regular ?-Languages. 
520 |a This book constitutes the refereed proceedings of the 12th International Conference on Developments in Language Theory, DLT 2008, held in Kyoto, Japan, September 2008. The 36 revised full papers presented together with 6 invited papers were carefully reviewed and selected from 102 submissions. All important issues in language theory are addressed including grammars, acceptors and transducers for words, trees and graphs; algebraic theories of automata; algorithmic, combinatorial and algebraic properties of words and languages; variable length codes; symbolic dynamics; cellular automata; polyominoes and multidimensional patterns; decidability questions; image manipulation and compression; efficient text algorithms; relationships to cryptography, concurrency, complexity theory and logic; bio-inspired computing; quantum computing. 
650 0 |a Mathematical logic. 
650 0 |a Computers. 
650 0 |a Algorithms. 
650 0 |a Computer science—Mathematics. 
650 1 4 |a Mathematical Logic and Formal Languages.  |0 https://scigraph.springernature.com/ontologies/product-market-codes/I16048 
650 2 4 |a Computation by Abstract Devices.  |0 https://scigraph.springernature.com/ontologies/product-market-codes/I16013 
650 2 4 |a Algorithm Analysis and Problem Complexity.  |0 https://scigraph.springernature.com/ontologies/product-market-codes/I16021 
650 2 4 |a Discrete Mathematics in Computer Science.  |0 https://scigraph.springernature.com/ontologies/product-market-codes/I17028 
650 2 4 |a Symbolic and Algebraic Manipulation.  |0 https://scigraph.springernature.com/ontologies/product-market-codes/I17052 
700 1 |a Ito, Masami.  |e editor.  |4 edt  |4 http://id.loc.gov/vocabulary/relators/edt 
700 1 |a Toyama, Masafumi.  |e editor.  |4 edt  |4 http://id.loc.gov/vocabulary/relators/edt 
710 2 |a SpringerLink (Online service) 
773 0 |t Springer Nature eBook 
776 0 8 |i Printed edition:  |z 9783540858133 
776 0 8 |i Printed edition:  |z 9783540857792 
830 0 |a Theoretical Computer Science and General Issues ;  |v 5257 
856 4 0 |u https://doi.org/10.1007/978-3-540-85780-8 
912 |a ZDB-2-SCS 
912 |a ZDB-2-SXCS 
912 |a ZDB-2-LNC 
950 |a Computer Science (SpringerNature-11645) 
950 |a Computer Science (R0) (SpringerNature-43710)