Document Search Results

Bezhanishvili, Nick; Bonsangue, Marcello M.; Hansen, Helle Hvid; Kozen, Dexter; Kupke, Clemens; Panangaden, Prakash; Silva, Alexandra

Minimisation in logical form. (English) Zbl 07920676

Palmigiano, Alessandra (ed.) et al., Samson Abramsky on logic and structure in computer science and beyond. Cham: Springer. Outst. Contrib. Log. 25, 89-127 (2023).

MSC: 03B70 68Qxx 81P68

Cite Review PDF

Full Text: DOI arXiv

Fiedor, Tomáš; Holík, Lukáš; Hruška, Martin; Rogalewicz, Adam; Síč, Juraj; Vargovčík, Pavol

Reasoning about regular properties: a comparative study. (English) Zbl 07838493

Pientka, Brigitte (ed.) et al., Automated deduction – CADE 29. 29th international conference on automated deduction, Rome, Italy, July 1–4, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 14132, 286-306 (2023).

MSC: 03B35 68V15

Cite Review PDF

Full Text: DOI arXiv

Jirásková, Galina

Operations on Boolean and alternating finite automata. (English) Zbl 07828935

Gazdag, Zsolt (ed.) et al., Proceedings of the 16th international conference on automata and formal languages, AFL, Eger, Hungary, September 5–7, 2023. Waterloo: Open Publishing Association (OPA). Electron. Proc. Theor. Comput. Sci. (EPTCS) 386, 3-10 (2023).

MSC: 68Q45

Cite Review PDF

Full Text: DOI arXiv

Grabolle, Gustav

A Nivat theorem for weighted alternating automata over commutative semirings. (English) Zbl 07788999

Log. Methods Comput. Sci. 19, No. 4, Paper No. 27, 25 p. (2023).

MSC: 68Q45 03D05 68Q70

Cite Review PDF

Full Text: DOI arXiv

OA License

Moreira, Nelma; Reis, Rogério

Manipulation of regular expressions using derivatives: an overview. (English) Zbl 07572309

Caron, Pascal (ed.) et al., Implementation and application of automata. 26th international conference, CIAA 2022, Rouen, France, June 28 – July 1, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13266, 19-33 (2022).

MSC: 68Q45

Cite Review PDF

Full Text: DOI

Peltomäki, Jarkko; Salo, Ville

Automatic winning shifts. (English) Zbl 1507.68170

Inf. Comput. 285, Part B, Article ID 104883, 21 p. (2022).

Reviewer: Michel Rigo (Liège)

MSC: 68Q45 11B85 37B51 68R15 91A46

Cite Review PDF

Full Text: DOI arXiv

OA License

Kunc, Michal; Okhotin, Alexander

Language equations. (English) Zbl 1510.68038

Pin, Jean-Éric (ed.), Handbook of automata theory. Volume I. Theoretical foundations. Berlin: European Mathematical Society (EMS). 765-799 (2021).

MSC: 68Q45

Cite Review PDF

Full Text: DOI

Gruber, Hermann; Holzer, Markus; Kutrib, Martin

Descriptional complexity of regular languages. (English) Zbl 1510.68036

Pin, Jean-Éric (ed.), Handbook of automata theory. Volume I. Theoretical foundations. Berlin: European Mathematical Society (EMS). 411-457 (2021).

MSC: 68Q45

Cite Review PDF

Full Text: DOI

Kapoutsis, Christos; Zakzok, Mohammad

Alternation in two-way finite automata. (English) Zbl 1504.68104

Theor. Comput. Sci. 870, 75-102 (2021).

MSC: 68Q45

Cite Review PDF

Full Text: DOI

OA License

Bournez, Olivier; Dowek, Gilles; Gilleron, Rémi; Grigorieff, Serge; Marion, Jean-Yves; Perdrix, Simon; Tison, Sophie

Theoretical computer science: computational complexity. (English) Zbl 07910886

Marquis, Pierrei (ed.) et al., A guided tour of artificial intelligence research. Volume III. Interfaces and applications of artificial intelligence. Cham: Springer. 51-89 (2020).

