Titlebook: Descriptional Complexity of Formal Systems; 22nd International C Galina Jirásková,Giovanni Pighizzini Conference proceedings 2020 Springer

Confer

书目名称Descriptional Complexity of Formal Systems影响因子(影响力)




书目名称Descriptional Complexity of Formal Systems影响因子(影响力)学科排名




书目名称Descriptional Complexity of Formal Systems网络公开度




书目名称Descriptional Complexity of Formal Systems网络公开度学科排名




书目名称Descriptional Complexity of Formal Systems被引频次




书目名称Descriptional Complexity of Formal Systems被引频次学科排名




书目名称Descriptional Complexity of Formal Systems年度引用




书目名称Descriptional Complexity of Formal Systems年度引用学科排名




书目名称Descriptional Complexity of Formal Systems读者反馈




书目名称Descriptional Complexity of Formal Systems读者反馈学科排名

用手捏

Mutually Accepting Capacitated Automata,tated automata model possible utilizations of systems with bounded resources. We study the basic properties of CAs: their expressive power in the nondeterministic and deterministic models, closure under classical operations, and the complexity of basic decision problems.

有组织

OASIS

中止

State Complexity Bounds for the Commutative Closure of Group Languages, states. Depending on the automaton in question, we label points of . by subsets of states and introduce unary automata which decompose the thus labelled grid. Based on these constructions, we give a general regularity condition, which is fulfilled for group languages.

工作

Operational Complexity of Straight Line Programs for Regular Languages,non-self-embedding grammars, since these models and SLPs are polynomially equivalent. We also examine . SLPs that may perform additional operations and show that the cost of simulating an extended SLP with shuffle or intersection by a conventional SLP is double exponential.

工作

高度表

Crisp-Determinization of Weighted Tree Automata over Additively Locally Finite and Past-Finite Monos crisp-determinizable if there exists an equivalent crisp-deterministic one. We prove that it is decidable whether weighted tree automata over additively locally finite and past-finite monotonic strong bimonoids are crisp-determinizable.

staging

Multiple Concatenation and State Complexity (Extended Abstract),18, Fund. Inform. 160, 255–279]. We prove that for ., the ternary alphabet is optimal. We also obtain lower bounds . and . in the binary and ternary case, respectively. Finally, we show that an upper bound for unary cyclic languages is . where . and ..

预定

Conference proceedings 2020olume were carefully reviewed and selected from 31 submissions. They deal with all aspects of descriptional complexity and costs of description of objects in various computational models, such as Turing machines, pushdown automata, finite automata, grammars, and others..