國立虎尾科技大學 |

Descriptional complexity of formal systems = 19th IFIP WG 1.02 International Conference, DCFS 2017, Milano, Italy, July 3-5, 2017 : proceedings /

Record Type:	Language materials, printed : Monograph/item
Title/Author:	Descriptional complexity of formal systems/ edited by Giovanni Pighizzini, Cezar Campeanu.
Reminder of title:	19th IFIP WG 1.02 International Conference, DCFS 2017, Milano, Italy, July 3-5, 2017 : proceedings /
remainder title:	DCFS 2017
other author:	Pighizzini, Giovanni.
corporate name:	Workshop on the Preservation of Stability under Discretization
Published:	Cham :Springer International Publishing : : 2017.,
Description:	x, 311 p. :ill., digital ; : 24 cm.;
Contained By:	Springer eBooks
Subject:	Formal methods (Computer science) -
Online resource:	http://dx.doi.org/10.1007/978-3-319-60252-3
ISBN:	9783319602523

Descriptional complexity of formal systems = 19th IFIP WG 1.02 International Conference, DCFS 2017, Milano, Italy, July 3-5, 2017 : proceedings /
Descriptional complexity of formal systems19th IFIP WG 1.02 International Conference, DCFS 2017, Milano, Italy, July 3-5, 2017 : proceedings /[electronic resource] :DCFS 2017edited by Giovanni Pighizzini, Cezar Campeanu. - Cham :Springer International Publishing :2017. - x, 311 p. :ill., digital ;24 cm. - Lecture notes in computer science,103160302-9743 ;. - Lecture notes in computer science ;6140..

Sensing 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.

This 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.

ISBN: 9783319602523

Standard No.: 10.1007/978-3-319-60252-3doiSubjects--Topical Terms:

564790
Formal methods (Computer science)

LC Class. No.: QA76.9.F67 / D34 2017

Dewey Class. No.: 004.0151

Descriptional complexity of formal systems = 19th IFIP WG 1.02 International Conference, DCFS 2017, Milano, Italy, July 3-5, 2017 : proceedings /
LDR:03341nam a2200361 a 4500 001 905616
003 DE-He213
005 20170602193941.0
006 m d
007 cr nn 008maaau
008 190308s2017 gw s 0 eng d
020 $a 9783319602523 $q (electronic bk.)
020 $a 9783319602516 $q (paper)
024 7 $a 10.1007/978-3-319-60252-3 $2 doi
035 $a 978-3-319-60252-3
040 $a GP $c GP
041 0 $a eng
050 4 $a QA76.9.F67 $b D34 2017
072 7 $a UM $2 bicssc
072 7 $a UYF $2 bicssc
072 7 $a COM051000 $2 bisacsh
072 7 $a COM036000 $2 bisacsh
082 0 4 $a 004.0151 $2 23
090 $a QA76.9.F67 $b D277 2017
111 2 $a Workshop on the Preservation of Stability under Discretization $d (2001 : $c Fort Collins, Colo.) $3 527686
245 1 0 $a Descriptional complexity of formal systems $h [electronic resource] : $b 19th IFIP WG 1.02 International Conference, DCFS 2017, Milano, Italy, July 3-5, 2017 : proceedings / $c edited by Giovanni Pighizzini, Cezar Campeanu.
246 3 $a DCFS 2017
260 $a Cham : $c 2017. $b Springer International Publishing : $b Imprint: Springer,
300 $a x, 311 p. : $b ill., digital ; $c 24 cm.
490 1 $a Lecture notes in computer science, $x 0302-9743 ; $v 10316
505 0 $a Sensing 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 $a This 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.
650 0 $a Formal methods (Computer science) $3 564790
650 0 $a Formal languages $v Congresses. $3 675203 $3 727858
650 1 4 $a Computer Science. $3 593922
650 2 4 $a Logics and Meanings of Programs. $3 670058
650 2 4 $a Computation by Abstract Devices. $3 669792
650 2 4 $a Mathematical Logic and Formal Languages. $3 670059
650 2 4 $a Algorithm Analysis and Problem Complexity. $3 593923
650 2 4 $a Software Engineering/Programming and Operating Systems. $3 669780
700 1 $a Pighizzini, Giovanni. $3 786274
700 1 $a Campeanu, Cezar. $3 1172858
710 2 $a SpringerLink (Online service) $3 593884
773 0 $t Springer eBooks
830 0 $a Lecture notes in computer science ; $v 6140. $3 744199
856 4 0 $u http://dx.doi.org/10.1007/978-3-319-60252-3
950 $a Computer Science (Springer-11645)