MSC: 68Q25 68Q12 68Q30 68Q45

Cite Review PDF

Full Text: DOI

Ferrère, Thomas; Maler, Oded; Ničković, Dejan; Pnueli, Amir

From real-time logic to timed automata. (English) Zbl 1473.68107

J. ACM 66, No. 3, Article No. 19, 31 p. (2019).

MSC: 68Q60 03B44 68Q45

Cite Review PDF

Full Text: DOI

Jirásková, Galina; Krajňáková, Ivana

Square on deterministic, alternating, and Boolean finite automata. (English) Zbl 1427.68147

Int. J. Found. Comput. Sci. 30, No. 6-7, 1117-1134 (2019).

MSC: 68Q45

Cite Review PDF

Full Text: DOI

Tian, Cong; Duan, Zhenhua

Model checking open systems with alternating projection temporal logic. (English) Zbl 1423.68293

Theor. Comput. Sci. 774, 65-81 (2019).

MSC: 68Q60 03B44 68Q45 68Q85

Cite Review PDF

Full Text: DOI

Hospodár, Michal; Jirásková, Galina; Mlynárčik, Peter

Descriptional complexity of the forever operator. (English) Zbl 1415.68130

Int. J. Found. Comput. Sci. 30, No. 1, 115-134 (2019).

MSC: 68Q45

Cite Review PDF

Full Text: DOI

D’Antoni, Loris; Kincaid, Zachary; Wang, Fang

A symbolic decision procedure for symbolic alternating finite automata. (English) Zbl 1525.68068

Silva, Alexandra (ed.), Proceedings of the 33rd conference on the mathematical foundations of programming semantics (MFPS XXXIII), Ljubljana, Slovenia, June 12–15, 2017. Amsterdam: Elsevier. Electron. Notes Theor. Comput. Sci. 336, 79-99 (2018).

MSC: 68Q45 68Q60

Cite Review PDF

Full Text: DOI arXiv

Hospodár, Michal; Jirásková, Galina

The complexity of concatenation on deterministic and alternating finite automata. (English) Zbl 1486.68096

RAIRO, Theor. Inform. Appl. 52, No. 2-4, 153-168 (2018).

MSC: 68Q45

Cite Review PDF

Full Text: DOI

Hospodár, Michal; Jirásková, Galina; Krajňáková, Ivana

Operations on Boolean and alternating finite automata. (English) Zbl 1484.68089

Fomin, Fedor V. (ed.) et al., Computer science – theory and applications. 13th international computer science symposium in Russia, CSR 2018, Moscow, Russia, June 6–10, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10846, 181-193 (2018).

MSC: 68Q45

Cite Review PDF

Full Text: DOI

Chida, Nariyoshi; Kuramitsu, Kimio

Linear parsing expression grammars. (English) Zbl 1485.68126

Drewes, Frank (ed.) et al., Language and automata theory and applications. 11th international conference, LATA 2017, Umeå, Sweden, March 6–9, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10168, 275-286 (2017).

MSC: 68Q42 68Q45

Cite Review PDF

Full Text: DOI arXiv

Farzan, Azadeh; Kincaid, Zachary; Podelski, Andreas

Proving liveness of parameterized programs. (English) Zbl 1401.68038

Proceedings of the 2016 31st annual ACM/IEEE symposium on logic in computer science, LICS 2016, New York City, NY, USA, July 5–8, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4391-6). 185-196 (2016).

MSC: 68N30 68Q85

Cite Review PDF

Full Text: DOI arXiv

Furusawa, Hitoshi; Struth, Georg

Taming multirelations. (English) Zbl 1407.03080

ACM Trans. Comput. Log. 17, No. 4, Article No. 28, 34 p. (2016).

MSC: 03G25 03E20 06F07 68Q85

Cite Review PDF

Full Text: DOI arXiv

Palmovský, Matúš

Kleene closure and state complexity. (English) Zbl 1357.68107

RAIRO, Theor. Inform. Appl. 50, No. 3, 251-261 (2016).

MSC: 68Q45

Cite Review PDF

Full Text: DOI Link

Furusawa, Hitoshi; Struth, Georg

