000 04361nam a22005895i 4500
001 978-3-319-60252-3
003 DE-He213
005 20240423125717.0
007 cr nn 008mamaa
008 170602s2017 sz | s |||| 0|eng d
020 _a9783319602523
_9978-3-319-60252-3
024 7 _a10.1007/978-3-319-60252-3
_2doi
050 4 _aQA75.5-76.95
072 7 _aUYA
_2bicssc
072 7 _aCOM014000
_2bisacsh
072 7 _aUYA
_2thema
082 0 4 _a004.0151
_223
245 1 0 _aDescriptional Complexity of Formal Systems
_h[electronic resource] :
_b19th IFIP WG 1.02 International Conference, DCFS 2017, Milano, Italy, July 3-5, 2017, Proceedings /
_cedited by Giovanni Pighizzini, Cezar Câmpeanu.
250 _a1st ed. 2017.
264 1 _aCham :
_bSpringer International Publishing :
_bImprint: Springer,
_c2017.
300 _aX, 311 p. 76 illus.
_bonline resource.
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
_bPDF
_2rda
490 1 _aTheoretical Computer Science and General Issues,
_x2512-2029 ;
_v10316
505 0 _aSensing as a Complexity Measure -- Avoiding Overlaps in Pictures -- Descriptional Complexity and Operations - Two non-Classical Cases -- Applications of Transducers in Independent Languages, Word Distances, Codes -- On the Degree of Nondeterminism of Tree Adjoining Languages and Head Grammar Languages -- On the Average Complexity of Strong Star Normal Form -- Most Complex Non-Returning Regular Languages -- Uncountable realtime probabilistic classes -- A Parametrized Analysis of Algorithms on Hierarchical Graphs -- Graph-Controlled Insertion-Deletion Systems Generating Language Classes Beyond Linearity -- Computational Completeness of Networks of Evolutionary Processors with Elementary Polarizations and a Small Number of Processors -- Recognizing Union-Find trees built up using union-by-rank strategy is NP-complete -- Self-attraction removal from oritatami systems -- One-Time Nondeterministic Computations -- Kuratowski Algebras Generated by Factor-, Subword-, and Suffix-Free Languages -- Branching Measures and Nearly Acyclic NFAs -- Square on Deterministic, Alternating, and Boolean Finite Automata -- A Pumping Lemma for Ordered Restarting Automata -- Concise Representations of Reversible Automata -- State Complexity of Unary SV-XNFA with Different Acceptance Conditions -- Reset Complexity of Ideal Languages Over a Binary Alphabet -- 2-state 2-symbol Turing machines with periodic support produce regular sets -- State Complexity of Suffix Distance -- The quotient operation on input-driven pushdown automata.
520 _aThis book constitutes the proceedings of the 19th International Conference on Descriptional Complexity of Formal Systems, DCFS 2017, held in Milano, Italy, in July 2017. The 20 full papers presented together with 4 invited talks were carefully reviewed and selected from 26 submissions.Descriptional Complexity is a field in Computer Science that deals with the size of all kinds of objects that occur in computational models, such as turing machines, finite automata, grammars, splicing systems and others. The topics of this conference are related to all aspects of descriptional complexity.
650 0 _aComputer science.
650 0 _aMachine theory.
650 0 _aAlgorithms.
650 0 _aSoftware engineering.
650 1 4 _aComputer Science Logic and Foundations of Programming.
650 2 4 _aTheory of Computation.
650 2 4 _aFormal Languages and Automata Theory.
650 2 4 _aAlgorithms.
650 2 4 _aSoftware Engineering.
700 1 _aPighizzini, Giovanni.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
700 1 _aCâmpeanu, Cezar.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
710 2 _aSpringerLink (Online service)
773 0 _tSpringer Nature eBook
776 0 8 _iPrinted edition:
_z9783319602516
776 0 8 _iPrinted edition:
_z9783319602530
830 0 _aTheoretical Computer Science and General Issues,
_x2512-2029 ;
_v10316
856 4 0 _uhttps://doi.org/10.1007/978-3-319-60252-3
912 _aZDB-2-SCS
912 _aZDB-2-SXCS
912 _aZDB-2-LNC
942 _cSPRINGER
999 _c180906
_d180906