LEADER 04541nam 22006975 450 001 9910483540803321 005 20230221182612.0 010 $a3-319-60252-7 024 7 $a10.1007/978-3-319-60252-3 035 $a(CKB)4340000000061579 035 $a(DE-He213)978-3-319-60252-3 035 $a(MiAaPQ)EBC5577607 035 $a(MiAaPQ)EBC6306988 035 $a(Au-PeEL)EBL5577607 035 $a(OCoLC)992166635 035 $a(Au-PeEL)EBL6306988 035 $a(PPN)202990885 035 $a(EXLCZ)994340000000061579 100 $a20170602d2017 u| 0 101 0 $aeng 135 $aurnn|008mamaa 181 $ctxt$2rdacontent 182 $cc$2rdamedia 183 $acr$2rdacarrier 200 10$aDescriptional Complexity of Formal Systems $e19th IFIP WG 1.02 International Conference, DCFS 2017, Milano, Italy, July 3-5, 2017, Proceedings /$fedited by Giovanni Pighizzini, Cezar Cāmpeanu 205 $a1st ed. 2017. 210 1$aCham :$cSpringer International Publishing :$cImprint: Springer,$d2017. 215 $a1 online resource (X, 311 p. 76 illus.) 225 1 $aTheoretical Computer Science and General Issues,$x2512-2029 ;$v10316 311 $a3-319-60251-9 327 $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. 330 $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 ?eld in Computer Science that deals with the size of all kinds of objects that occur in computational models, such as turing machines, ?nite automata, grammars, splicing systems and others. The topics of this conference are related to all aspects of descriptional complexity. 410 0$aTheoretical Computer Science and General Issues,$x2512-2029 ;$v10316 606 $aComputer science 606 $aMachine theory 606 $aAlgorithms 606 $aSoftware engineering 606 $aComputer Science Logic and Foundations of Programming 606 $aTheory of Computation 606 $aFormal Languages and Automata Theory 606 $aAlgorithms 606 $aSoftware Engineering 615 0$aComputer science. 615 0$aMachine theory. 615 0$aAlgorithms. 615 0$aSoftware engineering. 615 14$aComputer Science Logic and Foundations of Programming. 615 24$aTheory of Computation. 615 24$aFormal Languages and Automata Theory. 615 24$aAlgorithms. 615 24$aSoftware Engineering. 676 $a005.1015113 702 $aPighizzini$b Giovanni$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aCāmpeanu$b Cezar$4edt$4http://id.loc.gov/vocabulary/relators/edt 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910483540803321 996 $aDescriptional Complexity of Formal Systems$91904989 997 $aUNINA