Concurrent dynamic algebra. (English) Zbl 1367.03054

ACM Trans. Comput. Log. 16, No. 4, Article No. 30, 38 p. (2015).

MSC: 03B70 03B45 03G25 68Q85 68T15

Cite Review PDF

Full Text: DOI arXiv

Farzan, Azadeh; Kincaid, Zachary; Podelski, Andreas

Proof spaces for unbounded parallelism. (English) Zbl 1345.68102

Proceedings of the 42nd ACM SIGPLAN-SIGACT symposium on principles of programming languages, POPL ’15, Mumbai, India, January 12–18, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3300-9). 407-420 (2015).

MSC: 68N30 68Q45 68Q60

Cite Review PDF

Full Text: DOI

Jacobs, Bart; Silva, Alexandra; Sokolova, Ana

Trace semantics via determinization. (English) Zbl 1327.68158

J. Comput. Syst. Sci. 81, No. 5, 859-879 (2015).

MSC: 68Q55 18C50

Cite Review PDF

Full Text: DOI HAL

Tian, Cong; Duan, Zhenhua; Yang, Mengfei

Transformation from PLTL to automata via NFGs. (English) Zbl 1319.68144

J. Comb. Optim. 29, No. 2, 406-417 (2015).

MSC: 68Q60 03B44 03D05 68Q45

Cite Review PDF

Full Text: DOI

Ionescu, Adrian; Leiss, Ernst L.

On the role of complementation in implicit language equations and relations. (English) Zbl 1433.68196

J. Comput. Syst. Sci. 80, No. 2, 457-467 (2014).

MSC: 68Q45 06E30

Cite Review PDF

Full Text: DOI

Farzan, Azadeh; Kincaid, Zachary; Podelski, Andreas

Inductive data flow graphs. (English) Zbl 1301.68178

Proceedings of the 40th annual ACM SIGPLAN-SIGACT symposium on principles of programming languages, POPL ’13, Rome, Italy, January 23–25, 2013. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-1832-7). 129-142 (2013).

MSC: 68Q60 68N30 68Q85 68W05

Cite Review PDF

Full Text: DOI

Bojanczyk, Mikolaj; Braud, Laurent; Klin, Bartek; Lasota, Slawomir

Towards nominal computation. (English) Zbl 1321.68139

Proceedings of the 39th annual ACM SIGPLAN-SIGACT symposium on principles of programming languages, POPL ’12, Philadelphia, PA, USA, January 22–28, 2012. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-1083-3). 401-412 (2012).

MSC: 68N18 68N15 68Q45

Cite Review PDF

Full Text: DOI Link

Holzer, Markus; Kutrib, Martin

Descriptional and computational complexity of finite automata – a survey. (English) Zbl 1217.68130

Inf. Comput. 209, No. 3, 456-470 (2011).

MSC: 68Q45 68Q25

Cite Review PDF

Full Text: DOI

Okhotin, Alexander

Decision problems for language equations. (English) Zbl 1201.68067

J. Comput. Syst. Sci. 76, No. 3-4, 251-266 (2010).

MSC: 68Q45 03D05 68Q17

Cite Review PDF

Full Text: DOI

Holzer, Markus; Kutrib, Martin

Descriptional and computational complexity of finite automata. (English) Zbl 1234.68211

Dediu, Adrian Horia (ed.) et al., Language and automata theory and applications. Third international conference, LATA 2009, Tarragona, Spain, April 2–8, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-00981-5/pbk). Lecture Notes in Computer Science 5457, 23-42 (2009).

MSC: 68Q45 68Q25

Cite Review PDF

Full Text: DOI

Kupferman, Orna; Piterman, Nir

Lower bounds on witnesses for nonemptiness of universal co-Büchi automata. (English) Zbl 1234.68221

de Alfaro, Luca (ed.), Foundations of software science and computational structures. 12th international conference, FOSSACS 2009, held as part of the joint European conferences on theory and practice of software, ETAPS 2009, York, UK, March 22–29, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-00595-4/pbk). Lecture Notes in Computer Science 5504, 182-196 (2009).

MSC: 68Q45 68Q60

