A formal-linguistic approach for solving an entertaining task is offered in this paper. The well-known task of the Hanoi towers is discussed in relation to some concepts of formal languages and grammars. A context-fre...A formal-linguistic approach for solving an entertaining task is offered in this paper. The well-known task of the Hanoi towers is discussed in relation to some concepts of formal languages and grammars. A context-free grammar which generates an algorithm for solving this task is described. A deterministic pushdown automation which in its work imitates the work of monks in solving the task of the Hanoi towers is built.展开更多
本文开展了超高性能混凝土材料(UHPC)后浇节点装配式钢筋混凝土(RC)梁–柱子结构的静力Pushdown试验以研究其抗倒塌性能。梁–柱子结构试件共设计制作了4个,几何尺寸相同,配筋形式相近,主要变量为梁纵筋在节点区的直线锚固长度。全现浇...本文开展了超高性能混凝土材料(UHPC)后浇节点装配式钢筋混凝土(RC)梁–柱子结构的静力Pushdown试验以研究其抗倒塌性能。梁–柱子结构试件共设计制作了4个,几何尺寸相同,配筋形式相近,主要变量为梁纵筋在节点区的直线锚固长度。全现浇试件S0的梁底部纵筋在梁柱节点区的直线锚固长度la为29 d (其中d为钢筋直径),而UHPC后浇试件PUS1、PUS2和PUS3的la分别为通长连续、20 d和10 d。试验结果表明:UHPC后浇节点试件与全现浇试件的破坏形态和裂缝发展过程相似,只是UHPC后浇试件开裂较早并集中在节点区附近;UHPC后浇试件的开裂荷载相较于整浇试件有所降低,而后浇试件的压拱机制承载力、悬链线机制承载力及其位移变形能力与全现浇试件的基本相当,甚至承载力略有提升;UHPC后浇试件减小中柱节点区梁纵筋的锚固长度,会降低试件的开裂荷载、压拱机制承载力及其位移,但是会提高悬链线机制的发展程度,增加悬链线机制承载力及其位移;当梁受拉纵筋在UHPC后浇区的锚固长度为20 d时,UHPC后浇试件的压拱机制和悬链线机制均能有较好的发挥。In this paper, static Pushdown tests of ultra-high performance concrete material (UHPC) post-cast-joint assembled reinforced concrete (RC) beam-column sub-assemblages were carried out to investigate the collapse behavior. A total of four specimens of beam-column sub-assemblages were designed and fabricated with the same geometry and similar reinforcements, with the main variable being the linear anchorage length of the beam longitudinal rebars in the joint zone. The linear anchorage length la of beam bottom longitudinal rebars in the joint zone for monolithic specimen S0 was 29 d (where d is the rebar diameter), while that of UHPC post-cast specimens PUS1, PUS2 and PUS3 was through-length continuous, 20 d and 10 d, respectively. The test results showed that the damage pattern and crack development process of UHPC post-cast specimens and monolithic specimen were similar, except that the UHPC post-cast specimens cracked earlier and the cracks tended to localize near the joint. The cracking load of the UHPC post-cast specimens was lower than that of monolithic specimen, while the load-carrying capacity of compression arch mechanism and catenary mechanism as well as the corresponding deformation capacity of the post-cast specimens were basically comparable with that of the monolithic specimen. Reducing the anchorage length of beam longitudinal rebars in the joint of the UHPC post-cast specimen decreased the cracking load, load carrying capacity of compression arch mechanism as well as the displacement, but would improve the development degree of the catenary mechanism and increase its load-carrying capacity and displacement. When the anchorage length of the beam longitudinal rebars in the UHPC post-cast joint was 20 d, UHPC post-cast specimens could achieve comparable performance of both compression arch mechanism and catenary mechanism with the monolithic specimen.展开更多
1-inkdot alternating pushdown automaton is a slightly modified alternating pushdown automaton with the additional power of marking at most 1 tape-cell on the input （with an inkdot） once. This paper investigates the ...1-inkdot alternating pushdown automaton is a slightly modified alternating pushdown automaton with the additional power of marking at most 1 tape-cell on the input （with an inkdot） once. This paper investigates the closure property of sublogarithmic space-bounded 1-inkdot alternating pushdown automata with only existential （universal） states, and shows, for example, that for any function L（n） such that L（n） ≥ log logn and L（n） = o（log n）, the class of sets accepted by weakly （strongly） L（n） space-bounded 1-inkdot two-way alternating pushdown automata with only existential （universal） states is not closed under concatenation with regular sets, length-preserving homomorphism, and Kleene closure.展开更多
Conditional pushdown systems (CPDSs) extend pushdown systems by associating each transition rule with a regular language over the stack alphabet. The goal is to model program verification problems that need to examine...Conditional pushdown systems (CPDSs) extend pushdown systems by associating each transition rule with a regular language over the stack alphabet. The goal is to model program verification problems that need to examine the run-time call stack of programs. Examples include security property checking of programs with stack inspection, compatibility checking of HTML5 parser specifications, etc. Esparza et al. proved that the reachability problem of CPDSs is EXPTIME-complete, which prevents the existence of an algorithm tractable for all instances in general. Driven by the practical applications of CPDSs, we study the reachability of patterned CPDS (pCPDS) that is a practically important subclass of CPDS, in which each transition rule carries a regular expression obeying certain patterns. First, we present new satura-tion algorithms for solving state and configuration reachability of pCPDSs. The algorithms exhibit the exponential-time complexity in the size of atomic patterns in the worst case. Next, we show that the reachability of pCPDSs carrying sim-ple patterns is solvable in fixed-parameter polynomial time and space. This answers the question on whether there exist tractable reachability analysis algorithms of CPDSs tailored for those practical instances that admit efficient solutions such as stack inspection without exception handling. We have evaluated the proposed approach, and our experiments show that the pattern-driven algorithm steadily scales on pCPDSs with simple patterns.展开更多
文摘A formal-linguistic approach for solving an entertaining task is offered in this paper. The well-known task of the Hanoi towers is discussed in relation to some concepts of formal languages and grammars. A context-free grammar which generates an algorithm for solving this task is described. A deterministic pushdown automation which in its work imitates the work of monks in solving the task of the Hanoi towers is built.
文摘本文开展了超高性能混凝土材料(UHPC)后浇节点装配式钢筋混凝土(RC)梁–柱子结构的静力Pushdown试验以研究其抗倒塌性能。梁–柱子结构试件共设计制作了4个,几何尺寸相同,配筋形式相近,主要变量为梁纵筋在节点区的直线锚固长度。全现浇试件S0的梁底部纵筋在梁柱节点区的直线锚固长度la为29 d (其中d为钢筋直径),而UHPC后浇试件PUS1、PUS2和PUS3的la分别为通长连续、20 d和10 d。试验结果表明:UHPC后浇节点试件与全现浇试件的破坏形态和裂缝发展过程相似,只是UHPC后浇试件开裂较早并集中在节点区附近;UHPC后浇试件的开裂荷载相较于整浇试件有所降低,而后浇试件的压拱机制承载力、悬链线机制承载力及其位移变形能力与全现浇试件的基本相当,甚至承载力略有提升;UHPC后浇试件减小中柱节点区梁纵筋的锚固长度,会降低试件的开裂荷载、压拱机制承载力及其位移,但是会提高悬链线机制的发展程度,增加悬链线机制承载力及其位移;当梁受拉纵筋在UHPC后浇区的锚固长度为20 d时,UHPC后浇试件的压拱机制和悬链线机制均能有较好的发挥。In this paper, static Pushdown tests of ultra-high performance concrete material (UHPC) post-cast-joint assembled reinforced concrete (RC) beam-column sub-assemblages were carried out to investigate the collapse behavior. A total of four specimens of beam-column sub-assemblages were designed and fabricated with the same geometry and similar reinforcements, with the main variable being the linear anchorage length of the beam longitudinal rebars in the joint zone. The linear anchorage length la of beam bottom longitudinal rebars in the joint zone for monolithic specimen S0 was 29 d (where d is the rebar diameter), while that of UHPC post-cast specimens PUS1, PUS2 and PUS3 was through-length continuous, 20 d and 10 d, respectively. The test results showed that the damage pattern and crack development process of UHPC post-cast specimens and monolithic specimen were similar, except that the UHPC post-cast specimens cracked earlier and the cracks tended to localize near the joint. The cracking load of the UHPC post-cast specimens was lower than that of monolithic specimen, while the load-carrying capacity of compression arch mechanism and catenary mechanism as well as the corresponding deformation capacity of the post-cast specimens were basically comparable with that of the monolithic specimen. Reducing the anchorage length of beam longitudinal rebars in the joint of the UHPC post-cast specimen decreased the cracking load, load carrying capacity of compression arch mechanism as well as the displacement, but would improve the development degree of the catenary mechanism and increase its load-carrying capacity and displacement. When the anchorage length of the beam longitudinal rebars in the UHPC post-cast joint was 20 d, UHPC post-cast specimens could achieve comparable performance of both compression arch mechanism and catenary mechanism with the monolithic specimen.
基金This work is supported by the National Natural Science Foundation of China under Grant No. 60403012,
文摘1-inkdot alternating pushdown automaton is a slightly modified alternating pushdown automaton with the additional power of marking at most 1 tape-cell on the input （with an inkdot） once. This paper investigates the closure property of sublogarithmic space-bounded 1-inkdot alternating pushdown automata with only existential （universal） states, and shows, for example, that for any function L（n） such that L（n） ≥ log logn and L（n） = o（log n）, the class of sets accepted by weakly （strongly） L（n） space-bounded 1-inkdot two-way alternating pushdown automata with only existential （universal） states is not closed under concatenation with regular sets, length-preserving homomorphism, and Kleene closure.
基金This work was supported by the National Natural Science Foundation of China under Grant Nos.61802126,61672229,61832015 and 62072176the Ministry of Science and Technology of the People’s Republic of China under Grant No.2018YFC0830400Shanghai Pujiang Program under Grant No.17PJ1402200.
文摘Conditional pushdown systems (CPDSs) extend pushdown systems by associating each transition rule with a regular language over the stack alphabet. The goal is to model program verification problems that need to examine the run-time call stack of programs. Examples include security property checking of programs with stack inspection, compatibility checking of HTML5 parser specifications, etc. Esparza et al. proved that the reachability problem of CPDSs is EXPTIME-complete, which prevents the existence of an algorithm tractable for all instances in general. Driven by the practical applications of CPDSs, we study the reachability of patterned CPDS (pCPDS) that is a practically important subclass of CPDS, in which each transition rule carries a regular expression obeying certain patterns. First, we present new satura-tion algorithms for solving state and configuration reachability of pCPDSs. The algorithms exhibit the exponential-time complexity in the size of atomic patterns in the worst case. Next, we show that the reachability of pCPDSs carrying sim-ple patterns is solvable in fixed-parameter polynomial time and space. This answers the question on whether there exist tractable reachability analysis algorithms of CPDSs tailored for those practical instances that admit efficient solutions such as stack inspection without exception handling. We have evaluated the proposed approach, and our experiments show that the pattern-driven algorithm steadily scales on pCPDSs with simple patterns.
