| 1. |
- Bensch, Suna, et al.
(författare)
-
Input-driven stack automata
- 2012
-
Ingår i: Theoretical computer science. - Berlin, Heidelberg : Springer Nature. - 9783642334740 - 9783642334757 ; , s. 28-42
-
Konferensbidrag (refereegranskat)abstract
- We introduce and investigate input-driven stack automata, which are a generalization of input-driven pushdown automata that recently became popular under the name visibly pushdown automata. Basically, the idea is that the input letters uniquely determine the operations on the pushdown store. This can nicely be generalized to stack automata by further types of input letters which are responsible for moving the stack pointer up or down. While visibly pushdown languages share many desirable properties with regular languages, input-driven stack automata languages do not necessarily so. We prove that deterministic and non- deterministic input-driven stack automata have different computational power, which shows in passing that one cannot construct a deterministic input-driven stack automaton from a nondeterministic one. We study the computational capacity of these devices. Moreover, it is shown that the membership problem for nondeterministic input-driven stack automata languages is NP-complete.
|
|
| 2. |
- Bensch, Suna, et al.
(författare)
-
On input-revolving deterministic and nondeterministic finite automata
- 2009
-
Ingår i: Information and Computation. - 0890-5401 .- 1090-2651. ; 207, s. 1140-1155
-
Tidskriftsartikel (refereegranskat)abstract
- We introduce and investigate input-revolving finite automata, which are (nondeterministic) finite state automata with additional ability to shift the remaining part of the input. Three different modes of shifting are considered, namely revolving to the left, revolving to the right, and circular-interchanging. We investigate the computational capacities of these three types of automata and their deterministic variants, comparing any of the six classes of automata with each other and with further classes of well-known automata. In particular, it is shown that nondeterminism is better than determinism, that is, for all three modes of shifting there is a language accepted by the nondeterministic model but not accepted by any determinstic automaton of the same type. Concerning the closure properties most of the deterministic language families studied are not closed under standard operations. For example, we show that the family of languages accepted by deterministic right-revolving finite automata is an anti-AFL which is not closed under reversal and intersection.
|
|
| 3. |
- Berglund, Martin, 1981-
(författare)
-
Complexities of Order-Related Formal Language Extensions
- 2014
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- The work presented in this thesis discusses various formal language formalisms that extend classical formalisms like regular expressions and context-free grammars with additional abilities, most relating to order. This is done while focusing on the impact these extensions have on the efficiency of parsing the languages generated. That is, rather than taking a step up on the Chomsky hierarchy to the context-sensitive languages, which makes parsing very difficult, a smaller step is taken, adding some mechanisms which permit interesting spatial (in)dependencies to be modeled.The most immediate example is shuffle formalisms, where existing language formalisms are extended by introducing operators which generate arbitrary interleavings of argument languages. For example, introducing a shuffle operator to the regular expressions does not make it possible to recognize context-free languages like anbn, but it does capture some non-context-free languages like the language of all strings containing the same number of as, bs and cs. The impact these additions have on parsing has many facets. Other than shuffle operators we also consider formalisms enforcing repeating substrings, formalisms moving substrings around, and formalisms that restrict which substrings may be concatenated. The formalisms studied here all have a number of properties in common.They are closely related to existing regular and context-free formalisms. They operate in a step-wise fashion, deriving strings by sequences of rule applications of individually limited power.Each step generates a constant number of symbols and does not modify parts that have already been generated. That is, strings are built in an additive fashion that does not explode in size (in contrast to e.g. Lindenmayer systems). All languages here will have a semi-linear Parikh image.They feature some interesting characteristic involving order or other spatial constraints. In the example of the shuffle multiple derivations are in a sense interspersed in a way that each is unaware of.All of the formalisms are intended to be limited enough to make an efficient parsing algorithm at least for some cases a reasonable goal.This thesis will give intuitive explanations of a number of formalisms fulfilling these requirements, and will sketch some results relating to the parsing problem for them. This should all be viewed as preparation for the more complete results and explanations featured in the papers given in the appendices.
|
|
| 4. |
- Drewes, Frank, et al.
(författare)
-
Tight Bounds for Cut-Operations on Deterministic Finite Automata
- 2015
-
Ingår i: Machines, Computations, and Universality. - Cham : Springer Publishing Company. - 9783319231112 - 9783319231105 ; , s. 45-60
-
Konferensbidrag (refereegranskat)abstract
- We investigate the state complexity of the cut and iterated cut operation for deterministic finite automata (DFAs), answering an open question stated in [M. Berglund, et al.: Cuts in regular expressions. In Proc. DLT, LNCS 7907, 2011]. These operations can be seen as an alternative to ordinary concatenation and Kleene star modelling leftmost maximal string matching. We show that the cut operation has a matching upper and lower bound of (n−1)⋅m+n(n−1)⋅m+n states on DFAs accepting the cut of two individual languages that are accepted by n- and m-state DFAs, respectively. In the unary case we obtain max(2n−1,m+n−2)max(2n−1,m+n−2) states as a tight bound. For accepting the iterated cut of a language accepted by an n-state DFA we find a matching bound of 1+(n+1)⋅F(1,n+2,−n+2;n+1∣−1)1+(n+1)⋅F(1,n+2,−n+2;n+1∣−1) states on DFAs, where FF refers to the generalized hypergeometric function. This bound is in the order of magnitude Θ((n−1)!)Θ((n−1)!). Finally, the bound drops to 2n−12n−1 for unary DFAs accepting the iterated cut of an n-state DFA and thus is similar to the bound for the cut operation on unary DFAs.
|
|
| 5. |
- Drewes, Frank, et al.
(författare)
-
Tight Bounds for Cut-Operations on Deterministic Finite Automata
- 2017
-
Ingår i: Fundamenta Informaticae. - : IOS Press. - 0169-2968 .- 1875-8681. - 9783319231112 - 9783319231105 ; 155, s. 89-110
-
Tidskriftsartikel (refereegranskat)abstract
- We investigate the state complexity of the cut and iterated cut operation for determin- istic finite automata (DFAs), answering an open question stated in [M. BERGLUND, et al.: Cuts in regular expressions. In Proc. DLT, LNCS 7907, 2011]. These operations can be seen as an al- ternative to ordinary concatenation and Kleene star modelling leftmost maximal string matching. We show that the cut operation has a matching upper and lower bound of n states, if m = 1, and (n−1)·m+n states, otherwise, on DFAs accepting the cut of two individual languages that are ac- cepted by n- and m-state DFAs, respectively. In the unary case we obtain max(2n − 1, m + n − 2) states as a tight bound—notice that for m ≤ n the bound for unary DFAs only depends on the former automaton and not on the latter. For accepting the iterated cut of a language accepted by an n-state DFA we find a matching bound of 1+(n+1)·F(1,n+2,−n+2;n+1 | −1) states on DFAs, if n ≥ 4 and where F refers to the generalized hypergeometric function. This bound is in the order of magnitude Θ((n − 1)!). Finally, the bound drops to 2n − 1 for unary DFAs accepting the iterated cut of an n-state DFA, if n ≥ 3, and thus is similar to the bound for the cut operation on unary DFAs.
|
|
| 6. |
- Storm, Christian, et al.
(författare)
-
A survey on general and temperature management of post cardiac arrest patients in large teaching and university hospitals in 14 European countries-The SPAME trial results
- 2017
-
Ingår i: Resuscitation. - : Elsevier BV. - 0300-9572. ; 116, s. 84-90
-
Tidskriftsartikel (refereegranskat)abstract
- Introduction: International guidelines recommend a bundle of care, including targeted temperature management (TTM), in post cardiac arrest survivors. Aside from a few small surveys in different European countries, adherence to the European Resuscitation Council (ERC) and European Society of Intensive Care Medicine (ESICM) recommendations are unknown. Methods: This international European telephone survey was conducted to provide an overview of current clinical practice of post cardiac arrest management with a main focus on TTM. We targeted large teaching and university hospitals within Europe as leading facilities and key opinion leaders in the field of post cardiac arrest care. Selected national principal investigators conducted the survey, which was based on a predefined questionnaire, between December 2014 and March 2015, before the publication of the ERC Guidelines 2015. Results: The return rate was 94% from 268 participating intensive care units (ICU). The majority had a predefined standard operating procedure (SOP) protocol for post cardiac arrest patients. Altogether, 68% of the ICUs provided TTM at a target temperature of 32-34. °C for 24. h, and 33% had changed the target temperature to 36. °C. The minority provided a written SOP for neurological prognostication, which was generally initiated 72. h after return of spontaneous circulation (ROSC). Electroencephalography and somatosensory evoked potentials were used by most ICUs for early prognostication. Treating more than fifty patients a year was significantly associated with providing written SOPs for TTM and prognostication (p. <. 0.01), as well as the use of a computer feedback device (p = 0.03) for TTM. Conclusion: This international European telephone survey revealed a high rate of implementation of TTM in post cardiac arrest patients in university and teaching hospitals. Most participants also provided a SOP, but only a minority had a SOP for neurological prognostication.
|
|