Cite Review PDF

Full Text: DOI

Hirst, Tirza

A Rice-style theorem for parallel automata. (English) Zbl 1169.68025

Inf. Comput. 207, No. 1, 1-13 (2009).

MSC: 68Q45 68Q17

Cite Review PDF

Full Text: DOI

Ésik, Zoltán; Kuich, Werner

Boolean fuzzy sets. (English) Zbl 1183.68338

Int. J. Found. Comput. Sci. 18, No. 6, 1197-1207 (2007).

MSC: 68Q45 68Q70 03E72

Cite Review PDF

Full Text: DOI

Massazza, Paolo; Salmela, Petri

On the simplest centralizer of a language. (English) Zbl 1112.68097

Theor. Inform. Appl. 40, No. 2, 295-301 (2006).

MSC: 68Q70 68R15

Cite Review PDF

Full Text: DOI Numdam EuDML Link

Okhotin, Alexander

Unresolved systems of language equations: expressive power and decision problems. (English) Zbl 1086.68077

Theor. Comput. Sci. 349, No. 3, 283-308 (2005).

MSC: 68Q45 03D05

Cite Review PDF

Full Text: DOI

Dixon, Clare; Bolotov, Alexander; Fisher, Michael

Alternating automata and temporal logic normal forms. (English) Zbl 1087.03013

Ann. Pure Appl. Logic 135, No. 1-3, 263-285 (2005).

MSC: 03B44 68Q45 68Q60

Cite Review PDF

Full Text: DOI

van Zijl, Lynette

Generalized acceptance, succinctness and supernondeterministic finite automata. (English) Zbl 1069.68072

Theor. Comput. Sci. 313, No. 1, 159-172 (2004).

MSC: 68Q45

Cite Review PDF

Full Text: DOI

Zhang, Guo-Qiang

Domain \(\mu\)-calculus. (English) Zbl 1038.03038

Theor. Inform. Appl. 37, No. 4, 337-364 (2003).

MSC: 03B70 68Q45 68Q55

Cite Review PDF

Full Text: DOI Numdam EuDML

Piterman, Nir; Vardi, Moshe Y.

From bidirectionality to alternation. (English) Zbl 1044.68101

Theor. Comput. Sci. 295, No. 1-3, 295-321 (2003).

MSC: 68Q45

Cite Review PDF

Full Text: DOI

Ayari, Abdelwaheb; Basin, David; Klaedtke, Felix

Decision procedures for inductive Boolean functions based on alternating automata. (English) Zbl 1028.68079

Theor. Comput. Sci. 300, No. 1-3, 301-329 (2003).

MSC: 68Q45

Cite Review PDF

Full Text: DOI

Okhotin, Alexander

On the closure properties of linear conjunctive languages. (English) Zbl 1042.68069

Theor. Comput. Sci. 299, No. 1-3, 663-685 (2003).

MSC: 68Q45

Cite Review PDF

Full Text: DOI

Choffrut, Christian; Karhumäki, Juhani; Ollinger, Nicolas

The commutation of finite sets: A challenging problem. (English) Zbl 1014.68128

Theor. Comput. Sci. 273, No. 1-2, 69-79 (2002).

MSC: 68R15

Cite Review PDF

Full Text: DOI

Massazza, P.

On the root of languages. (English) Zbl 1022.68071

Int. J. Algebra Comput. 11, No. 5, 549-563 (2001).

MSC: 68Q45 68Q70 68Q17

Cite Review PDF

Full Text: DOI

Salomaa, Kai (ed.); Wood, Derick (ed.); Yu, Sheng (ed.)

Implementing automata. Selected papers from the 2nd international workshop, WIA ’97, Univ. of Western Ontario, London, Ontario, Canada, September 18–20, 1997. (English) Zbl 0948.00048

Theor. Comput. Sci. 231, No. 1, 140 p. (2000).

MSC: 00B25 68-06

Cite Review PDF

Full Text: DOI

Salomaa, K.; Wu, X.; Yu, S.

Efficient implementation of regular languages using reversed alternating finite automata. (English) Zbl 0951.68061

