{"id":"W2061265323","doi":"10.1016/j.tcs.2009.01.004","title":"Nondeterministic state complexity of nested word automata","year":2009,"lang":"en","type":"article","venue":"Theoretical Computer Science","topic":"semigroups and automata theory","field":"Computer Science","cited_by":23,"is_retracted":false,"has_abstract":false,"ca_institutions":"Queen's University","funders":"Natural Sciences and Engineering Research Council of Canada","keywords":"Nondeterministic algorithm; Nondeterministic finite automaton; Nested word; Word (group theory); Discrete mathematics; Deterministic finite automaton; Intersection (aeronautics); Mathematics; Upper and lower bounds; Combinatorics; Automaton; Finite-state machine; Automata theory; Computer science; Quantum finite automata; Theoretical computer science; Algorithm","routes":{"ca_aff":true,"ca_fund":true,"ca_venue":false,"about_ca":false,"invisible_to_affiliation_only":false},"retraction":null,"screen":null,"direct_labels":[],"prediction":{"model_version":"metacan-v3-hybrid-931329e0061c","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.002501664,0.0005119886,0.001505736,0.001143964,0.001664334,0.006076335,0.002088342,0.001517001,0.006318136],"category_scores_gemma":[0.02257256,0.0008333637,0.001524261,0.001365471,0.003237188,0.01334098,0.002713335,0.003745915,0.0004464045],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.002901318,"about_ca_system_score_gemma":0.00202367,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.002167965,"about_ca_topic_score_gemma":0.002286813,"domain_scores_codex":[0.9958764,0.001166798,0.0003451178,0.0007950987,0.001306561,0.0005099786],"domain_scores_gemma":[0.9542304,0.03853951,0.001567351,0.002894286,0.001767842,0.001000611],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"theoretical_or_conceptual","study_design_gemma":"theoretical_or_conceptual","study_design_scores_codex":[0.0002539579,0.000108366,0.001946029,0.0001145529,0.00003898959,0.0001968162,0.0009844246,0.03873389,0.003115664,0.9445148,0.0008121658,0.009180437],"study_design_scores_gemma":[0.00002022274,0.00001591017,0.0003510939,0.00000720014,0.00001597218,0.00004413465,0.00006529781,0.1129608,0.001058996,0.8850876,0.0003541638,0.00001857925],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"empirical","genre_gemma":"empirical","genre_scores_codex":[0.7413291,0.0005859311,0.2337545,0.002267277,0.00008020793,0.00009509707,0.0007129156,0.0003695673,0.02080536],"genre_scores_gemma":[0.9832028,0.0001748241,0.01258438,0.00007318194,0.00006743431,0.00009571313,0.0002970408,0.00007973585,0.00342486],"genre_candidate":"empirical","genre_consensus":"empirical","teacher_disagreement_score":0.006318136,"threshold_uncertainty_score":0.02113622,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.01999266988656173,"score_gpt":0.2667129231920374,"score_spread":0.2467202533054757,"validation_status":"score_only:v0-immature-baseline","note":"Baseline scores from an immature model (maturity gate not passed). Scores rank; they never assert a category."}}