Theor. Comput. Sci. 231, No. 1, 103-111 (2000).

MSC: 68Q45

Cite Review PDF

Full Text: DOI

Salomaa, K.; Yu, S.

Alternating finite automata and star-free languages. (English) Zbl 0944.68090

Theor. Comput. Sci. 234, No. 1-2, 167-176 (2000).

MSC: 68Q45

Cite Review PDF

Full Text: DOI

Redziejowski, Roman R.

Construction of a deterministic \(\omega\)-automaton using derivatives. (English) Zbl 0946.68078

Theor. Inform. Appl. 33, No. 2, 133-158 (1999).

MSC: 68Q45 68R15

Cite Review PDF

Full Text: DOI EuDML

Vardi, Moshe Y.

Alternating automata: unifying truth and validity checking for temporal logics. (English) Zbl 1430.68156

McCune, William (ed.), Automated deduction – CADE-14. 14th international conference on automated deduction, Townsville, North Queensland, Australia. July 13–17, 1997. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1249, 191-206 (1997).

MSC: 68Q60 03B44 03D05 68Q45

Cite Review PDF

Full Text: DOI

Antimirov, Valentin

Partial derivatives of regular expressions and finite automaton constructions. (English) Zbl 0872.68120

Theor. Comput. Sci. 155, No. 2, 291-319 (1996).

MSC: 68Q45 68W15

Cite Review PDF

Full Text: DOI

Birget, J.-C.

Two-way automata and length-preserving homomorphisms. (English) Zbl 0846.68071

Math. Syst. Theory 29, No. 3, 191-226 (1996).

MSC: 68Q45 68Q05

Cite Review PDF

Full Text: DOI

Vardi, Moshe Y.

An automata-theoretic approach to linear temporal logic. (English) Zbl 1543.68236

Moller, Faron (ed.) et al., Logics for concurrency: structure versus automata. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 1043, 238-266 (1996).

MSC: 68Q60 03B44 03B70 68N30 68Q45

Cite Review PDF

Full Text: DOI

Givan, Robert

Inferring program specifications in polynomial-time. (English) Zbl 1482.68138

Cousot, Radhia (ed.) et al., Static analysis. Third international symposium, SAS ’96, Aachen, Germany, September 24–26, 1996. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1145, 205-219 (1996).

MSC: 68Q60 68N18

Cite Review PDF

Full Text: DOI

Birget, Jean-Camille

**The state complexity of \(\overline{\varSigma ^*\overline{L}}\) and its connection with temporal logic.** (English) Zbl 1410.68197

Inf. Process. Lett. 58, No. 4, 185-188 (1996).

MSC: 68Q45 03B44

Cite Review PDF

Full Text: DOI

Antimirov, Valentin M.; Mosses, Peter D.

Rewriting extended regular expressions. (English) Zbl 0873.68104

Theor. Comput. Sci. 143, No. 1, 51-72 (1995).

MSC: 68Q42

Cite Review PDF

Full Text: DOI

Leiss, Ernst L.

Implicit language equations: existence and uniqueness of solutions. (English) Zbl 0874.68164

Theor. Comput. Sci. 145, No. 1-2, 71-93 (1995).

MSC: 68Q45

Cite Review PDF

Full Text: DOI

Fellah, Abdelaziz

Equations and regular-like expressions for AFA. (English) Zbl 0832.68073

Int. J. Comput. Math. 51, No. 3-4, 157-172 (1994).

MSC: 68Q45

Cite Review PDF

Full Text: DOI

Leiss, E. L.

Unrestricted complementation in language equations over a one-letter alphabet. (English) Zbl 0821.68076

Theor. Comput. Sci. 132, No. 1-2, 71-84 (1994).

MSC: 68Q45

Cite Review PDF

Full Text: DOI

Leiss, Ernst L.

Language equations over a one-letter alphabet with union, concatenation and star: A complete solution. (English) Zbl 0861.68052

Theor. Comput. Sci. 131, No. 2, 311-330 (1994).

MSC: 68Q45 68R15

Cite Review PDF

Full Text: DOI

Birget, Jean-Camille

State-complexity of finite-state devices, state compressibility and incompressibility. (English) Zbl 0779.68061

Math. Syst. Theory 26, No. 3, 237-269 (1993).

Reviewer: K.Peeva (Sofia)

MSC: 68Q45

Cite Review PDF

Full Text: DOI

Birget, Jean-Camille

Positional simulation of two-way automata: Proof of a conjecture of R. Kannan and generalizations. (English) Zbl 0769.68019

J. Comput. Syst. Sci. 45, No. 2, 154-179 (1992).

MSC: 68Q05 68Q45 20M35

Cite Review PDF

Full Text: DOI

Abrahamson, Karl R.

Succinct representation of regular sets using gotos and Boolean variables. (English) Zbl 0642.68025

J. Comput. Syst. Sci. 34, 129-148 (1987).

MSC: 68Q60 03B70

Cite Review PDF

Full Text: DOI

Muller, David E.; Schupp, Paul E.

Alternating automata on infinite trees. (English) Zbl 0636.68108

Theor. Comput. Sci. 54, 267-276 (1987).

Reviewer: A.V.Anisimov

MSC: 68Q45 68Q05

Cite Review PDF

Full Text: DOI

Leiss, Ernst L.

Generalized language equations with multiple solutions. (English) Zbl 0606.68071

Theor. Comput. Sci. 44, 155-174 (1986).

Reviewer: B.Zelinka

MSC: 68Q45

Cite Review PDF

Full Text: DOI

Leiss, Ernst

Succinct representation of regular languages by Boolean automata. II. (English) Zbl 0582.68028

Theor. Comput. Sci. 38, 133-136 (1985).

MSC: 68Q45

Cite Review PDF

Full Text: DOI

Leiss, Ernst

On classes of tractable unrestricted regular expressions. (English) Zbl 0571.68072

Theor. Comput. Sci. 35, 313-327 (1985).

Reviewer: A.V.Anisimov

MSC: 68Q45

Cite Review PDF

Full Text: DOI

Leiss, Ernst

Succinct representation of regular languages by Boolean automata. (English) Zbl 0458.68017

Theor. Comput. Sci. 13, 323-330 (1981).

MSC: 68Q45 68Q25

Cite Review PDF

Full Text: DOI

Leiss, Ernst

On generalized language equations. (English) Zbl 0454.68105

Theor. Comput. Sci. 14, 63-77 (1981).

MSC: 68T99

Cite Review PDF

Full Text: DOI

Found 68 Documents (Results 1–68)

Minimisation in logical form. (English) Zbl 07920676

Reasoning about regular properties: a comparative study. (English) Zbl 07838493

Operations on Boolean and alternating finite automata. (English) Zbl 07828935

A Nivat theorem for weighted alternating automata over commutative semirings. (English) Zbl 07788999

Manipulation of regular expressions using derivatives: an overview. (English) Zbl 07572309

Automatic winning shifts. (English) Zbl 1507.68170

Language equations. (English) Zbl 1510.68038

Descriptional complexity of regular languages. (English) Zbl 1510.68036

Alternation in two-way finite automata. (English) Zbl 1504.68104

Theoretical computer science: computational complexity. (English) Zbl 07910886

From real-time logic to timed automata. (English) Zbl 1473.68107

Square on deterministic, alternating, and Boolean finite automata. (English) Zbl 1427.68147

Model checking open systems with alternating projection temporal logic. (English) Zbl 1423.68293

Descriptional complexity of the forever operator. (English) Zbl 1415.68130

A symbolic decision procedure for symbolic alternating finite automata. (English) Zbl 1525.68068

The complexity of concatenation on deterministic and alternating finite automata. (English) Zbl 1486.68096

Operations on Boolean and alternating finite automata. (English) Zbl 1484.68089

Linear parsing expression grammars. (English) Zbl 1485.68126

Proving liveness of parameterized programs. (English) Zbl 1401.68038

Taming multirelations. (English) Zbl 1407.03080

Kleene closure and state complexity. (English) Zbl 1357.68107

Concurrent dynamic algebra. (English) Zbl 1367.03054

Proof spaces for unbounded parallelism. (English) Zbl 1345.68102

Trace semantics via determinization. (English) Zbl 1327.68158

Transformation from PLTL to automata via NFGs. (English) Zbl 1319.68144

On the role of complementation in implicit language equations and relations. (English) Zbl 1433.68196

Inductive data flow graphs. (English) Zbl 1301.68178

Towards nominal computation. (English) Zbl 1321.68139

Descriptional and computational complexity of finite automata – a survey. (English) Zbl 1217.68130

Decision problems for language equations. (English) Zbl 1201.68067

Descriptional and computational complexity of finite automata. (English) Zbl 1234.68211

Lower bounds on witnesses for nonemptiness of universal co-Büchi automata. (English) Zbl 1234.68221

A Rice-style theorem for parallel automata. (English) Zbl 1169.68025

Boolean fuzzy sets. (English) Zbl 1183.68338

On the simplest centralizer of a language. (English) Zbl 1112.68097

Unresolved systems of language equations: expressive power and decision problems. (English) Zbl 1086.68077

Alternating automata and temporal logic normal forms. (English) Zbl 1087.03013

Generalized acceptance, succinctness and supernondeterministic finite automata. (English) Zbl 1069.68072

Domain \(\mu\)-calculus. (English) Zbl 1038.03038

From bidirectionality to alternation. (English) Zbl 1044.68101

Decision procedures for inductive Boolean functions based on alternating automata. (English) Zbl 1028.68079

On the closure properties of linear conjunctive languages. (English) Zbl 1042.68069

The commutation of finite sets: A challenging problem. (English) Zbl 1014.68128

On the root of languages. (English) Zbl 1022.68071

Implementing automata. Selected papers from the 2nd international workshop, WIA ’97, Univ. of Western Ontario, London, Ontario, Canada, September 18–20, 1997. (English) Zbl 0948.00048

Efficient implementation of regular languages using reversed alternating finite automata. (English) Zbl 0951.68061

Alternating finite automata and star-free languages. (English) Zbl 0944.68090

Construction of a deterministic \(\omega\)-automaton using derivatives. (English) Zbl 0946.68078

Alternating automata: unifying truth and validity checking for temporal logics. (English) Zbl 1430.68156

Partial derivatives of regular expressions and finite automaton constructions. (English) Zbl 0872.68120

Two-way automata and length-preserving homomorphisms. (English) Zbl 0846.68071

An automata-theoretic approach to linear temporal logic. (English) Zbl 1543.68236

Inferring program specifications in polynomial-time. (English) Zbl 1482.68138

The state complexity of \(\overline{\varSigma ^*\overline{L}}\) and its connection with temporal logic. (English) Zbl 1410.68197

Rewriting extended regular expressions. (English) Zbl 0873.68104

Implicit language equations: existence and uniqueness of solutions. (English) Zbl 0874.68164

Equations and regular-like expressions for AFA. (English) Zbl 0832.68073

Unrestricted complementation in language equations over a one-letter alphabet. (English) Zbl 0821.68076

Language equations over a one-letter alphabet with union, concatenation and star: A complete solution. (English) Zbl 0861.68052

State-complexity of finite-state devices, state compressibility and incompressibility. (English) Zbl 0779.68061

Positional simulation of two-way automata: Proof of a conjecture of R. Kannan and generalizations. (English) Zbl 0769.68019

Succinct representation of regular sets using gotos and Boolean variables. (English) Zbl 0642.68025

Alternating automata on infinite trees. (English) Zbl 0636.68108

Generalized language equations with multiple solutions. (English) Zbl 0606.68071

Succinct representation of regular languages by Boolean automata. II. (English) Zbl 0582.68028

On classes of tractable unrestricted regular expressions. (English) Zbl 0571.68072

Succinct representation of regular languages by Boolean automata. (English) Zbl 0458.68017

On generalized language equations. (English) Zbl 0454.68105

Filter Results by …

Document Type

Author

Serial

Year of Publication

Main Field

Software

**The state complexity of \(\overline{\varSigma ^*\overline{L}}\) and its connection with temporal logic.** (English) Zbl 1410.68197